C++数据结构与算法工程实现：哈希表、并查集与对拍落地-平芜编程栈

简介：这是一本面向有一定C++基础、希望系统提升算法设计与实现能力的开发者与计算机专业学生的PDF电子书，原书由Dmytro Kedyk撰写。内容从算法正确性证明、渐进记法、随机化算法与机器模型讲起，延伸到基础数据结构、内存管理、代码优化、递归控制、多算法选择及并行化，并穿插软件工程流程、测试与代码审查等实践主题；章末还给出课程建议、学习策略和项目练习。资源包仅含1个PDF文件，压缩包约485.74MB，适合按目录分块研读与查阅。当前已有185人学习，可作为理解算法权衡、优化实现和把理论落到C++代码中的参考。

1. 从一份慢三倍的哈希表说起

有位开发者拿着一份自己写的哈希表头文件来问：四十万键压测下来比标准库慢三倍，内存还多花四成。他要的不是再听一遍散列原理，而是能直接抄进工程的实现细节——容量取 2 的幂还是素数、装载因子到哪一步 rehash、删元素用墓碑还是整体重建。《Implementing Useful Algorithms in C++》正好是这种路子，它不陪你推公式，而是把 Vector、Treap、B+ 树、分支限界这些结构一段段写成能编译的 C++ 代码，再解释为什么这么写。这本书适合已经能写 C++、想补上数据结构与算法实现这一块的开发者；也适合带人 review 代码、需要一份参照实现的人。

2. 全书骨架：28 章的分层、目录结构与实现取向

2.1 从目录看分层：四个区块，读法完全不同

把目录摊开看，28 章不是平铺的算法清单，而是四层结构。第 1 到 4 章是背景层，讲算法该满足什么、怎么证明基本正确、渐进记法怎么用、随机化算法为什么值得单独拎出来，还夹了软件工程流程、职业建议和计算机法律这些“非技术但会绊倒人”的内容。第 5 到 12 章是容器与基础算法层，Vector、块数组、链表、位集、并查集、随机数生成器、排序、跳表、Treap、哈希表、二叉堆、图算法全在这一段，也是全书代码密度最高的地方。第 13 到 15 章转向系统侧，外存算法、字符串索引、压缩，处理的是内存装不下的数据和文本检索。第 16 到 28 章是数学与学习层，组合优化、大数、计算几何、纠错码、统计、数值矩阵、数值函数、数值优化，最后四章落在机器学习。

这个分层对二次开发很关键：容器层是拿来改的，数学层多数时候是拿来读的。下面这张表是我自己贴在书桌前的一张速查，按用途分类而不是按页码。

读的时候有个顺序建议：第 5 章和第 6 章连着读，因为后面所有容器和算法测试都要用到随机数；第 7 到 10 章可以按需跳，但第 11 章的图表示一定要看，它的邻接表写法会影响你对后面所有图算法的理解。

2.2 实现取向：模板、值语义、分配与构造分离

这本书的代码风格很统一，抓到三条就能预判它每个模块长什么样。第一是模板化，容器几乎都是template <typename T>，没有虚基类，不做运行时多态；第二是值语义，对象可拷贝可移动，迭代器就是裸指针或轻量包装；第三是把内存分配和对象构造拆成两步，这一点在第 5.2 节的工具函数里专门铺垫过，后面 Vector、块数组、自由链表都靠它。

按这个取向还原一个典型头文件的骨架，大概是这样：

