1. 项目缘起为什么我们需要一个“常用模板”库在C的日常开发中无论是算法竞赛、项目攻坚还是技术面试我们总会反复遇到一些“似曾相识”的问题。比如快速写一个并查集来处理连通性问题或者实现一个带自定义比较器的优先队列。每次遇到要么是去翻找以前的代码要么是临时上网搜索效率低下不说还容易因为记忆模糊而引入边界条件的错误。更头疼的是不同场景下的实现细节往往有微妙差别——竞赛追求极致的运行效率项目则更看重代码的清晰与可维护性。这种割裂感促使我开始系统地整理一份属于自己的C常用模板库。这份“学习记录”并非一份面面俱到的STL文档也不是一本算法教科书。它的核心定位是一个实战导向的、经过验证的代码工具箱。里面的每一段代码都源自于我过去在解决具体问题时踩过的坑、优化过的细节以及在不同需求间权衡后的最终选择。它记录的不是“标准答案”而是“在什么情况下哪种写法更合适”。例如一个简单的二分查找在数组严格单调和存在重复元素时lower_bound和upper_bound的返回值处理就完全不同一个Dijkstra最短路径算法使用vector还是priority_queue其代码结构和性能表现也大相径庭。因此我将不定期更新这个库每次新增或修改都伴随着对某个技术点更深入的理解或是在新场景下的应用心得。希望这份持续生长的记录不仅能作为我个人的“外置大脑”也能为正在阅读的你提供一些可直接“抄作业”又知其所以然的参考。2. 基础构建块超越std::的实用模板与宏在深入复杂的数据结构和算法之前一些基础的工具模板能极大提升编码效率和代码健壮性。它们通常是解决更复杂问题的基石。2.1 类型别名与编译期常量使用using进行类型别名定义比传统的typedef更清晰尤其是在模板编程中。templatetypename T using Vec std::vectorT; // 简化嵌套的vector声明如 VecVecint 代替 std::vectorstd::vectorint using ll long long; // 算法竞赛中防止溢出的常用类型 using pii std::pairint, int; // 简化pair声明常用于图的邻接表存储 (to, weight)编译期常量能避免魔法数字提高代码可读性。constexpr int INF 0x3f3f3f3f; // 一个很大的数常用于初始化距离数组两个INF相加不会溢出int constexpr double EPS 1e-8; // 浮点数比较的精度容忍度2.2 输入输出加速与调试宏对于需要处理大量输入输出的场景如算法竞赛关闭C标准流与C标准流的同步可以显著提升速度。std::ios::sync_with_stdio(false); // 解除与C标准库的同步 std::cin.tie(nullptr); // 解除cin与cout的绑定进一步加速 std::cout.tie(nullptr);注意使用此优化后严禁将std::cin/std::cout与printf/scanf混用否则会导致输入输出顺序错乱。调试宏在开发阶段非常有用可以方便地输出变量值并在发布时一键禁用。#ifdef LOCAL // 通常本地调试时定义此宏 #define debug(...) std::cerr [ #__VA_ARGS__ ]:, debug_out(__VA_ARGS__) template typename... Args void debug_out(Args... args) { ((std::cerr args), ...) std::endl; } #else #define debug(...) 42 // 非调试模式下宏展开为一个无操作的值 #endif这个debug宏利用了C17的折叠表达式可以打印任意数量、任意类型的参数并自动添加换行比手动写多个cerr语句方便得多。2.3 范围遍历与Lambda表达式辅助C11引入的基于范围的for循环极大地简化了容器遍历。结合auto和引用可以写出既安全又高效的代码。std::vectorint vec {1, 2, 3}; // 只读遍历 for (const auto val : vec) { /* ... */ } // 需要修改元素的遍历 for (auto val : vec) { val * 2; } // 如果元素是复杂对象且遍历过程不修改容器结构使用 const auto 是性能最佳实践。Lambda表达式是现代C的利器尤其在配合STL算法时。一个常见的需求是定义临时的比较器。// 对vectorpairint, string 按第一个元素降序第二个元素升序排序 std::vectorstd::pairint, std::string data; std::sort(data.begin(), data.end(), [](const auto a, const auto b) { if (a.first ! b.first) return a.first b.first; // 第一维降序 return a.second b.second; // 第二维升序 });这里使用auto作为参数类型让编译器自动推导使得Lambda表达式成为一个模板更加通用。3. 容器精讲std::deque的双端艺术与实战选择STL提供了丰富的容器每个都有其特定的复杂度保证和适用场景。vector和map大家都很熟悉而deque双端队列的特性却常常被误解或低估。3.1deque的底层逻辑与性能特征deque允许在头部和尾部进行常数时间的插入和删除操作。这与vector尾部操作快头部操作慢和list任何位置插入删除都快但内存不连续形成了鲜明对比。它的内部实现通常是一系列固定大小的数组块buffer通过一个中央映射表map来管理这些块。这种结构带来了几个关键特性随机访问支持operator[]和at()时间复杂度为O(1)但常数因子比vector大因为它需要先计算目标元素在哪个内存块。迭代器失效在首尾添加元素不会使任何迭代器失效但会使所有指向元素的引用和指针失效除非插入位置在另一端。在中间插入或删除元素会使所有迭代器、引用和指针失效。这一点比vector尾部插入可能失效中间插入必然失效稍好但比list永远不失效差。内存占用由于需要维护内部映射表和多块内存其内存开销通常高于vector。3.2 何时该用deque对比vector和list选择容器本质是在随机访问、中间插入/删除、首尾插入/删除和内存局部性之间做权衡。vsvector当你需要一个“可双向生长的数组”时用deque。典型场景是实现一个滑动窗口最大值/最小值问题。你需要频繁在窗口尾部添加新元素在窗口头部移除旧元素。如果使用vector从头部移除元素是O(n)的操作需要移动后面所有元素而deque的pop_front是O(1)。// 滑动窗口最大值示例框架 std::dequeint dq; // 存储的是数组下标而非值 for (int i 0; i n; i) { // 移除超出窗口范围的头部元素 while (!dq.empty() dq.front() i - k) dq.pop_front(); // 维护deque单调递减队首始终是当前窗口最大值 while (!dq.empty() nums[dq.back()] nums[i]) dq.pop_back(); dq.push_back(i); if (i k - 1) result.push_back(nums[dq.front()]); }vslist当你需要频繁的随机访问同时也有不少首尾操作但中间插入删除很少时deque是比list更好的选择。因为list的随机访问是O(n)而deque是O(1)且deque的内存连续块能更好地利用CPU缓存。list的优势仅在需要频繁在容器任意位置插入删除且不需要随机访问时才能体现例如实现一个LRU缓存的高频更新部分。3.3deque的陷阱与最佳实践慎用insert和erase除非万不得已避免在deque中间进行插入删除。这不仅会导致*O(n)*的时间复杂度因为需要移动元素还会使所有迭代器失效极易引发难以调试的bug。理解内存分配deque的扩容比vector更“平滑”。vector扩容需要分配一块全新的更大的内存并整体搬迁而deque只需分配一个新的内存块并添加到映射表中。这使得deque在需要持续向尾部添加元素且担心vector扩容导致性能波动的场景下能提供更可预测的性能但每次扩容的增量较小。性能测试对于关键路径上的代码如果纠结于用vector自定义头指针模拟队列还是直接用deque最好的方法是用真实数据做性能剖析Profiling。抽象复杂度相同但常数因子可能因具体实现、编译器优化和数据规模而产生显著差异。4. 算法模板核心二分查找的“魔鬼细节”二分查找是算法中最基础也最易出错的模板之一。其核心难点不在于思想而在于循环不变量的维护和边界条件的处理。这里提供两种最常用的、语义清晰的模板。4.1 模板一寻找第一个不小于目标值的位置 (lower_bound)这个模板用于在非递减序列中查找第一个大于等于目标值target的元素位置。如果所有元素都小于target则返回数组长度即假设的尾后位置。// 返回 [left, right) 区间内第一个 target 的元素索引。若不存在返回 right。 int lower_bound(const std::vectorint nums, int target) { int left 0; int right nums.size(); // 注意右边界是开区间 while (left right) { // 循环条件区间内还有元素 int mid left (right - left) / 2; // 防止(leftright)溢出 if (nums[mid] target) { right mid; // 答案在左半部分包括mid } else { left mid 1; // 答案在右半部分不包括mid } } // 循环结束时left right且指向第一个target的位置或nums.size() return left; }循环不变量在整个循环过程中[left, right)这个左闭右开区间内始终包含如果存在的话第一个大于等于target的元素。right的初始值nums.size()确保了即使target大于所有元素这个不变量也成立。4.2 模板二寻找第一个大于目标值的位置 (upper_bound)这个模板用于在非递减序列中查找第一个大于目标值target的元素位置。// 返回 [left, right) 区间内第一个 target 的元素索引。若不存在返回 right。 int upper_bound(const std::vectorint nums, int target) { int left 0; int right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { // 唯一区别将 改为 right mid; } else { left mid 1; } } return left; }实战应用upper_bound-lower_bound的值就是序列中等于target的元素个数。这是解决“统计出现次数”类问题的利器。4.3 避坑指南为什么我的二分死循环了二分查找最常见的错误是导致无限循环根源在于中间位置mid的计算和边界更新不匹配。mid的取整方向在上面的模板中我们使用mid left (right - left) / 2这是向下取整。当更新left mid 1时区间一定会缩小。但如果你的更新逻辑是left mid在某些寻找最后一个满足条件的元素的模板中并且使用向下取整当left和right相差1时mid会等于left导致left无法更新陷入死循环。此时需要改用向上取整mid left (right - left 1) / 2。区间开闭始终坚持一种区间表示法推荐左闭右开[left, right)并让循环条件(left right)、mid计算和边界更新与之匹配。混用开闭区间是混乱的根源。最终返回值理解left或right退出循环时的语义。在lower_bound模板中它返回的是插入位置即如果要将target插入有序序列并保持有序应该插入的索引。这个理解有助于处理“找不到”的情况。我个人建议在绝大多数情况下使用上面提供的lower_bound/upper_bound模板足矣。对于寻找“最后一个小于等于target的元素”这类问题可以转化为“寻找第一个大于target的元素然后减一”即upper_bound(...) - 1这样能复用稳定可靠的模板减少出错概率。5. 图论算法模板Dijkstra的多种实现与选择单源最短路径算法是图论的核心。Dijkstra算法适用于边权非负的图其实现方式多样性能差异显著。5.1 邻接表存储灵活性的基础首先图的存储方式决定了下限。邻接表比邻接矩阵更节省空间尤其适合稀疏图。struct Edge { int to; // 目标顶点 int weight; // 边权 // 可以添加其他属性如边的编号、反向边指针用于网络流等 }; using Graph std::vectorstd::vectorEdge; // 邻接表 // 初始化一个n个顶点的图 int n 100; Graph g(n); // 添加一条从u到v权重为w的有向边 g[u].push_back({v, w}); // 对于无向图需要添加两条有向边 g[u].push_back({v, w}); g[v].push_back({u, w});5.2 标准库优先队列版最常用的写法这是最直观和常用的实现利用std::priority_queue默认是大顶堆来获取当前距离源点最近的点。std::vectorint dijkstra(const Graph g, int start) { int n g.size(); std::vectorint dist(n, INF); dist[start] 0; // 使用小顶堆pair的first是距离second是顶点编号 std::priority_queuestd::pairint, int, std::vectorstd::pairint, int, std::greaterstd::pairint, int pq; pq.emplace(0, start); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); // 关键优化如果弹出的不是最新距离说明是旧数据直接跳过 if (d dist[u]) continue; for (const auto e : g[u]) { int v e.to; int nd d e.weight; if (nd dist[v]) { dist[v] nd; pq.emplace(nd, v); } } } return dist; }关键点if (d dist[u]) continue;这行代码至关重要。因为优先队列不支持修改已有元素的值我们采用“惰性删除”策略当某个顶点的距离被更新时我们将新的(距离, 顶点)对压入堆中。堆里可能同时存在同一个顶点的多个不同距离的条目。当弹出时如果发现弹出的距离大于当前记录的最短距离说明这是一个过时的、无效的条目直接跳过。这避免了实现复杂的堆内元素修改操作。时间复杂度为O((VE) log V)其中V是顶点数E是边数。5.3 手写二叉堆或std::set版何时需要标准库的priority_queue不支持修改堆内元素的值这在某些极端情况下可能导致堆中无效条目过多影响性能尽管有上述的跳过机制。如果图的边权更新非常频繁或者对常数性能有极致要求可以考虑能支持decrease-key操作的数据结构。手写二叉堆或斐波那契堆可以实现decrease-key操作保证每个顶点在堆中只有一个条目理论复杂度更优但实现复杂在竞赛或普通工程中很少需要。使用std::setset本身是有序的可以看作一个可删除任意元素的“堆”。我们可以将(距离, 顶点)对存入set当需要更新一个顶点的距离时先找到并删除旧的条目再插入新的。std::setstd::pairint, int s; s.emplace(0, start); // ... 在更新距离时 auto it s.find({dist[v], v}); if (it ! s.end()) s.erase(it); s.emplace(nd, v);这种方法代码简洁且每个顶点在set中最多只有一个条目。但set的插入、删除、查找都是O(log n)且常数比priority_queue大。实测中对于普通规模的图priority_queue惰性删除的方案几乎总是更快因为其常数更小且现代CPU缓存对其连续内存访问更友好。选择建议无脑优先使用priority_queue惰性删除的方案。它简单、高效、可靠。只有在非常确定decrease-key操作能带来巨大性能提升且愿意承担代码复杂度的前提下才考虑其他实现。6. 并查集模板路径压缩与按秩合并的权衡并查集用于处理不相交集合的合并与查询问题其核心优化是路径压缩和按秩合并。两者结合使用能使单次操作的均摊时间复杂度接近常数。6.1 基础模板与两种优化class UnionFind { public: std::vectorint parent; std::vectorint rank; // 秩可以理解为树的高度上界 UnionFind(int n) : parent(n), rank(n, 0) { for (int i 0; i n; i) parent[i] i; } int find(int x) { // 路径压缩在查找根的同时将路径上所有节点的父节点直接指向根 return parent[x] x ? x : (parent[x] find(parent[x])); } void unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; // 按秩合并将矮树接到高树下避免树退化成链 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; // 两棵树高度相同合并后高度1 } } bool connected(int x, int y) { return find(x) find(y); } };6.2 为什么需要“按秩合并”如果只使用路径压缩在最坏情况下例如总是将大树接到小树下单次unite操作的时间复杂度可能退化到O(log n)。按秩合并保证了树的高度增长非常缓慢从而与路径压缩配合达到近乎常数的均摊时间。一个常见的误解是“按秩合并”的rank是精确的树高。在路径压缩后树高会发生变化rank实际上只是一个上界。它记录的是“在没有路径压缩的情况下这棵树可能达到的高度”。这正是它巧妙的地方我们不需要维护精确的高度只需要一个上界来指导合并顺序就能保证效率。6.3 扩展应用维护额外信息并查集的神奇之处在于可以扩展在集合的根节点上维护一些额外信息。维护集合大小初始化一个size数组全为1。在unite时将小集合的size加到大的集合上。if (size[rootX] size[rootY]) std::swap(rootX, rootY); parent[rootY] rootX; size[rootX] size[rootY];带权并查集在每个节点上维护一个到根节点的“权值”如距离、差值等。在find进行路径压缩时需要同步更新权值。这在解决“食物链”、“奇偶性”等问题时非常有用。pairint, int find(int x) { // 返回根节点和x到根节点的权值 if (parent[x] ! x) { auto [root, val] find(parent[x]); weight[x] (weight[x] val) % MOD; // 根据具体问题定义合并规则 parent[x] root; } return {parent[x], weight[x]}; }这类问题的关键在于定义清楚权值的含义和推导出合并两个集合时连接两根的边的权值该如何计算。这通常需要根据题意列出方程。实操心得对于绝大多数问题使用基础模板路径压缩按秩合并就足够了。在遇到需要统计集合大小的问题时增加size数组。只有遇到明显的“相对关系”类问题如A和B是同类的B和C是敌人问A和C的关系才需要考虑带权并查集。在实现带权并查集时务必在纸上画图推导清楚权值合并的公式这是最容易出错的地方。