简介：《Implementing Useful Algorithms in C++》是 Dmytro Kedyk 编写的 C++ 算法实践指南，面向希望系统提升算法设计、实现与优化能力的中高级开发者及计算机专业学生。全书从算法正确性证明、渐进记法、机器模型与随机化算法讲起，延伸至数据类型选择、内存管理、代码优化、递归控制、多算法取舍与并行化，并穿插软件工程周期、测试审查、职业面试与法律常识等实用主题，目录还覆盖基础数据结构等模块。资源包为单一 PDF 文件，压缩包约 485.74MB，便于离线阅读与长期查阅。已有 185 人学习下载。读者可从中获得从基础数据结构到工程化实现的完整知识框架，并借助章节末推荐课程、学习策略、项目实践与参考资料继续深入，适合作为算法课程辅助读本和工程实践参考手册。

1. 一份把算法写成能编译代码的 C++ 实战底稿

去年做跨平台数据清洗工具时，我需要自己实现一套按时间窗口淘汰的哈希表和稳定排序。翻了几本算法书，内容全是伪代码加复杂度推导，真正写成 C++ 后，内存管理和边界条件仍得自己补，调试只能靠反复试。后来读到《Implementing Useful Algorithms in C++》这份 PDF，看到第 5 章讲 Vector 的 reserve 与 resize 差在哪里，我才明白差距不在算法本身，而在“算法怎么被写成一段能复用的代码”。全书 24 章，从数据结构实现细节、xorshift 这类随机数生成器，到排序、哈希、图算法、字符串、压缩、纠错码，再到数值方法与机器学习，每章末尾都带 Implementation Notes 和 Projects。适合会写 C++、但没系统写过算法库的人。

2. 目录地图：24 章怎么从正确性证明一路铺到矩阵分解

拿到这份 PDF 后，先别从第 1 页开始逐页阅读。全书 24 章、900 多页，前四章不讲具体算法，后面的章节又层层依赖。正确做法是按依赖关系挑读，而不是按页码顺序硬啃。下面按章节结构拆开讲。

2.1 前四章不是算法，是写算法之前要先立好的规矩

第 1 章 Background 覆盖算法正确性证明、渐进记法、机器模型、随机化算法、效率测量、数据类型、内存管理、代码优化、递归、并行化。这些内容看起来像科普，但恰恰是后面所有章节的约定来源。

比如 1.9 节讨论数据类型时，先分析int在 32 位和 64 位下的位宽差异，再讨论索引类型只能选择size_t还是int。1.11 内存管理讲动态分配与释放的配对，也讲为什么算法库里要尽量避免new和delete散落在各处。1.12 代码优化讲的顺序是先用 profiler 定位热点，再考虑缓存友好性；如果两者颠倒，优化会白费。这些细节直接决定你抄下来的算法能不能用。

第 2 章把软件工程压缩成 14 节，从需求、组件结构设计、编码、模式、错误管理、测试、评审到发布维护。第 3 章讲求职与面试，第 4 章讲知识产权与许可。如果只想跑代码，第 3、4 章可以先跳过；但第 2 章的 2.7 错误管理和 2.8 测试值得提前读，后面每一章的算法在出错时，靠的就是这两节的约定。

2.2 中段十六章：一条有强依赖关系的算法主干道

第 5 章到第 20 章是主线，顺序不是随意排列的。第 5 章讲五个基础结构：Vector、Block Array、Linked List、Free List、Stack、Queue，再补树、位算法、Bit Set、union-find。第 6 章随机数立刻接上，因为后面排序测试、跳表层级、蒙特卡洛方法、随机图生成都要用生成器。第 7 章排序，第 8 章动态有序序列（跳表、treap、trie、三元 treap trie），第 9 章哈希，第 10 章优先队列，第 11 章图算法。

这个顺序不能乱跳。第 8 章的 treap 依赖第 5 章的 Vector 和迭代器约定；第 11 章的最小生成树依赖第 5 章的 union-find，最短路径依赖第 10 章的索引堆。跳过后面任意一环，代码都编译不过。

再往后是 12 杂项（静态转动态、持久化、缓存、生成排列组合）、13 外存算法（CSV、B+ 树、外存排序）、14 字符串（单模式搜索、正则、后缀索引、语法树）、15 压缩（Huffman、字典压缩、BWT、MTF）、16 组合优化（分支定界、局部搜索、模拟退火、遗传算法）、17 大数、18 计算几何（k-d 树、凸包、平面扫描）、19 纠错码（有限域、Reed-Solomon、LDPC）、20 密码学。这部分是“按需选读”区，做文本处理先看 14、15，做空间索引先看 18。