// 按书里取向还原的容器骨架：模板 + 值语义 + 分配/构造分离 #pragma once #include <cassert> #include <cstddef> #include <new> #include <utility> template <typename T> class array_vector { public: using value_type = T; using iterator = T*; using const_iterator = const T*; array_vector() = default; explicit array_vector(std::size_t n) : size_(n), capacity_(n) { data_ = allocate(n); // 只拿原始内存，不构造 for (std::size_t i = 0; i < n; ++i) new (data_ + i) T(); // 逐个 placement new } ~array_vector() { destroy_and_free(); } // 拷贝构造、移动构造、赋值运算符按值语义补齐（三/五法则） array_vector(const array_vector& other) { copy_from(other); } array_vector(array_vector&& other) noexcept { steal_from(other); } T& operator[](std::size_t i) { assert(i < size_); // 边界检查只在 debug 生效 return data_[i]; } void push_back(const T& value) { if (size_ == capacity_) grow(capacity_ ? capacity_ * 2 : 4); new (data_ + size_) T(value); ++size_; } private: static T* allocate(std::size_t n) { return static_cast<T*>(::operator new(n * sizeof(T))); } void grow(std::size_t new_cap); // 扩容 + 搬移 + 释放旧块 void destroy_and_free(); T* data_ = nullptr; std::size_t size_ = 0; std::size_t capacity_ = 0; };

这段骨架的重点不在语法，在三个决策点。allocate只拿字节、不构造对象，是因为扩容时你需要把旧元素移动过去再统一析构，混在一起写就会出现“移动构造抛异常、旧块泄漏”的情况。operator[]用assert而不是抛异常，是因为容器在热路径上，release 版本必须零开销，越界属于调用方 bug。grow的容量翻倍策略直接决定后续所有基于 Vector 的容器性能——常见的做法是 1.5 到 2 倍之间，1.5 在长期运行的服务里更容易复用已释放的空闲块，2 在批处理里拷贝次数更少。我自己在写这层时会把增长因子做成模板参数，压测之后再定值，不预先拍脑袋。

2.3 目录结构怎么落到本地工程

书里的代码是按章节组织的单文件示例，直接平铺在一个目录里，几百个文件很快会乱。我的做法是按章号前缀建目录，把每个头文件按“一个数据结构一个文件”拆开，公共工具放common/：

# 按章节顺序落成本地工程，章号前缀保证文件排序和书里一致 algo_lab/ ├── common/ # 断言宏、计时器、随机种子工具 ├── 05_fundamental_ds/ # vector.h block_array.h bitset.h union_find.h ├── 06_random/ # xorshift.h mt19937.h mrg32k3a.h distributions.h ├── 07_sorting/ # insertion_sort.h quicksort.h mergesort.h selection.h ├── 08_sorted_sequences/ # skip_list.h treap.h trie.h ternary_trie.h ├── 09_hashing/ # hash_functions.h chaining_table.h probing_table.h bloom.h ├── 10_priority_queues/ # binary_heap.h indexed_heap.h ├── 11_graph/ # graph.h mst.h shortest_path.h flow.h matching.h ├── 12_misc/ # cache.h permutations.h primes.h ├── 13_external/ # io_model.h external_vector.h bplus_tree.h csv.h ├── 14_strings/ # pattern_search.h suffix_index.h regex.h ├── 15_compression/ # bit_stream.h huffman.h bwt.h ├── 16_optimization/ # branch_bound.h local_search.h annealing.h ├── 17_bignum/ # big_integer.h modular.h primality.h ├── 18_geometry/ # vp_tree.h kd_tree.h convex_hull.h ├── 19_ecc/ # galois_field.h reed_solomon.h ├── 21_statistics/ # bootstrap.h hypothesis_test.h ├── 22_numeric_matrix/ # lup.h cholesky.h qr.h svd.h sparse.h ├── 23_numeric_functions/ # fft.h interpolation.h ode.h ├── 24_numeric_optimization/ # line_search.h simplex.h ├── 25_ml/ # 分类、回归、聚类三个子目录 └── tests/ # 对拍脚本与暴力解参照实现

拆文件时会遇到一个绕不开的问题：书里的示例为了排版紧凑，经常把辅助函数直接定义在头文件里但不加inline，一旦被两个翻译单元包含就重定义。我在拆的时候统一给自由函数加inline，模板辅助函数放匿名命名空间，工具类改成只含静态成员的struct，这样基本不会再炸。目录建好之后，后面每写一个容器就配一个tests/下的对拍用例，这套习惯一直留到现在。

