C++算法竞赛 STL 入门笔记

在算法竞赛中STL标准模板库是提升编码效率的核心神器无需手动实现数据结构就能快速完成动态存储、排序、查找、最值维护等操作。本文覆盖竞赛 90% 场景下的高频 STL 组件配合代码示例、时间复杂度、适用场景和踩坑指南看完即可上手刷题。1. vector 动态数组vector 是竞赛中使用频率最高的容器可以理解为长度可动态变化的数组数据存储在堆内存中不会爆栈支持下标随机访问。头文件#include vector万能头bits/stdc.h已自动包含1.1 常用构造方式cpp运行vectorint arr1; // 空的int型数组 vectorint arr2(100); // 长度为100元素默认初始化为0 vectorint arr3(100, 1); // 长度为100所有元素初始化为1 // 二维数组构造矩阵、邻接表常用 vectorvectorint mat1(100); // 100行每行是空数组 vectorvectorint mat2(100, vectorint(666, -1)); // 100行666列初值全为-1时间复杂度O (n)n 为元素个数。1.2 核心操作方法cpp运行arr.push_back(x); // 尾部插入元素x数组长度1 arr.pop_back(); // 删除尾部元素数组长度-1 arr.size(); // 返回当前元素个数 arr.empty(); // 判断数组是否为空 arr.clear(); // 清空所有元素长度变为0 arr.resize(n); // 将数组长度调整为n多删少补默认补0 arr.back(); // 获取尾部元素 arr.front(); // 获取头部元素 arr[i]; // 下标访问第i个元素从0开始1.3 时间复杂度尾插push_back、尾删pop_back均摊 O (1)下标随机访问O (1)中间位置插入 / 删除O (n)构造、清空O (n)1.4 竞赛适用情形替代普通数组避免开小了 RE、开大了 MLE 的问题存图的邻接表最主流写法二维 / 多维动态矩阵行列数由输入决定的场景动态存储答案、临时数据数据规模不确定的题目。1.5 注意事项与优化提前开空间提速如果已知元素总个数直接在构造时指定长度避免反复扩容的开销大数据量下差异明显。cpp运行// 优化前反复扩容慢 vectorint a; for(int i0; i1e8; i) a.push_back(i); // 优化后一次性分配空间快 vectorint a(1e8); for(int i0; ia.size(); i) a[i] i;下标不能越界空数组调用back()、pop_back()会直接运行错误极端卡常的题目普通数组速度略优于 vector可优先用数组。2. stack 栈栈是先进后出LIFO的线性结构只能操作栈顶元素底层默认由 deque 封装。头文件#include stack2.1 常用方法作用用法示例构造栈stack类型 栈名stackint stk;元素入栈.push(x)stk.push(1);栈顶出栈.pop()stk.pop();获取栈顶.top()int x stk.top();获取大小.size()int len stk.size();判空.empty()if(stk.empty()) ...2.2 时间复杂度所有操作均为 O (1)。2.3 竞赛适用情形括号匹配、表达式求值中缀转后缀单调栈经典题型最大矩形、每日温度等模拟递归避免递归深度过深爆栈DFS 非递归写法。2.4 注意事项不支持随机访问不能遍历不能用下标、范围 for 循环遍历栈这是新手最容易犯的错误空栈执行pop()、top()会直接 RE操作前必须判空也可以用 vector 模拟栈push_back对应入栈pop_back对应出栈back()对应取栈顶功能一致且速度更快卡常时推荐使用。3. queue 队列队列是先进先出FIFO的线性结构只能队尾入队、队头出队。头文件#include queue3.1 常用方法cpp运行queueint q; q.push(x); // 队尾插入元素x q.pop(); // 弹出队头元素 q.front(); // 获取队头元素 q.back(); // 获取队尾元素 q.size(); // 返回队列元素个数 q.empty(); // 判断队列是否为空3.2 时间复杂度所有操作均为 O (1)。3.3 竞赛适用情形BFS 广度优先搜索迷宫最短路、层序遍历等必用排队轮转类模拟题单调队列基础载体滑动窗口最值问题。3.4 注意事项和栈一样不支持随机访问、不能用下标遍历空队列执行pop()、front()会 RE操作前务必判空。4. priority_queue 优先队列堆优先队列本质是二叉堆默认是大根堆堆顶为最大元素支持快速取出最值、插入元素是堆相关算法的核心。头文件#include queue4.1 基础用法与示例cpp运行priority_queueint pque; // 默认大根堆 pque.push(1); // 堆顶为1 pque.push(3); // 堆顶为3 pque.push(2); // 堆顶仍为3 pque.push(4); // 堆顶为4 pque.pop(); // 弹出最大值4堆顶变为34.2 小根堆写法竞赛高频默认是大根堆实现小根堆需要指定比较方式cpp运行// int型小根堆 priority_queueint, vectorint, greaterint pq; // pair型小根堆按first排序Dijkstra常用 priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq;自定义结构体也可以通过重载运算符实现堆排序这里不再展开。4.3 时间复杂度插入push、删除popO(logn)取堆顶topO(1)4.4 竞赛适用情形Dijkstra 堆优化最短路算法核心写法堆优化 Prim 最小生成树Top K 问题、多路归并、哈夫曼编码贪心算法中动态维护最值的场景。4.5 注意事项默认是大根堆写最短路等需要最小值的场景时一定要转成小根堆这是新手高频错题不支持删除任意元素只能删除堆顶如果需要删除中间元素改用 set空堆执行pop()、top()会 RE操作前判空。5. set multiset 有序集合底层由红黑树实现元素自动升序排序。set中元素不重复multiset允许元素重复均支持高效查找、插入、删除。头文件#include set5.1 常用方法cpp运行setint s; s.insert(x); // 插入元素x重复元素不会重复插入 s.erase(x); // 删除所有值为x的元素 s.erase(it); // 删除迭代器it指向的单个元素 s.find(x); // 查找x返回迭代器找不到返回s.end() s.count(x); // 返回x的出现次数set中只能是0或1 s.size(); // 元素个数 s.empty(); // 是否为空 s.clear(); // 清空集合 s.lower_bound(x); // 第一个 x 的元素的迭代器 s.upper_bound(x); // 第一个 x 的元素的迭代器5.2 时间复杂度插入、删除、查找、二分均为 O (logn)。5.3 竞赛适用情形需要去重 自动排序的场景动态维护有序集合快速查找前驱、后继离散化数据处理需要支持删除任意元素的堆场景。5.4 注意事项巨坑预警元素不可修改要修改某个元素必须先删除旧值再插入新值erase的坑s.erase(值)会删除所有等于该值的元素如果只想删一个必须传迭代器s.erase(s.find(x))find找不到元素会返回end()解引用*s.end()会 RE使用前必须判断。6. map multimap 有序映射键值对结构底层红黑树按 key 自动升序排序key 唯一不重复multimap允许 key 重复。可以理解为「下标可以是任意类型的数组」。头文件#include map6.1 常用方法cpp运行mapstring, int mp; mp[apple] 1; // 支持[]直接访问赋值 mp.insert({banana, 2}); // 插入键值对 mp.erase(key); // 删除键为key的元素 mp.find(key); // 查找key返回迭代器找不到返回mp.end() mp.count(key); // 返回key的出现次数map中为0或1 mp.size(); // 键值对个数 mp.empty(); // 是否为空 mp.clear(); // 清空6.2 时间复杂度插入、删除、查找、下标访问均为 O (logn)。6.3 竞赛适用情形字符串 / 复杂类型映射到数字编号统计元素出现次数mp[x]一行搞定离散化、字典序相关题目需要按 key 有序遍历的键值对场景。6.4 注意事项[]的副作用如果 key 不存在访问mp[key]会自动插入一个默认值如 int 默认 0单纯查找时建议用find避免多余插入key 是只读的不能修改只能删除后重新插入遍历方式cpp运行for(auto p : mp) { cout p.first p.second endl; }7. string 字符串专门处理字符串的容器比 C 风格 char 数组便捷得多支持大量内置操作。头文件#include string7.1 常用方法cpp运行string s1 hello; string s2(5, a); // 生成5个a组成的字符串 s1 world; // 字符串拼接 s1.push_back(!); // 尾部追加字符 s1.pop_back(); // 删除尾部字符 s1.size(); // 字符串长度 s1.empty(); // 是否为空 s1.clear(); // 清空 s1.substr(pos, len); // 从pos位置开始截取长度为len的子串 s1.find(ll); // 查找子串首次出现的位置 s1.erase(pos, len); // 从pos开始删除len个字符 s1.insert(pos, xx);// 在pos位置插入字符串 s1.c_str(); // 转成C风格char*用于printf输出7.2 竞赛适用情形所有字符串处理类题目高精度运算用 string 存大数字符串匹配、模拟类题目。7.3 注意事项substr的第二个参数是长度不是结束位置新手极易写错find找不到子串会返回string::npos判断时要写if(s.find(xx) ! string::npos)支持下标访问s[i]从 0 开始。8. pair 二元组把两个元素打包成一个整体是竞赛里最常用的「简易结构体」支持自动比较排序。头文件大部分 STL 头文件已自动包含无需额外引入。8.1 基础用法cpp运行pairint, int p1; // 默认构造两个值均为0 pairint, string p2(1, ok); auto p3 make_pair(2, 3); // 自动推导类型竞赛推荐写法 int a p3.first; // 访问第一个元素 int b p3.second; // 访问第二个元素8.2 比较规则pair 可以直接比较大小先比较first相等时再比较second。因此 pair 可以直接放进 set、priority_queue或者配合 sort 排序。8.3 竞赛适用情形存储坐标点(x,y)Dijkstra 中存(距离, 节点编号)向 map 中插入键值对需要两个元素绑定排序的场景。9. 迭代器 Iterator迭代器是 STL 容器的通用访问方式可以理解为指向容器元素的指针所有有序容器都支持迭代器遍历。9.1 基础用法cpp运行vectorint arr {1,2,3,4,5}; auto it arr.begin(); // 指向第一个元素的迭代器 auto end arr.end(); // 指向最后一个元素的下一个位置尾后迭代器 *it; // 解引用获取迭代器指向的元素 it; // 移动到下一个元素9.2 两种遍历写法cpp运行// 写法1迭代器遍历所有容器通用 for(setint::iterator it s.begin(); it ! s.end(); it) { cout *it endl; } // 写法2范围forC11及以上简洁竞赛推荐 for(auto x : s) { cout x endl; }9.3 注意事项迭代器失效vector 插入 / 删除元素后原有迭代器会失效set/map 插入不会失效删除当前迭代器会使其失效end()是尾后迭代器不指向任何有效元素绝对不能解引用。10. 竞赛必背配套算法位于algorithm头文件和 STL 容器搭配使用频率极高sort(begin, end)默认升序排序时间复杂度 O (nlogn)lower_bound(begin, end, x)查找第一个 x 的位置返回迭代器upper_bound(begin, end, x)查找第一个 x 的位置返回迭代器next_permutation(begin, end)生成下一个全排列unique(begin, end)去重需先排序返回去重后的尾迭代器