2.3 后四章：数值、统计、机器学习的自下而上铺法

第 21 到 28 章是第二个体系。21 计算统计讲估计量、置信区间、bootstrap、假设检验；22 矩阵代数讲浮点误差、LUP、Cholesky、QR、SVD、稀疏矩阵迭代法；23 函数运算讲 FFT、插值、积分、求根、ODE；24 数值优化讲线搜索、坐标下降、模拟退火、线性规划；25 到 28 才是机器学习，依次是通用、分类、回归、聚类。

这套排列有说法。SVM 要解二次规划，所以 26 章 SVM 放在 24 章优化之后；PCA 要 SVD，所以降维内容不会出现在 22 章之前。阅读顺序要倒着看依赖，而不是顺着写。

2.4 三段式结尾：Implementation Notes 才是真正该先读的部分

每一章末尾固定的三段是 Implementation Notes、Comments、Projects。我的习惯是先翻 Implementation Notes：会用一张表对比本章几种实现在不同数据规模下的表现，写清哪种该用、哪种只在特定约束下才用。比如第 9 章哈希的 Implementation Notes 直接给链式与线性探测的耗时对比，第 10 章索引堆会告诉你什么时候普通二叉堆加惰性删除就够、什么时候必须上索引。Comments 说明本章的内容边界，Projects 是动手题。

摸清这张地图后，剩下的工作是挑一条线真正跑通，下一章从最底层的基础结构动手。

3. 基础层拆解：一个 Xorshift 随机数背后的工程约定

第 5 章到第 7 章是全书的底座。很多人看算法书会跳过随机数和容器，直接从快排开始抄，结果后面图算法、跳表、测试数据生成全都卡住。这里按“随机数 → 容器 → 数据结构 → 排序”的顺序，把能直接复用的部分拆开。

3.1 Xorshift32：默认参数里藏着一个大坑

原书 6.4 节的 xorshift 是全书最短的一段代码，也是最容易被抄错的一段。核心就是三次移位异或，但状态初值、位移量、种子来源三个地方都有讲究。

#include <cstdint> // 书 6.4 节 xorshift32：状态只有 32 位，周期 2^32 - 1 struct XorShift32 { std::uint32_t s; // 种子不能为 0，否则移位异或永远停在 0 explicit XorShift32(std::uint32_t seed = 2463534242u) : s(seed ? seed : 0x9e3779b9u) {} std::uint32_t next() { s ^= s << 13; // 左移 13 位后异或回状态 s ^= s >> 17; // 右移 17 位 s ^= s << 5; // 左移 5 位 return s; } // [0, n) 上的均匀整数，用拒绝采样消掉取模偏差 std::uint32_t bounded(std::uint32_t n) { std::uint32_t limit = UINT32_MAX - (UINT32_MAX % n) - 1; std::uint32_t r; do { r = next(); } while (r > limit); return r % n; } };

逻辑说明：13/17/5是 Marsaglia 给出的一组移位三元组，并非随意选择。换一组参数，周期会掉到 2 的几千次方甚至更小。三个移位量必须满足左移、右移、左移的交替，否则低位会退化。bounded里先用UINT32_MAX % n算出不能整除的余数部分，再拒绝采样，这比直接next() % n均匀，做法和第 6.11 节讲有界离散分布采样时一致。

参数说明：种子默认值给的是一个非零常数，不建议用time(0)直接作为默认参数。原因很简单，同一秒内构造若干个生成器，它们的状态会完全一样，随机化测试时会看到“随机”结果每次都相同，很容易误判成算法有 bug。要真正的熵源，就显式传std::random_device{}()进去，别把时间当默认值。

3.2 Vector：size 与 capacity 分开才撑得住后面的所有结构

第 5.3 节的 Vector 是全书出现频率最高的组件，跳表、哈希表、优先队列、图邻接表全都建在它上面。这个容器最关键的设计是让 size 和 capacity 分开管理；元素构造与内存分配分离，只在这一步处理。简化版如下。