3. 底座落地：Vector、Union-find 与 Xorshift 随机数

3.1 动态数组的三个关键决策

第 5.3 节的 Vector 是全书的地基，后面块数组、链表、哈希表的桶数组、图算法的边数组全都从它派生。真正需要想清楚的是三件事：扩容时用拷贝还是移动、迭代器在扩容后是否失效、reserve和resize的语义边界。书里的取向是扩容一律走移动构造（std::move_if_noexcept那种保守写法留给需要强异常保证的场合），迭代器就是裸指针，扩容后必然失效——这一点它不打算用花哨的迭代器类去掩盖。

reserve(n)只改容量不改大小，resize(n)会构造或析构元素，这两个函数在书里的实现共用一个grow和shrink路径。我一般会把shrink做成显式调用而不是自动触发，因为自动缩容在反复增删的场景下会造成容量抖动，性能比不缩还差。这一条在书里没有强调，但凡是自己实现过动态数组的人都被它坑过一次。

3.2 用 xorshift32 起手：一个种子和三个移位量

第 6 章开头给的就是 xorshift，代码短到可以背下来。它的状态只有一个 32 位整数，三次移位异或完成一轮混合：

// 第 6.4 节的起手式：xorshift32，移位量 13/17/5 是经典参数组 struct xorshift32 { unsigned int state; // 种子不能为 0，否则状态永远停在 0 explicit xorshift32(unsigned int seed = 2463534242u) : state(seed) { if (state == 0) state = 2463534242u; } unsigned int next() { unsigned int x = state; x ^= x << 13; // 左移：把高位信息混到低位 x ^= x >> 17; // 右移：把低位信息混回高位 x ^= x << 5; // 再左移：扩散最后一轮 state = x; return x; } };

三个移位量不是随便填的，(13, 17, 5)是一组经过验证的全周期参数，周期为2^32 - 1。种子取 0 会让状态恒等于 0，这是最常见的翻车点，所以构造函数里要兜一下。这个生成器速度快到几乎没有开销，适合造测试数据和做蒙特卡洛采样，但它不是密码学安全的，状态可以被少量输出反推出来，别用在任何需要不可预测性的地方——这一点书里在第 6.3 节说得很明确。

书里紧接着给了 Mersenne Twister 和 MRG32k3a 两套更重的实现。选择逻辑大致是：只要速度、不在乎可预测性，用 xorshift；需要长周期和较好的统计性质，用 MT19937；需要多个独立流做并行模拟，用 MRG32k3a 的多分量结构。我在项目里通常是 xorshift 打底做单元测试，线上模拟换成 MT。

3.3 Union-find：路径压缩与按秩合并的组合拳

并查集在第 5.12 节，代码不到三十行，但它是后面 Kruskal 最小生成树和连通分量算法的基础。书里的写法是路径压缩加按秩合并，两者合用可以把均摊复杂度压到近似常数：

// 第 5.12 节：并查集，迭代版路径压缩 + 按秩合并 class union_find { public: explicit union_find(int n) : parent_(n), rank_(n, 0) { for (int i = 0; i < n; ++i) parent_[i] = i; } int find(int x) { // 路径减半：每走两步就把节点挂到祖父上，比递归压缩省栈 while (parent_[x] != x) { parent_[x] = parent_[parent_[x]]; x = parent_[x]; } return x; } // 返回 false 表示两个节点本来就在同一集合，Kruskal 靠这个跳过成环的边 bool unite(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (rank_[a] < rank_[b]) std::swap(a, b); parent_[b] = a; if (rank_[a] == rank_[b]) ++rank_[a]; return true; } private: std::vector<int> parent_; std::vector<int> rank_; };

find用迭代不用递归，是因为在“先大量合并再查询”的极端输入下递归深度可能达到几十万，栈直接爆掉。路径减半（parent_[x] = parent_[parent_[x]]）比完整的两遍路径压缩稍慢一点，但实现简单、常数小，实际跑起来差距在 5% 以内。unite的返回值很关键，它把“是否发生合并”这个信息暴露出来，后面 Kruskal 里可以写成一行if (uf.unite(u, v)) total += w;，成环的边自动被过滤，不需要额外判断。

