C++算法模板库：从设计到实战的完整指南

简介这是一份面向竞赛编程与算法学习者的C算法模板库聚焦在有限时间内快速调用经过优化的常用算法与数据结构解决大规模数据与高性能计算场景下的实现难题。压缩包共127个文件以123个cpp源码为主体另含2个md说明、1个tex与1个pdf文档整体约730KB体量轻便、便于随取随用。内容覆盖基础算法中的双指针、离散化、前缀和与差分、二分查找、单调栈与单调队列、尺取法、树的中心、拓扑排序数学部分包含素数筛法、质因数分解、欧拉函数、组合数、扩展欧几里得、线性同余方程、容斥原理、高斯消元、矩阵乘法、莫比乌斯反演、BSGS与FFT数据结构涉及并查集、Sparse Table、Trie、树状数组、线段树、树链剖分、可持久化线段树与莫队图论则涵盖Floyd、BellmanFord、SPFA、Dijkstra、分层图最短路、差分约束、最小生成树、LCA、二分图匹配、强连通分量与2SAT等。已有76人学习适合希望系统整理模板、快速查漏补缺的选手参考。1. 算法模板库到底解决什么问题从一道单调栈题说起刷题刷到一定阶段你会发现一个尴尬的事实每道题的解法你好像都见过但真到写的时候二分边界又调了十分钟并查集的路径压缩又忘了写快速幂的取模又溢出了。这不是你笨而是算法竞赛和面试准备本身就有一套「重复造轮子」的损耗。基于 C 的算法模板库本质上就是把这套损耗一次性干掉——把二分、并查集、线段树、单调栈、快速幂、图论最短路这些高频结构提前写成经过验证的、接口统一的头文件比赛或面试时直接调用。这个方向适合三类人一是准备 C 面试、需要快速手写八股的求职者二是打算法竞赛、追求编码速度的选手三是想把算法能力沉淀成个人资产、而不是每次从零推导的工程师。标题里的「源码」两个字很关键——它不是让你背模板而是让你拥有一套可以编译、可以改、可以按自己习惯重构的代码库。接下来我会按「怎么组织这套库 → 每个模块怎么写 → 怎么验证 → 坑在哪」的顺序把这件事讲透。2. 模板库的目录结构与编译方式别把所有代码塞进一个 main.cpp2.1 为什么模板库要按「数据结构 / 图论 / 数学 / 字符串」分目录很多人第一次攒模板习惯把所有函数写在一个template.cpp里用的时候整段复制。这个做法在只有十几个模板时还能忍一旦超过三十个找起来就是灾难而且不同模板之间的宏定义、类型别名会互相污染。常见做法是按算法领域拆成独立头文件每个头文件自包含只依赖标准库不依赖其他模板。这样你在比赛时只需要#include segtree.hpp不会因为引入一个二分而带进一堆无关代码。我一般会这样组织目录algo-template/ ├── include/ │ ├── ds/ # 数据结构 │ │ ├── dsu.hpp │ │ ├── segtree.hpp │ │ └── monotonic_stack.hpp │ ├── graph/ # 图论 │ │ ├── dijkstra.hpp │ │ └── topo_sort.hpp │ ├── math/ # 数学 │ │ ├── fast_pow.hpp │ │ └── gcd_lcm.hpp │ └── string/ # 字符串 │ └── kmp.hpp ├── tests/ # 每个模板对应的验证用例 │ ├── test_dsu.cpp │ └── test_segtree.cpp └── CMakeLists.txt这个结构的好处是每个.hpp可以单独编译测试tests/目录保证你改完模板后能立刻验证没写崩。CMakeLists 只负责把 tests 编译成可执行文件模板本身是 header-only不需要单独编译成库。2.2 用 CMake 把模板库跑起来的最小配置header-only 库的 CMake 配置非常轻核心就是指定 include 路径、开启 C17、把测试文件逐个注册成可执行目标。下面是我常用的最小CMakeLists.txtcmake_minimum_required(VERSION 3.16) project(algo_template CXX) set(CMAKE_CXX_STANDARD 17) set(CMAKE_CXX_STANDARD_REQUIRED ON) set(CMAKE_CXX_FLAGS ${CMAKE_CXX_FLAGS} -Wall -Wextra -O2) # 模板头文件所在目录 include_directories(${CMAKE_SOURCE_DIR}/include) # 自动收集 tests 目录下所有 cpp每个编译成一个可执行文件 file(GLOB TEST_SOURCES ${CMAKE_SOURCE_DIR}/tests/*.cpp) foreach(test_src ${TEST_SOURCES}) get_filename_component(test_name ${test_src} NAME_WE) add_executable(${test_name} ${test_src}) endforeach()逻辑说明include_directories让测试文件能直接#include ds/dsu.hppfile(GLOB ...)自动发现测试文件新增一个test_xxx.cpp不用改 CMake-Wall -Wextra是必须的模板代码里的符号比较、类型截断问题全靠它暴露。参数上-O2在验证性能敏感模板比如线段树时建议保留否则你可能误判模板效率。编译和运行mkdir build cd build cmake .. make -j4 ./test_dsu如果test_dsu输出全部用例通过说明这套骨架已经可用。接下来往里填模板就行。提示不要用-O0验证模板正确性某些未定义行为比如越界读在-O2下才暴露而比赛和面试手写时通常默认开优化。3. 高频模板怎么写并查集、单调栈、快速幂三个样板3.1 并查集路径压缩加按秩合并的完整实现并查集是模板库里复用率最高的结构之一面试手写频率极高。核心就两个操作find和unite。只写路径压缩已经够用但加上按秩合并能把均摊复杂度压到接近常数。下面是我模板库里的dsu.hpp#pragma once #include vector #include numeric class DSU { public: // n 个元素初始各自独立 explicit DSU(int n) : parent_(n), rank_(n, 0) { std::iota(parent_.begin(), parent_.end(), 0); } // 查找根节点带路径压缩 int find(int x) { if (parent_[x] ! x) parent_[x] find(parent_[x]); // 递归压缩 return parent_[x]; } // 合并两个集合按秩合并 bool unite(int a, int b) { int ra find(a), rb find(b); if (ra rb) return false; // 已在同一集合 if (rank_[ra] rank_[rb]) std::swap(ra, rb); parent_[rb] ra; if (rank_[ra] rank_[rb]) rank_[ra]; return true; } bool same(int a, int b) { return find(a) find(b); } private: std::vectorint parent_; std::vectorint rank_; };逻辑说明find用递归实现路径压缩代码最短unite先找根再按秩决定谁挂到谁下面秩相同才增加。参数上n是元素个数元素编号默认 0 到 n-1如果你的题目是 1-based构造时传n1并忽略下标 0 即可。注意递归find在极端链式数据下可能爆栈如果数据量到 1e6 以上改成迭代版本更稳。3.2 单调栈下一个更大元素的标准写法单调栈是「用空间换时间」的典型很多题柱状图最大矩形、每日温度都是它的变体。模板库里应该有一个通用的「求每个元素左边/右边第一个更大/更小元素」的函数。下面这个版本返回每个位置右边第一个更大元素的下标不存在则为 -1#pragma once #include vector #include stack // 返回每个位置右侧第一个严格更大元素的下标无则 -1 std::vectorint nextGreaterElement(const std::vectorint nums) { int n nums.size(); std::vectorint res(n, -1); std::stackint st; // 存下标对应值单调递减 for (int i 0; i n; i) { while (!st.empty() nums[st.top()] nums[i]) { res[st.top()] i; // 找到了右侧第一个更大 st.pop(); } st.push(i); } return res; }逻辑说明栈里维护的是「还没找到更大元素」的下标且对应值从栈底到栈顶递减。遍历到i时把所有比nums[i]小的栈顶弹出来它们右侧第一个更大就是i。参数上nums传值还是传引用看习惯数据量大时建议传const避免拷贝。把改成就变成「严格更大」和「非严格更大」的区别这是最容易翻车的地方写模板时一定要在注释里标清楚。3.3 快速幂取模版本和非取模版本要分开快速幂是数学模块的标配但很多人只写一个版本结果在需要取模的题里溢出或者在不取模的题里被模数限制。我的做法是提供两个重载一个带模数一个不带。带模版本用long long防溢出#pragma once // 快速幂不取模注意结果可能溢出 long long fastPow(long long base, long long exp) { long long res 1; while (exp 0) { if (exp 1) res * base; base * base; exp 1; } return res; } // 快速幂取模mod 建议用 long long long long fastPowMod(long long base, long long exp, long long mod) { long long res 1 % mod; base % mod; while (exp 0) { if (exp 1) res res * base % mod; base base * base % mod; exp 1; } return res; }逻辑说明二进制拆分指数每次把底数平方。取模版本里res初始化为1 % mod是为了处理mod 1的边界。参数上exp用long long是因为有些题指数会超过intmod也建议long long避免两个int相乘溢出。这两个函数建议放在同一个头文件里命名区分清楚别指望调用方记得住哪个取模。注意fastPow不取模版本在指数稍大时就会溢出模板库里应该默认引导使用者用取模版本非取模版本只在明确知道结果范围时使用。4. 模板库的验证与测试别等比赛时才发现模板写错了4.1 每个模板配一个暴力对拍测试模板库最大的风险不是「不会写」而是「写错了但自己不知道」。我见过太多人比赛时套自己模板结果线段树区间更新写反调到最后发现是模板的锅。解决办法很土但有效每个模板配一个暴力版本用随机数据对拍。以并查集为例#include ds/dsu.hpp #include cassert #include cstdlib #include iostream int main() { for (int iter 0; iter 1000; iter) { int n rand() % 50 1; DSU dsu(n); // 暴力维护连通性 std::vectorstd::vectorbool conn(n, std::vectorbool(n, false)); for (int i 0; i n; i) conn[i][i] true; for (int op 0; op 200; op) { int a rand() % n, b rand() % n; if (rand() % 2) { dsu.unite(a, b); for (int i 0; i n; i) for (int j 0; j n; j) if (conn[i][a] conn[b][j]) conn[i][j] true; } else { bool expect conn[a][b]; assert(dsu.same(a, b) expect); } } } std::cout DSU all tests passed\n; return 0; }逻辑说明随机生成操作序列一边用模板跑一边用暴力二维布尔数组维护连通性每次查询都断言两者一致。参数上迭代次数 1000、元素数上限 50、操作数 200 是我常用的组合能在几秒内跑完且覆盖大部分边界。这个模式可以复制到线段树、最短路等所有模板上暴力版本怎么写取决于模板功能但思路一致。4.2 用编译期断言检查接口一致性模板库的接口一旦定下来最好用static_assert锁住关键类型避免以后重构时不小心改坏。比如快速幂取模版本可以断言返回类型和参数类型一致#include math/fast_pow.hpp #include type_traits static_assert(std::is_same_vdecltype(fastPowMod(2LL, 10LL, 1000LL)), long long, fastPowMod should return long long);逻辑说明static_assert在编译期检查不产生运行时代价。参数上decltype推导函数返回类型std::is_same_v做比较。这个技巧适合放在每个头文件末尾作为接口契约的一部分。如果哪天有人把返回类型改成int编译直接失败比运行时出错早得多。提示对拍测试不要只跑一次就删把它留在tests/目录里每次改模板后重新make一遍这是模板库能长期可信的唯一保障。5. 避坑与常见问题模板库用错比不会更可怕5.1 现象并查集 find 递归爆栈原因数据退化成链解决改迭代或加路径减半现象是程序在 1e6 级别数据上直接段错误本地小数据却正常。原因是find用递归实现如果合并顺序不当树可能退化成一条长链递归深度等于链长。解决办法有两个一是把find改成迭代版本用循环一路向上找根再压缩二是用「路径减半」技巧在循环里每次让parent_[x] parent_[parent_[x]]把深度砍半。我一般直接上迭代版本代码稍长但彻底免疫。5.2 现象单调栈结果和预期差一位原因严格与非严格比较搞混解决在函数名和注释里写死现象是「下一个更大元素」在存在相等元素时返回了下标而不是 -1。原因是模板里用了而不是把相等元素也当成更大。解决办法是在函数命名上区分比如nextGreaterStrict和nextGreaterOrEqual并在注释第一行写明比较规则。这个坑我踩过不止一次后来干脆在模板库里同时提供两个函数调用方自己选。5.3 现象快速幂取模结果负数原因底数为负没处理解决先取模再调整现象是fastPowMod(-2, 3, 100)返回负数。原因是 C 里负数取模结果符号跟被除数一致base % mod之后base仍是负的。解决办法是在base % mod后加一句if (base 0) base mod;。参数上如果题目保证底数非负可以不加但模板库应该默认处理因为调用方不一定记得。5.4 现象模板头文件重复包含导致重定义原因没写 include guard 或 pragma once解决每个头文件第一行加 pragma once现象是链接时报 multiple definition。原因是两个头文件互相包含或者测试文件重复引入。解决办法是每个.hpp第一行写#pragma once这是最省事的做法。注意#pragma once不是标准但所有主流编译器都支持模板库场景下够用。如果追求可移植性用传统 include guard 也行但名字要写全别用_DSU_H这种以下划线开头的保留标识符。5.5 现象CMake 编译通过但运行找不到头文件原因include 路径写成了相对路径解决统一用 CMAKE_SOURCE_DIR 拼绝对路径现象是cmake ..成功make时报fatal error: ds/dsu.hpp: No such file。原因是include_directories里写了include这种相对路径而 CMake 的相对路径基准是当前构建目录不是源码目录。解决办法是统一用${CMAKE_SOURCE_DIR}/include拼绝对路径。这个坑在新机器上第一次配环境时几乎必踩记住就行。6. 让模板库真正省时间的两个进阶习惯第一个习惯是给每个模板写「一行调用示例」放在头文件顶部注释里。比如dsu.hpp顶部写// DSU dsu(n); dsu.unite(a,b); dsu.same(a,b);。别小看这一行比赛时你脑子是热的翻到头文件看到调用示例比看函数签名快得多。第二个习惯是定期做「模板瘦身」把半年没用过的模板移到archive/目录主目录只留高频的十几个。模板库不是越大越好越大越容易在关键时刻选错。验证模板库是否合格有个很简单的标准随机抽一道你做过的题只允许用模板库里的代码看能不能在 15 分钟内写完并通过。如果做不到说明要么模板不全要么接口不顺手。我自己的库迭代了三年现在稳定在 20 个头文件左右每次比赛前跑一遍全部对拍测试通过才敢用。这个习惯帮我省下的调试时间远比攒模板花的时间多。希望帮到你。本文还有配套的精品资源点击获取