#include <cstddef> #include <new> #include <utility> template <class T> class Vector { public: Vector() = default; ~Vector() { destroy_all(); ::operator delete(data_); } std::size_t size() const { return size_; } std::size_t capacity() const { return cap_; } T& operator[](std::size_t i) { return data_[i]; } // 容量只增不减，避免 push_back 反复扩容抖动 void reserve(std::size_t n) { if (n <= cap_) return; T* p = static_cast<T*>(::operator new(n * sizeof(T))); for (std::size_t i = 0; i < size_; ++i) new (p + i) T(std::move(data_[i])); // 只要求可移动 destroy_all(); ::operator delete(data_); data_ = p; cap_ = n; } void push_back(const T& v) { if (size_ == cap_) reserve(cap_ ? cap_ * 2 : 8); new (data_ + size_) T(v); // 原地构造，不赋值 ++size_; } // 变大补默认构造，变小析构尾部元素 void resize(std::size_t n) { if (n > size_) { reserve(n); for (; size_ < n; ++size_) new (data_ + size_) T(); } else { for (std::size_t i = n; i < size_; ++i) data_[i].~T(); size_ = n; } } private: void destroy_all() { for (std::size_t i = 0; i < size_; ++i) data_[i].~T(); size_ = 0; } T* data_ = nullptr; std::size_t size_ = 0, cap_ = 0; };

逻辑说明：这里用::operator new分配原始内存，再用 placement new 在内存上构造对象，把“分配”和“构造”拆成两步。好处是reserve扩容时不必要求 T 可拷贝，只需要可移动；resize缩小时也能准确控制析构时机。如果直接用new T[n]，那么即使只用了 3 个元素，也会构造 n 个对象，Hash 表扩容时代价会非常大。

参数说明：增长因子取 2 是常见的折中，用 1.5 可以让内存复用更充分，但扩容次数会变多。cap_ ? cap_ * 2 : 8里的 8 是初始容量，别设成 1，否则前几次push_back会连续扩容。

3.3 BitSet 与 union-find：两百行以内，复用率最高

第 5.11 节的 BitSet 用std::uint64_t数组按位存，第 5.12 节的 union-find 用路径减半加按秩合并。两段都不长，但第 11 章图算法里几乎每个都用到。

#include <vector> #include <cstddef> class UnionFind { public: explicit UnionFind(std::size_t n) : parent_(n), rank_(n, 0) { for (std::size_t i = 0; i < n; ++i) parent_[i] = i; } std::size_t find(std::size_t x) { while (parent_[x] != x) { parent_[x] = parent_[parent_[x]]; // 路径减半，压一层就够 x = parent_[x]; } return x; } // 合并成功返回 true，已在同一集合返回 false bool unite(std::size_t a, std::size_t 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<std::size_t> parent_, rank_; };

逻辑说明：find用路径减半，把查找路径上每个节点都直接指向祖父节点，单次复杂度可以视为近似常数，也比完全路径压缩的递归写法省栈。unite用按秩合并保证树高不失控，两者结合后的复杂度是反阿克曼函数。

参数说明：rank_可以换成按 size 合并，效果接近，索引从 0 开始时用 rank 更直观。用int存索引在这里不如size_t稳妥，图节点数超过 20 亿时int会溢出。

3.4 排序组合拳：快排只负责粗分，收尾交给插入排序

第 7 章的排序部分明确反对“一个快排走天下”。实际做法是三数取中选轴，递归到小区间就切换到插入排序，因为小区间上插入排序常数更小。