3.4 有界离散分布：拒绝采样消除取模偏差

第 6.11 节讲有界区间离散分布采样，这是最容易被忽略、又最容易在统计类代码里引入系统性偏差的地方。直接用next() % n会让小数值出现得更频繁，因为2^32不能被n整除，余数区间的长度不一致：

// 第 6.11 节：区间 [0, n) 上的均匀采样，拒绝采样消除取模偏差 unsigned int uniform_bounded(xorshift32& rng, unsigned int n) { assert(n > 0); // (0u - n) % n 等于 2^32 % n，正好是落在余数区间里的取值个数 unsigned int threshold = (0u - n) % n; unsigned int r; do { r = rng.next(); } while (r < threshold); // 落在余数区间的样本直接丢弃重采 return r % n; }

threshold这个写法的妙处在于它不需要算2^32 - (2^32 % n)，直接用无符号整数减法溢出就得到了。循环里拒绝掉的概率小于n / 2^32，对常见规模（比如n是几百万）几乎没有额外开销，但在n接近2^31时会明显变慢，那种场景得换成更精细的位运算版本。书里第 6.12 节还给了正态分布、指数分布的采样，思路都一样：先用均匀分布打底，再做变换或拒绝。

4. 算法层落地：快排、线性探测哈希与图搜索

4.1 排序：小区间插入排序 + 三数取中快排

第 7 章的排序是全书最“工程化”的一章，因为它反复强调一件事：教科书上的快排和能上生产的快排差的不是算法，是一堆边界处理。书里的组合是入口先判断规模，小于阈值就走插入排序，否则用三数取中选枢轴，再用尾递归消除保证栈深度：

// 第 7.2、7.3 节：插入排序做小区间收尾，快排负责大区间划分 template <typename T> void insertion_sort(T* a, int n) { for (int i = 1; i < n; ++i) { T key = std::move(a[i]); int j = i - 1; while (j >= 0 && key < a[j]) { a[j + 1] = std::move(a[j]); // 移动而非拷贝，对字符串等类型差距明显 --j; } a[j + 1] = std::move(key); } } template <typename T> void quicksort(T* a, int n) { while (n > 16) { // 阈值 16 是书里给的参考值 int mid = n / 2; // 三个位置排序后把中位数换到 mid，首尾自然有序，减少无效划分 if (a[mid] < a[0]) std::swap(a[mid], a[0]); if (a[n - 1] < a[0]) std::swap(a[n - 1], a[0]); if (a[n - 1] < a[mid]) std::swap(a[n - 1], a[mid]); T pivot = a[mid]; int i = 0, j = n - 1; while (i <= j) { while (a[i] < pivot) ++i; while (pivot < a[j]) --j; if (i <= j) { std::swap(a[i], a[j]); ++i; --j; } } // 先递归小的那半，大的那半继续循环，栈深度压到 O(log n) quicksort(a, j + 1); a += i; n -= i; } insertion_sort(a, n); // 收尾 }

阈值的取法有讲究：16 是书里的建议，但在实际机器上 8 到 32 之间差别不大，关键是要有，不能一路递归到长度 1。先用插入排序收尾的好处是，小区间上快排的函数调用开销和划分开销超过了插入排序的平方级比较，实测能省 10% 到 20%。三数取中的三个if连续写，看起来笨，但它同时完成了两件事：把中位数放到mid，并让a[0]和a[n-1]初步就位，后续划分时这两个位置不用再检查边界，省掉了两个哨兵判断。

书里在第 7.5 节还给了整数专用排序（基数排序）和排列排序，用于键本身就是下标或者键值域很小的情况。这类场景下基数排序能比比较排序快三到五倍，但需要额外的计数数组，空间换时间，用之前得算清楚内存预算。

