简介面向竞赛编程的C算法模板库按基础算法、数学、数据结构与图论四大模块系统整理适合算法竞赛选手、考研机试考生及需要快速落地经典算法的开发者。压缩包共127个文件以123个cpp模板为主体另有2个Markdown导读、1个tex与1个pdf公式参考整体仅730KB轻量易携。已有76人学习下载。模板覆盖双指针、前缀和、二分查找、单调栈、拓扑排序素数筛、欧拉函数、高斯消元、FFT并查集、树状数组、线段树、莫队以及Dijkstra、最小生成树、LCA、二分图匹配、2-SAT等常用算法。实现高效、结构统一注释清晰既可直接摘用参加比赛也可作为系统研读算法原理的资料适合作为竞赛与工程中的便携算法手册。1. 这个C算法模板库不是给链接用的是给你抄的拿到一个(源码)基于C的算法模板库.zip很多人的第一反应是把它当成现成库#include进来然后直接link。我劝你按住这个念头。这类源码包绝大多数不是稳定发布的二进制库而是刷题笔记、竞赛代码和工作片段攒成的“头文件集合”。它的价值不在链接在“抄”——把里面验证过的单调栈、线段树、KMP、数论筛子变成你自己能看懂、能改、能调的头文件。它可以帮你省掉大量重复造轮子的时间也能让你在笔试前快速把常用算法过一遍但前提是搞清楚它怎么组织、怎么编译、坑在哪。适合的人有三类准备算法面试的开发者、需要快速搭算法原型的工程师、以及想积累一个私人算法仓库的 C 使用者。2. 先看懂源码包目录怎么分、头文件怎么组织、为什么每个模板要能单独编译2.1 一个能落地的目录结构按数据结构、图论、数论、字符串分开解开 zip 之后我一般不会急着看哪个算法实现得漂亮而是先看它的目录。一个能长期维护的算法模板库目录一定按“算法领域”划分而不是按“谁写的”或“日期”划分。常见做法是这样algo_templates/ ├── include/ │ ├── data_structure/ │ │ ├── monotonic_stack.h │ │ ├── seg_tree.h │ │ └── union_find.h │ ├── graph/ │ │ ├── dijkstra.h │ │ └── tarjan_scc.h │ ├── math/ │ │ ├── gcd_ext.h │ │ └── prime_sieve.h │ ├── string/ │ │ ├── kmp.h │ │ └── trie.h │ └── sort/ │ ├── bubble_sort.h │ └── quick_sort.h ├── tests/ │ ├── test_monotonic_stack.cpp │ └── test_kmp.cpp ├── CMakeLists.txt └── README.md先把include/独立出来是有道理的模板头文件不需要单独编译成.o你只需要在编译时用-Iinclude把路径指给编译器。tests/放每个模板的验证程序这个习惯能救你的命。我第一次拿到别人模板库时图省事把所有代码放到一个all.h里结果每次改动都全量编译后来才拆开。2.2 自包含头文件原则include 一次就别靠“先后顺序”很多模板库的坑在于“头文件之间互相依赖但依赖关系完全靠 include 顺序维持”。比如你先 include 了common.h再 includeseg_tree.h能编译反过来就不行。这是最坏的设计。正确的做法叫“自包含头文件”每个头文件必须 include 它自己依赖的所有标准库或模块头文件。我拿到一个模板后会写一个十几行的脚本逐个头文件做语法检查for f in $(find include -name *.h); do echo checking $f g -fsyntax-only -stdc17 -Wall -Iinclude $f || echo FAIL: $f done这段脚本的逻辑很简单-fsyntax-only只做语法和语义分析不生成目标文件所以能非常快地找出“这个头文件单独编译时缺了什么”。如果某个头文件报错几乎都是因为它依赖了另一个头文件却没有自行 include。修法很简单把缺的#include vector、#include cstdint补到它自己头上。这样你以后在任意工程里随手 include 一个文件都能过不用背“先包含谁再包含谁”的顺序。2.3 只用标准库的边界STL 有的别自己造补 STL 没有的才叫模板库看模板库源码时一个最常见的误区是“看到什么都想自己写”。我见过的烂模板里有人连vector都要自己实现一遍结果边界问题比业务代码还多。一个合格的 C 算法模板库应该默认站在 C STL 的肩膀上排序用std::sort动态数组用std::vector字符串匹配优先考虑标准库能力模板库里只补 STL 不覆盖的算法和数据结构。所以当我打开模板库时会先快速扫一遍如果看到类似void bubble_sort(std::vectorint)这样的教学代码我不会指望它用在生产环境只会把它当“理解排序原理”的参考。真正值得复用的是单调栈、线段树、Dijkstra 堆优化、KMP 自动机这类 STL 给不了现成实现的算法。把 STL 能做的事从模板库里剥掉你的编译时间和维护成本立刻降一半。3. 把模板库跑起来VS Code 配置 C/C 环境用最小示例验证单调栈模板3.1 三个配置文件tasks.json、launch.json、c_cpp_properties.json拿到模板库第一件事是在本机跑通一个头文件。做 C 开发VS Code 配 C/C 环境是地面常见操作。很多新手只装了 C 插件就开始点右上角运行结果报“无法打开 源文件”根因多半是includePath没指到模板库的include/目录。我一般会建一个.vscode目录放三个文件。先看tasks.json它负责编译{ version: 2.0.0, tasks: [ { type: cppbuild, label: Build with g, command: /usr/bin/g, args: [ -stdc17, -O2, -Wall, -Iinclude, main.cpp, -o, main ], group: { kind: build, isDefault: true } } ] }参数这么多核心就是三条-stdc17定语言标准-Iinclude让编译器能找到模板头文件-O2开优化。模板库里的算法大多按“性能优先”写不开-O2某些数据结构会慢到让你误判复杂度。然后是launch.json它负责让 F5 能调试{ version: 0.2.0, configurations: [ { name: Debug, type: cppdbg, request: launch, program: ${workspaceFolder}/main, args: [], stopAtEntry: false, cwd: ${workspaceFolder}, environment: [], externalConsole: false, MIMode: gdb, setupCommands: [ { description: Enable pretty-printing, text: -enable-pretty-printing, ignoreFailures: true } ], preLaunchTask: Build with g } ] }program指向编译产物preLaunchTask告诉它调试前先跑一遍构建任务。第三个文件c_cpp_properties.json给 IntelliSense 用{ configurations: [ { name: Linux, includePath: [ ${workspaceFolder}/include, ${workspaceFolder}/** ], defines: [], compilerPath: /usr/bin/g, cStandard: c17, cppStandard: c17 } ], version: 4 }三个文件配合好编辑器不再满屏红波浪线F5 能直接断点单步跟进模板内部——这一步对新读者尤其重要因为模板代码一旦封装深了想通过printf看状态非常痛苦断点比 print 靠谱得多。3.2 第一个模板单调栈跑通最小示例我在模板库里最先跑通的通常是单调栈。它实现短、依赖少、但思路有代表性。假设include/data_structure/monotonic_stack.h长这样#pragma once #include vector #include stack namespace algo { // 返回每个元素右侧第一个比它大的元素的下标没有则为 -1 template typename T std::vectorint nextGreaterRight(const std::vectorT nums) { std::vectorint res(nums.size(), -1); std::stackint st; // 栈里存下标 for (int i 0; i (int)nums.size(); i) { while (!st.empty() nums[i] nums[st.top()]) { res[st.top()] i; st.pop(); } st.push(i); } return res; } } // namespace algo配一个最小主程序#include iostream #include vector #include data_structure/monotonic_stack.h int main() { std::vectorint a {2, 1, 5, 3, 4}; auto ans algo::nextGreaterRight(a); for (int x : ans) std::cout x ; std::cout std::endl; return 0; }编译命令g -stdc17 -O2 -Wall -Iinclude main.cpp -o main ./main这段逻辑说明一下单调栈维护的是“当前还没找到右侧更大元素”的下标栈从底到顶保持下标对应的值递减。每当新元素比栈顶大就说明栈顶右侧第一个更大元素出现了于是出栈并记录答案。模板参数T让这个栈能处理int、long long、double等数值类型如果你需要“右侧第一个更小”只需把比较符号反过来封装成另一个函数。3.3 排序类模板怎么选别急着替换 std::sort模板库里经常出现冒泡排序、快排这类教学实现。比如include/sort/bubble_sort.h#pragma once #include vector namespace algo { template typename T void bubbleSort(std::vectorT a) { int n (int)a.size(); for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { std::swap(a[j], a[j 1]); swapped true; } } if (!swapped) break; // 本趟无交换说明已有序 } } } // namespace algo这个模板的价值在于教学和理解不在生产。真实场景我推荐直接用std::sortstd::sort(a.begin(), a.end());如果要在排序时自定义规则比如“按绝对值降序”就在模板库里封装一个比较器template typename T, typename Compare void smartSort(std::vectorT a, Compare cmp) { std::sort(a.begin(), a.end(), cmp); } // 使用 smartSort(a, [](int x, int y) { return std::abs(x) std::abs(y); });把std::sort包一层smartSort的收益是统一入口将来想统计排序次数、加日志、换成稳定排序只改一处。但千万别因为模板库里有一份冒泡排序源码就真拿它去排十万条数据——复杂度摆在那里跑一次就后悔。4. 模板封装粒度与 C 版本边界参数、命名空间、字符串数组初始化4.1 封装粒度算法用函数模板数据结构用类模板看模板库源码时最需要拿捏的是“封装到多细”。我的一般标准纯算法用函数模板有状态的结构用类模板。算法比如快速幂、GCD、单调栈输入输出都是明确的函数模板正合适线段树、并查集、Trie 这类需要内部维护数组或节点对象必须用类模板把状态藏起来。一个容易翻车的点是模板参数设计过重。有人喜欢把每次调用都传入“分配器”“比较器”“策略模式”看着很通用实际上用起来又长又难读。我的经验是默认参数给最常用的实现保持简单template typename T, typename Compare std::lessT class MonotonicStack { public: void push(const T v) { while (!st_.empty() cmp_(st_.top(), v)) st_.pop(); st_.push(v); } T top() const { return st_.top(); } private: std::stackT st_; Compare cmp_; };同时把这些类放进namespace algo。命名空间是模板库的刚需否则Dijkstra、UnionFind这种名字放到业务工程里很容易和别的库撞车。调用时写algo::MonotonicStackint清晰using namespace algo;也不至于把 pollute 到什么程度。4.2 字符串和数组的两种输入处理别让字符串模板只会读整串模板库里字符串算法KMP、Trie、Manacher最常见的问题是没有处理“字符串数组”和“逐字符访问”的差异。比如 KMP 模板有的写死成void kmp(const std::string text, const std::string pat)一旦你想对std::vectorstd::string同时跑多个模式串又得写一遍循环。我的处理方式是把核心逻辑写成迭代器版本template typename Iterator std::vectorint buildPrefix(Iterator first, Iterator last) { int n (int)(last - first); std::vectorint pi(n, 0); for (int i 1, j 0; i n; i) { while (j 0 first[i] ! first[j]) j pi[j - 1]; if (first[i] first[j]) j; pi[i] j; } return pi; }这样std::string、std::vectorchar、const char*都能喂进去。至于“c字符串数组初始化”常见需求是这样的std::vectorstd::string dict {apple, banana, cherry}; // 字符串数组 std::string s hello; // 普通字符串 std::vectorint nums{1, 2, 3, 4}; // 数组初始化模板内部尽量统一接收“迭代器范围”或const std::string避免 C 风格数组作为参数发生时数组名退化成指针导致的边界丢失。如果模板库里到处是char[]和strlen我建议你重写而不是复用。4.3 C 版本与模板库的兼容性边界用 C17 写用 static_assert 守门不同的编译器默认标准不一样老项目可能还在 C11新项目已经 C20。模板库如果用了auto返回类型推导、if constexpr、std::string_view就得在 README 里写清楚最低版本。我习惯在公共头文件顶部放一个静态断言#if __cplusplus 201703L #error This algorithm library requires C17 or later. #endif这行会在编译期直接拒绝老编译器比等到模板实例化时爆一堆看不懂的报错友好得多。再往下模板内部尽量少用if constexpr这类“初学者看不明白”的特性除非它确实能减少代码量。用std::string_view做只读字符串参数能减少拷贝但要注意它不保证以\0结尾如果你的算法内部调用了依赖空字符结尾的 C API就别偷懒用std::string。我在承接一个 muduo 风格的网络服务时把模板库标准锁在 C17理由很朴素编译快、特性够用、团队成员都能看懂C20 的 concept 和 module 等稳定了再说。日志组件我偏好 spdlog 这类成熟库算法模板库只管算法本身不掺和 IO 和网络边界干净才敢长期依赖。5. 避坑模板库编译失败、重复定义、编译慢到底怎么排查5.1 现象模板实例化报错满屏红根本看不懂用模板库时最容易看到的是“编译错误上千行”尤其在你把一个vectorint传给期望vectorstring的模板时。原因在于模板是在调用处展开的真正的错误信息往往埋在第一条后面全是编译器被错误状态带偏后的连锁反应。解决办法是在编译命令里加-fmax-errors1g -stdc17 -Iinclude -fmax-errors1 main.cpp -o main这样编译器只报第一个错误就停。然后顺着第一个错误往上翻基本就是“类型不匹配”“缺少 include”“参数个数不对”这三类。记住一个惨痛教训别被前 20 行报错带偏去看最上面的error:行。模板报错是黑匣子但它的入口总是明确的。5.2 现象链接期提示 multiple definition of xxx头文件明明加了#pragma once为什么链接还报重复定义因为#pragma once只防止“同一个编译单元里被 include 两次”但如果两个.cpp文件都 include 同一个头文件而头文件里写了“非模板的普通函数定义”链接器就会看到两份同名符号。解决方法是分清三类内容模板函数、模板类、内联函数可以放在头文件普通函数和全局变量要么放进单独的.cpp要么加inline。比如// bad: 链接期 multiple definition int addOne(int x) { return x 1; } // good: 加 inline 或写成模板 inline int addOne(int x) { return x 1; }我见过一个模板库把所有工具函数都写成非 inline 的普通函数结果调用者只要 include 两个不同模块就链接失败。检查时用nm main.o | grep addOne看看符号是不是T类型如果是全局文本符号且没有inline就要处理。5.3 现象模板库 Debug 模式慢到怀疑人生O2 下又正常如果你用 VS Code 默认的-g命令编译模板库跑一个一百万数据量的快速排序可能比 O2 慢几十倍。这不一定是模板库代码的问题而是 STL 在 Debug 模式下会插入大量边界检查和迭代器验证。解决方法是把“验证正确性”和“测量性能”分离。日常调试用-O0 -g只验证逻辑性能测试用-O2 -DNDEBUG让assert和_GLIBCXX_DEBUG都关闭。比如# 调试 g -stdc17 -g -O0 -Iinclude main.cpp -o main_debug # 性能 g -stdc17 -O2 -DNDEBUG -Iinclude main.cpp -o main_release如果你在测试模板库里某个数据结构Debug 慢得无法接受可以先开-O1折中。另一个技巧是给测试代码里关键的循环加std::chrono计时用数据说话别靠“感觉慢”。5.4 现象字符串匹配模板越跑越慢传参在反复拷贝KMP 这类字符串算法如果接口写的是void kmp(std::string text, std::string pat)那么每调用一次就会拷贝两份字符串。当文本是几 MB 时这个拷贝开销甚至能盖过算法本身的复杂度。原因不言自明按值传递。解决方法是所有只读字符串参数改成常量引用或 C17 的std::string_view// bad void kmp(const std::string text, const std::string pat); // good void kmp(const std::string text, const std::string pat); // or void kmp(std::string_view text, std::string_view pat);用std::string_view的收益是字符串切片零拷贝但它有副作用它不保证\0结尾所以如果模板内部用了c_str()传给 C 函数就得小心。另外别把临时字符串存进string_view否则临时对象销毁后它就是悬垂引用。这是 C 模板库源码里最容易踩出的血泪经验。5.5 现象整个 include 模板库编译时间爆炸有人图省事写了一个all.h把所有模板 include 进去然后工程里每个.cpp都 include 它。第一次编译还能忍改动一个头文件后所有依赖它的文件全部重编十几秒起步项目越大越痛苦。解决方法是“按需 include”同时在 CMake 里把include/设为接口头文件目录不参与编译add_library(algo_templates INTERFACE) target_include_directories(algo_templates INTERFACE ${CMAKE_CURRENT_SOURCE_DIR}/include) target_compile_features(algo_templates INTERFACE cxx_std_17)这样只有真正#include data_structure/monotonic_stack.h的文件才感知模板库的变化。如果你的模板库本身就分成几十个独立头文件每个编译单元只碰自己需要的部分编译时间通常能控制在秒级。真遇到“全量重编”的场景可以给稳定不变的大头文件开预编译头但不建议在模板库维护初期用收益不大还增加复杂度。6. 把模板库变成自己的武器库对拍验证、性能基准和一条命令跑完测试模板库的价值只有在你信任它之后才体现。我给自己定了一条铁律任何从网上抄来的模板必须经过“对拍”才能进自己的库。所谓对拍就是写一个暴力算法和一个模板算法用随机数据反复对比输出。暴力算法可能很慢但正确性一眼能看出来模板算法跑得快但可能有隐蔽的边界错。只要两者结果不一致就先查模板。一个最简单的对拍框架长这样#include random #include iostream #include data_structure/monotonic_stack.h std::vectorint bruteForce(const std::vectorint nums) { int n (int)nums.size(); std::vectorint res(n, -1); for (int i 0; i n; i) for (int j i 1; j n; j) if (nums[j] nums[i]) { res[i] j; break; } return res; } int main() { std::mt19937 rng(2024); for (int t 0; t 10000; t) { int n rng() % 20 1; std::vectorint a(n); for (int x : a) x (int)(rng() % 100) - 50; auto ans1 bruteForce(a); auto ans2 algo::nextGreaterRight(a); if (ans1 ! ans2) { std::cerr mismatch on test t std::endl; return 1; } } std::cout all tests passed std::endl; return 0; }有了这个框架每新增一个模板我就在tests/下放一个对拍文件最后用一条命令把整个测试目录跑完for f in tests/test_*.cpp; do g -stdc17 -O2 -Iinclude $f -o /tmp/t /tmp/t || echo FAIL $f done性能基准则单独写用std::chrono::steady_clock测最坏输入不要用随机小数据自我感动。比如测排序模板就生成降序、升序、重复值三种数据分别计时。我自己的习惯是每次拿到新模板先对拍、再测性能、最后写一行注释说明适用场景和数据范围。这个动作坚持半年后模板库会越来越像自己的武器库。调试时先用线性扫描验证答案再用模板做大数据量性能测试能避免绝大多数“正确性没验过就上线”的翻车。希望帮到你。本文还有配套的精品资源点击获取