template <class T> void insertion_sort(T* a, int lo, int hi) { for (int i = lo + 1; i < hi; ++i) { T key = std::move(a[i]); int j = i - 1; while (j >= lo && key < a[j]) { a[j + 1] = std::move(a[j]); --j; } a[j + 1] = std::move(key); } } template <class T> void quick_sort(T* a, int lo, int hi) { while (hi - lo > 16) { // 小区间不递归 int mid = lo + (hi - lo) / 2; if (a[mid] < a[lo]) std::swap(a[mid], a[lo]); // 三数取中 if (a[hi - 1] < a[lo]) std::swap(a[hi - 1], a[lo]); if (a[hi - 1] < a[mid]) std::swap(a[hi - 1], a[mid]); std::swap(a[mid], a[hi - 1]); T pivot = a[hi - 1]; int i = lo, j = hi - 1; for (;;) { while (a[++i] < pivot) {} while (pivot < a[--j]) {} if (i >= j) break; std::swap(a[i], a[j]); } std::swap(a[i], a[hi - 1]); quick_sort(a, lo, i); // 先递归小的那头 lo = i + 1; // 大的那头用循环，省栈 } insertion_sort(a, lo, hi); }

逻辑说明：三数取中把轴值拉到中间，避免对已排序数组退化；循环里先递归较短的一侧，较长的一侧改成尾递归形式的手写循环，栈深度被压到 O(log n)。最后整段交给插入排序，hi - lo <= 16这个阈值是根据实测调出来的，8 到 32 之间差别不大。

参数说明：insertion_sort的 lo/hi 是左闭右开区间，和std::sort一致，方便对照测试。把16改成更大值会让快排递归更浅，但插入排序本身是 O(n²)，超过 64 之后整体会变慢。

把这三段跑通并写一个乱序数据的对拍测试，基础层就算立住了，后面的跳表、哈希、图算法才有地方站。

4. 图算法与哈希表：从最小生成树到线性探测的取舍

第 9 章哈希和第 11 章图算法是这本书最像“工程手册”的两章。两章都给了两种以上实现，并附实测数据，让读者自己权衡。这一章按“表示方式 → 具体算法 → 底层容器”的顺序拆。

4.1 图表示：邻接表还是边表，决定了后面所有算法的写法

第 11.3 节把图的表示分成邻接矩阵、邻接表、边表三种，没有说哪种更好，而是给出各自适合的场景。稠密图用矩阵，稀疏图的搜索用邻接表，最小生成树用边表，因为 Kruskal 需要把所有边排序。

实际工程里常见的做法是用邻接表建图，再额外维护一个边列表给 Kruskal 用，两份数据共享同一套顶点下标。

struct Edge { int u, v; double w; }; // 邻接表：搜索与最短路使用；w 为边权 using Graph = std::vector<std::vector<std::pair<int, double>>>; // 从邻接表导出边表，供 Kruskal 使用 std::vector<Edge> to_edge_list(const Graph& g) { std::vector<Edge> edges; for (int u = 0; u < static_cast<int>(g.size()); ++u) for (const auto& [v, w] : g[u]) if (u < v) edges.push_back({u, v, w}); // 无向图去重 return edges; }

逻辑说明：邻接表里每条无向边会存两次，u < v是去重条件，漏掉它会导致 Kruskal 里同一条边被判断两次，虽然并查集会挡掉第二次，但边表规模翻倍、排序变慢。这个细节书里写在实现注释里，抄代码时很容易丢。

参数说明：w用double是为了兼容最短路径里的正实数权重，纯整数权重可以换成int，比较更快。

4.2 Kruskal 与并查集：二十行的最小生成树

第 11.6 节讲最小生成树，Kruskal 和 Prim 各有实现。Kruskal 的代码极短，关键在边排序和并查集。

#include <algorithm> #include <vector> // 返回 MST 总权重；图不连通时返回 -1 double kruskal(int n, std::vector<Edge> edges) { std::sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.w < b.w; }); UnionFind uf(n); double total = 0.0; int used = 0; for (const auto& e : edges) { if (uf.unite(e.u, e.v)) { // 不成环才加入 total += e.w; if (++used == n - 1) break; // 已够 n-1 条边，提前收工 } } return used == n - 1 ? total : -1.0; }

逻辑说明：按权重升序扫描边，并查集负责判断加入这条边会不会成环。used == n - 1提前退出很关键，稀疏图上能省掉后面一大段扫描。返回 -1 而不是抛异常，是因为调用方通常需要区分“图不连通”和“权重计算结果为负”两种情况。

参数说明：n是顶点数，edges是去重后的边表。权重相等时排序结果不唯一，但 MST 总权重唯一，所以对拍测试应该比较总权重而不是边集。

4.3 线性探测哈希表：删除为什么必须留“墓碑”

第 9 章先给链式哈希，再给线性探测。链式实现简单，但节点头开销大；线性探测缓存友好，代价是删除麻烦。

template <class K, class V> class LinearProbeMap { enum State : unsigned char { EMPTY, USED, DELETED }; struct Slot { K key{}; V val{}; State st = EMPTY; }; public: explicit LinearProbeMap(std::size_t cap = 16) : slots_(cap) {} V* find(const K& key) { std::size_t i = hash(key) % slots_.size(); for (std::size_t n = 0; n < slots_.size(); ++n) { Slot& s = slots_[i]; if (s.st == EMPTY) return nullptr; // 探测链断了 if (s.st == USED && s.key == key) return &s.val; i = (i + 1) % slots_.size(); } return nullptr; } void insert(const K& key, const V& val) { if ((used_ + deleted_ + 1) * 4 > slots_.size() * 3) rehash(); // 负载 0.75 std::size_t i = probe_for_insert(key); Slot& s = slots_[i]; if (s.st != USED) ++used_; else --deleted_; s.key = key; s.val = val; s.st = USED; } bool erase(const K& key) { V* p = find(key); if (!p) return false; std::size_t i = hash(key) % slots_.size(); while (!(slots_[i].st == USED && slots_[i].key == key)) i = (i + 1) % slots_.size(); slots_[i].st = DELETED; // 打墓碑，不能直接置 EMPTY --used_; ++deleted_; return true; } private: std::size_t probe_for_insert(const K& key) { std::size_t i = hash(key) % slots_.size(); std::size_t first_deleted = slots_.size(); for (std::size_t n = 0; n < slots_.size(); ++n) { Slot& s = slots_[i]; if (s.st == EMPTY) return first_deleted != slots_.size() ? first_deleted : i; if (s.st == DELETED && first_deleted == slots_.size()) first_deleted = i; else if (s.st == USED && s.key == key) return i; i = (i + 1) % slots_.size(); } return first_deleted; } std::size_t hash(const K& key) { return std::hash<K>{}(key); } void rehash() { /* 扩容到 2 倍，重新插入所有 USED 槽位 */ } std::vector<Slot> slots_; std::size_t used_ = 0, deleted_ = 0; };

逻辑说明：find遇到 EMPTY 才能停，遇到 DELETED 必须继续往后走，否则删除一个元素会把它后面的整条探测链切断。erase打墓碑而不是置空，就是为了保住这条链。probe_for_insert里要记住第一个墓碑位置，这样插入可以复用墓碑槽，避免表越用越空、墓碑越来越多。

参数说明：负载因子设 0.75 是线性探测的经验值，超过这个值探测长度会明显变长；deleted_单独计数，是因为墓碑占位置但不存数据，重哈希的触发条件必须把两者加起来算。

4.4 优先队列与 Dijkstra：索引堆和惰性删除怎么选

第 10 章给了普通二叉堆和索引堆两套。索引堆支持change(i, key)，用来实现 Dijkstra 的 decrease-key；普通堆只能重复入堆，靠出堆时判断过期。第 10.4 节的索引堆用pos_数组记录每个元素在堆里的下标，堆内交换时同步更新。

工程里更常用的是惰性删除版本，代码短、常数小，边数不是特别大时性能够用。

#include <queue> #include <limits> std::vector<double> dijkstra(const Graph& g, int src) { const double INF = std::numeric_limits<double>::infinity(); std::vector<double> dist(g.size(), INF); using P = std::pair<double, int>; // (距离, 顶点) std::priority_queue<P, std::vector<P>, std::greater<P>> pq; dist[src] = 0.0; pq.push({0.0, src}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; // 陈旧条目，直接丢弃 for (const auto& [v, w] : g[u]) { if (dist[u] + w < dist[v] - 1e-12) { // 浮点比较留余量 dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } return dist; }

逻辑说明：d > dist[u]这一行是惰性删除的核心：同一个顶点可能被压入堆很多次，只有距离最小的那次是有效的。第 10 章的索引堆则把“判断过期”省掉，直接修改堆内元素，堆里永远只有 n 个条目。两种写法在 m 远大于 n 的稠密图上差别明显。

参数说明：1e-12的容差是为了避免浮点误差导致的无穷松弛循环，书里第 22 章讨论浮点误差时也强调过，最短路径里不能用严格的<。图规模超过百万边时，priority_queue的vector底层会频繁扩容，可以提前reserve。

5. 避坑记录：从上手到跑通最容易翻车的五个点

这份 PDF 是书稿排版稿，代码片段分散在各章正文和 Implementation Notes 里，不是完整的可编译工程。按书里的思路自己搭工程时，下面五个问题几乎是一定会遇到的。

5.1 编译与工程层面的两个坑

第一，整本书大量使用模板，但实现注释里的辅助函数是普通函数。直接把这些函数放进头文件，然后 被两个.cpp包含，链接时会报multiple definition。

现象：编译通过，链接阶段报duplicate symbol，报的符号名看着陌生。

原因：书里为了排版简洁，把一些非模板辅助函数（比如位运算工具、打印函数、计时器）单独写出来，没有标inline，而读者往往会图省事把它们和其他代码一起塞进头文件。

解决：非模板函数一律加inline，或者拆到.cpp里只留声明。模板函数本身有隐式 inline 语义，不受影响。再省事一点就整体用namespace { }包起来给内部链接，但那样每个编译单元都会生成一份副本，别在头文件里这么干。

第二，开了优化之后浮点结果和书里的数字对不上。

现象：同一段矩阵分解代码，-O0下残差是1e-15，-O2之后变成1e-13，对拍测试大面积失败。

原因：编译器把中间结果保留在更高精度的寄存器里，或者把乘加合并成 FMA 指令，累加顺序和源码不一致。如果还加了-ffast-math，连NaN和Inf的语义都可能变。

解决：数值章节的代码固定用-std=c++17，关掉-ffast-math，比较时用相对误差而不是绝对相等。书里第 22.3 节专门讨论过浮点误差来源，测试阈值按那里的思路设。

5.2 算法使用层面的三个坑

第三，快排在某些输入上退化成 O(n²)。

现象：随机数据排序 100 万元素用 0.1 秒，换成已经有序的数据直接卡到十几秒。

原因：固定选首元素或尾元素做轴，有序输入下每次划分都只能砍掉一个元素，递归深度变成 n。

解决：按第 7.3 节的做法三数取中，小区间切插入排序，递归时先处理较短的一侧。三件事缺一件都可能在特定输入上翻车，我最早只做了三数取中，遇到大量重复元素时还是慢，后来补上小区间切换才稳定。

第四，线性探测哈希表删除后查不到后面的元素。

现象：插入 a、b、c，删掉 b，再查 c 返回nullptr。

原因：删除时把槽位置成 EMPTY，查找时遇到 EMPTY 就认为探测链断了，而 c 恰好被哈希到 b 后面。

解决：留墓碑，把删除标记和空槽分成两种状态，find遇到墓碑继续走，insert优先复用第一个墓碑。墓碑累积到一定比例就整体重哈希。

第五，Dijkstra 算出来的距离比正确答案大。

现象：小图上结果正确，换成带环的图之后某些点的距离明显偏大。

原因：用了普通二叉堆又想让距离变小时直接修改数组里的值，堆里的顺序没更新，出堆顺序就乱了。

解决：要么用第 10.4 节的索引堆维护pos_映射，要么用上面那段惰性删除，重复入堆、出堆时判过期。前者省内存，后者代码短，别试图在普通堆上手动改元素。

6. 二次开发：把这些算法接进自己的工程

真要把这本书里的代码搬进项目，我的做法是先做一次“最小可用移植”，再谈优化。第一步挑一个章节，把它依赖的基础结构一起拷过来，比如要图算法就一起拷 Vector、union-find、二叉堆、边排序，别只拷kruskal函数本身。第二步，按书里的 API 约定把接口对齐，优先队列统一成push/pop/top/empty，容器统一成左闭右开区间，后面替换实现时调用方不用改。第三步，写对拍测试，用小规模随机数据把新实现和标准库对应物比较。

#include <algorithm> #include <cassert> #include <random> #include <vector> // 与 std::sort 对拍：随机数据 + 边界数据各跑一遍 void verify_sort() { std::mt19937 rng(12345); for (int trial = 0; trial < 200; ++trial) { int n = 1 + static_cast<int>(rng() % 500); std::vector<int> a(n); for (auto& x : a) x = static_cast<int>(rng() % 1000); std::vector<int> b = a; // 留一份给标准库 quick_sort(a.data(), 0, n); std::sort(b.begin(), b.end()); assert(a == b); // 边界：全相同、已升序、已降序 std::vector<int> same(n, 7), up(n), down(n); for (int i = 0; i < n; ++i) { up[i] = i; down[i] = n - i; } for (auto* v : {&same, &up, &down}) { auto expect = *v; std::sort(expect.begin(), expect.end()); quick_sort(v->data(), 0, n); assert(*v == expect); } } }

这段对拍的价值在于边界数据，随机数据只能验出明显错误。全相同元素测轴选择，已排序测退化，降序测划分边界。我当时只跑随机数据，上线后遇到一批几乎有序的日志时间戳，直接用性能问题暴露了。

另一个技巧是把书里每章的 Implementation Notes 抄成一张选型表放在工程 wiki 里，写明数据结构、适用规模、最坏复杂度、我这边实测的阈值。下次有人问“为什么不用std::unordered_map”，表里直接有答案：链式哈希在小键值、频繁删除的场景下节点开销大，线性探测在负载 0.75 以内更快，但墓碑处理不当会翻车。

从那以后，我每次从书里、从别人的仓库里搬算法代码，都强制先跑一遍对拍和边界用例，再合进主干。省下来的调试时间远比写测试的时间多。希望帮到你。

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