4.2 哈希表：线性探测的装载因子与墓碑

第 9 章把哈希表拆成两套实现：链式（9.8）和线性探测（9.9）。书里对线性探测的评价很直接——缓存友好，实际跑起来比链式快，前提是你把装载因子和删除处理做对。下面这段是核心结构：

// 第 9.9 节：线性探测哈希表，容量保持 2 的幂，取模换成位与 template <typename K, typename V> class probing_table { struct slot { K key; V value; bool used = false; // 该位置是否存过键 bool dead = false; // 墓碑：删过但探测链不能在这里断 }; public: V* find(const K& key) { std::size_t mask = slots_.size() - 1; std::size_t i = hash(key) & mask; while (slots_[i].used || slots_[i].dead) { if (slots_[i].used && slots_[i].key == key) return &slots_[i].value; i = (i + 1) & mask; // 线性探测：步长固定为 1 } return nullptr; // 走到空位说明不存在 } void erase(const K& key) { std::size_t mask = slots_.size() - 1; std::size_t i = hash(key) & mask; while (slots_[i].used || slots_[i].dead) { if (slots_[i].used && slots_[i].key == key) { slots_[i].used = false; slots_[i].dead = true; // 只打墓碑，不清探测链 --size_; ++dead_; if (dead_ > slots_.size() / 4) rehash(); // 墓碑过多就整体重建 return; } i = (i + 1) & mask; } } private: std::vector<slot> slots_; std::size_t size_ = 0; std::size_t dead_ = 0; std::size_t hash(const K& key) const; // 见第 9.3、9.4 节的函数选择 void rehash(); // 容量翻倍后重新插入所有有效键 };

三个参数直接决定性能。容量取 2 的幂，是为了把%换成&，在热路径上这一条能省掉整数除法的几十个周期。装载因子（size_ + dead_除以容量）书里建议控制在 0.7 以内，超过就 rehash，我一般设 0.5，因为线性探测在 0.7 以上时平均探测长度会陡增，缓存友好的优势会被抵消。墓碑数量单独设阈值（这里是容量的四分之一），是因为墓碑不占有效元素但会拖长探测链，长时间反复增删的表如果不重建，性能会一路下滑。

哈希函数本身在第 9.3 到 9.6 节铺了很长，从通用哈希到滚动哈希都有。书里的观点是：对整数键，乘法哈希（乘一个奇数再取高位）已经够用；对字符串键，别自己发明，直接用书里给的 rolling hash 或标准库的std::hash特化。自己拍脑袋写的哈希函数是性能玄学的主要来源，我见过太多“换了个哈希函数快了一倍”的案例，换回去就再也复现不了。

4.3 图表示：邻接表、MST 与最短路

第 11 章从图的表示讲起，这个选择会连锁影响后面所有算法。书里给的邻接表是“每个顶点一条出边数组”，边只存目标和权重：

// 第 11.3 节：邻接表表示，边结构只保留必要字段 struct edge { int to; double weight; }; using graph = std::vector<std::vector<edge>>; // 第 11.6 节：Kruskal 求最小生成树，边表排序 + 并查集判环 double mst_cost(std::vector<std::tuple<double, int, int>> edges, int n) { std::sort(edges.begin(), edges.end()); // 按权重升序 union_find uf(n); double total = 0.0; int picked = 0; for (const auto& [w, u, v] : edges) { if (uf.unite(u, v)) { // 合并成功才计入，成环的边自动跳过 total += w; if (++picked == n - 1) break; // 选够 n-1 条边提前结束 } } return total; } // 第 11.7 节：Dijkstra，用优先队列维护待扩展顶点 std::vector<double> dijkstra(const graph& g, int source) { const double inf = std::numeric_limits<double>::infinity(); std::vector<double> dist(g.size(), inf); using item = std::pair<double, int>; // (当前距离, 顶点编号) std::priority_queue<item, std::vector<item>, std::greater<item>> pq; dist[source] = 0.0; pq.push({0.0, source}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; // 过期条目直接丢弃 for (const edge& e : g[u]) { if (dist[u] + e.weight < dist[e.to]) { dist[e.to] = dist[u] + e.weight; pq.push({dist[e.to], e.to}); } } } return dist; }

Kruskal 这段的关键在unite的返回值，它把“这条边会不会成环”的判断压进了一次并查集操作，比先建图再 DFS 检测环简单得多。picked == n - 1的提前退出在稠密图上能省掉大量无效遍历。Dijkstra 里的if (d > dist[u]) continue;是标准做法，优先队列里会堆积同一个顶点的多个历史距离，不做这个判断就会重复扩展，复杂度退化成 O(V·E) 级别。书里在第 10.4 节专门给了索引堆，用它可以省掉优先队列里的重复条目，代价是实现复杂度上一个台阶——我在边数超过百万的图里会换成索引堆，普通规模没必要。

第 11 章后半部分还覆盖了最大流、二分匹配、稳定匹配和分配问题。稳定匹配那一节的代码异常短，二十来行就把 Gale-Shapley 写完了，这类结构简单但语义精巧的算法，正是这本书比起纯理论教材更好用的地方。

4.4 组合优化：分支限界、局部搜索怎么选

第 16 章是我认为最值得反复看的一章，因为它教的是“精确解拿不到时怎么办”。书里把手段分成三档：分支限界（16.6）不适合拿来做，适合做精确解，前提是你能写出一个足够紧的下界；局部搜索（16.8）实现成本最低，用在一个初始解上反复做邻域改进，比如旅行商问题里的 2-opt 交换；模拟退火（16.10）和迭代局部搜索（16.11）是在局部搜索上加“允许变差”的机制，用来跳出局部最优。

选择逻辑用一句话概括：问题规模在几十以内、需要保证最优，走分支限界；规模上千、只要一个足够好的解，走局部搜索；目标和约束都在变、解的形态不固定，走模拟退火或遗传算法。书里第 16.13 节给了一组性能结果，这些数字会随机器变化，但相对排序有参考价值。第 16.14 节讲问题特定预处理，往往比换算法更有效——比如在分配问题里先做一遍行最小值归约，能把搜索空间砍掉一个数量级。

5. 排查与避坑：编译、边界与性能的五类翻车

5.1 编译与工程类

现象一：把头文件拷进项目，链接期报一堆multiple definition。原因是书里为排版紧凑，很多自由函数直接定义在头文件里没有加inline，单个翻译单元能过，两个就撞。解决办法是给所有非模板自由函数加inline，辅助函数塞进匿名命名空间，纯工具类改成只含静态成员的struct。

现象二：模板容器编译通过，换个类型使用就报链接错误。原因是把模板成员函数的定义写进了.cpp，编译器在实例化时看不到定义。解决办法是把模板定义全部放回头文件，或者在.cpp末尾显式实例化你需要的那几个类型。后者能显著缩短编译时间，代价是新增类型时要手动加一行。

现象三：多次运行程序，随机数序列完全一样。原因是种子取了time(0)的秒级时间戳，同一秒内启动必然重复。常见做法是把高精度时钟的纳秒部分和进程 ID 混一下，再喂给 xorshift 的构造函数；做可复现实验时反过来，把种子固定成常量打到日志里，出问题能原样重跑。

5.2 语义与边界类

现象四：线性探测哈希表删了几个键之后，原本能查到的键查不到了。原因是删除时把used直接置 false，探测链在这里断掉，后面的键再也走不过来。解决办法就是 4.2 里写的墓碑方案：删除只打dead标记，查找时把dead位置当作“可以继续走”，同时统计墓碑数量，超过容量四分之一就整体 rehash 重建。这个坑我在两个不同项目里各踩过一次，第二次是因为换了语言后忘了墓碑这回事。

现象五：并查集在百万级数据上跑着跑着栈溢出。原因是find写成了递归版，输入又是“先构造一条长链、再连续查询”的构造数据，路径压缩还没来得及生效，递归深度先到了几十万。解决办法是改成迭代版路径减半（3.3 里那段），或者退一步用两遍循环做完整路径压缩，栈上只留一个临时变量。

现象六：快排处理已经有序的数组时退化成 O(n²)，跑几分钟不出结果。原因是枢轴固定取首元素，有序输入下每次划分都只减少一个元素。解决办法是三数取中加小区间插入排序，再做尾递归消除，这三件事必须一起做，只做前两件在特定输入下仍会退化。

提示：这五类问题里，编译类的那三条在拆书里的代码时几乎百分之百会遇到，建议一开始就把inline和模板定义位置当成硬规矩，别等报错再回头改。

6. 二次开发：把书里的模块摘进自己工程

我自己把书里的代码往工程里搬，有一套固定流程。第一步是定接口边界：如果模块是容器，先想清楚它要不要暴露迭代器、迭代器在修改后是否失效、容量语义怎么定；如果是算法，就把“输入什么、输出什么、失败怎么表示”写成三行注释放在头文件顶部，再动手改。接口没定就改代码，十有八九会改出一个既不像书里也不像工程的四不像。

第二步是写对拍脚本，这一步不能省。拿一个暴力解当参照，随机生成小规模输入，两边跑，比对输出。下面这个脚本是我常用的模板，生成随机图、跑两份实现、递归对比结果：

#!/usr/bin/env bash # 对拍：暴力解 vs 书里摘出来的实现，小规模随机输入 set -euo pipefail g++ -O2 -std=c++17 -o ref tests/mst_bruteforce.cpp # 暴力解参照 g++ -O2 -std=c++17 -o fast tests/mst_kruskal.cpp # 摘出来的实现 for i in $(seq 1 500); do # 生成 2 到 30 个顶点的随机连通图，权重 1 到 100 python3 tests/gen_graph.py --nodes $((RANDOM % 29 + 2)) --seed "$i" > /tmp/case.txt ./ref < /tmp/case.txt > /tmp/out_ref.txt ./fast < /tmp/case.txt > /tmp/out_fast.txt if ! diff -q /tmp/out_ref.txt /tmp/out_fast.txt > /dev/null; then echo "case $i 不一致，输入保留在 /tmp/case.txt" exit 1 fi done echo "500 组全部通过"

第三步才是性能验证。我一般分两轮：先全部关掉优化（-O0）跑一遍，确认正确性；再开-O2跑基准，记录中位数而不是平均值，因为单次抖动在容器类代码里很常见。基准测试的输入规模从一万到一千万分档，每档重复二十次取中位数，这样能看清哪个规模区间开始出现缓存未命中导致的性能拐点。

下面是几个模块的改造取舍，是我自己踩过之后总结的：

| 模块 | 改造成本 | 建议 | | Vector、并查集 | 低 | 直接搬，改命名空间即可，注意扩容因子按场景调 | | 线性探测哈希表 | 中 | 值得搬，但哈希函数别自己写，用标准库的 | | Treap、跳表 | 中 | 有std::map能覆盖时不必搬，需要可持久化或特殊增强时再上 | | B+ 树 | 高 | 只有数据确实放不进内存才考虑，否则用现成的嵌入式库 | | 分支限界、局部搜索 | 中高 | 直接搬框架，问题特定的下界和邻域操作必须自己写 |

书上给的代码是教学性质的，边界检查和错误分支经常是断言了事，搬进工程必须补上真实的错误处理。这一点我吃过亏：有次直接把书里一段堆实现拿去用在调度器里，空堆时top()的行为是未定义，线上偶发返回垃圾值，排查了两天才定位到。

从那以后我每次把书里的代码搬进工程，都会先写一个两百行左右的对拍脚本，把随机输入和暴力解对一遍，再补三条边界用例（空输入、单元素、超大规模），最后才敢合并。这套流程慢，但比事后查线上问题快得多。希望帮到你。

本文还有配套的精品资源，点击获取