作为一个常年泡在算法竞赛里、靠STL吃饭的老选手我太清楚容器用得好能省多少事了。很多人觉得STL就是个“工具库”用的时候翻一眼文档就行了但真正到了赛场上面对一秒的时间限制和可能爆掉的内存你对容器的理解深度直接决定了代码的成败。这篇东西不是给你念文档而是把我自己在刷题和比赛里反复踩过、验证过的STL容器常用基本操作做了个汇总把那些最容易被忽略、最容易出错的点全部翻出来讲透希望能帮你少走点弯路。1. 认知框架与选型思维1.1 竞赛场景下的容器选型逻辑先说个很实在的问题为什么竞赛里大家都爱用STL一个字快。这个快不是指运行速度而是开发速度。一场比赛三四个小时你有多少时间花在写平衡树、写链表、写哈希表上STL把最常用的数据结构都封装好了你只需要关心怎么用不需要关心怎么实现。但正因为用起来太顺手很多人反而忽略了它背后的代价。选容器之前你脑子里得先过一遍三个问题需要随机访问吗需要频繁在中间插入删除吗需要有序性吗这三个问题的答案基本就锁定了容器的范围。比如你要维护一个滑动窗口的极值那deque几乎是唯一选择要频繁判断元素是否存在且数据范围大到数组开不下那就得上unordered_set或者set要做Dijkstra最短路priority_queue加pair是标配。我见过不少新手写题的时候压根不想这些随手定义一个vector就往里塞等发现超时了才回头改。其实选容器的功夫花在前面后面能省大量调试时间。我的习惯是拿到题先分析数据规模和时间限制估算每个操作需要什么复杂度再决定容器类型。这个习惯一旦养成你的解题速度会明显提升。1.2 底层结构与操作复杂度对照理解容器操作的时间复杂度是竞赛选手的基本功。这里有一个很关键的认知STL各容器底层的物理结构天差地别复杂度也就完全不同。vector连续内存支持O(1)随机访问尾部插入删除均摊O(1)中间插入删除O(n)。deque分段的连续内存支持O(1)头尾插入删除随机访问O(1)但常数比vector大不少。list双向链表不支持随机访问任意位置插入删除O(1)但需要O(n)找到那个位置。set/map/multiset/multimap红黑树插入删除查找都是O(log n)且自动有序。unordered_set/unordered_map哈希表插入删除查找均摊O(1)但无序且常数较大。priority_queue二叉堆插入和弹出O(log n)堆顶O(1)访问。stack/queue默认基于deque实现的适配器操作都是O(1)。这张表你得刻在脑子里。我经常看到有人用list去做需要随机访问的题那复杂度直接炸裂也有人用vector模拟栈和队列其实用stack和queue更清晰代码也更不容易出错。另外注意unordered系列虽然号称O(1)但它有哈希碰撞的风险极端数据下可能退化到O(n)。竞赛里有些题专门卡这个你后面会看到我具体怎么处理。2. 顺序容器操作精讲2.1 vector核心操作与性能陷阱vector是STL里出场率最高的容器没有之一。原因很简单连续内存随机访问极快而且能动态扩容。但很多人对vector的理解停留在“会用push_back”和“会用[]访问”这个层面这还远远不够。先讲初始化。除了默认构造你还会用到带大小的构造、带初值的构造、以及通过迭代器区间构造vectorint a; // 空vector vectorint b(10); // 10个0 vectorint c(10, 5); // 10个5 vectorint d(b.begin(), b.end()); // 用b的所有元素构造 int arr[] {1, 2, 3}; vectorint e(arr, arr 3); // 从数组构造再看修改操作。push_back是均摊O(1)的但如果你要提前知道元素个数最好先用reserve预留空间。这个操作很多人不理解为什么重要我举个例子你要往vector里塞100万个int如果不reservevector会多次扩容——每次扩容是倍增的也就是1变22变44变8……看起来扩容次数不多也就20次左右但每次扩容都要把旧内存里的全部元素搬到新内存去这个搬运开销会累加。你提前reserve(1000000)直接就避免了所有搬运。还有一个高频操作是erase。注意erase在vector中间删除是O(n)的因为后面的元素要往前面移动。如果你需要频繁删除中间元素vector并不是好选择。vectorint v {1, 2, 3, 4, 5}; v.erase(v.begin() 2); // 删掉第2个元素也就是3 v.erase(v.begin(), v.begin() 2); // 删除前两个元素这里有个巨大的坑erase之后迭代器会失效。上面的代码里v.erase(v.begin() 2)执行完之后之前存的所有迭代器、指针、引用除了指向被删元素后面位置的基本都失效了。如果你在循环里一边遍历一边删必须特别小心。还有个容易被忽视的操作是insert。vector的insert可以在任意位置插入但同样是O(n)。如果你需要在中间大量插入list或者deque更合适。另外insert的迭代器参数同样会失效这点我在后面专门讲迭代器失效的章节再展开。最后说一个竞赛里非常实用的小技巧用vector模拟栈。有些人觉得反正有stack何必用vector。但vector的优势是可以通过下标随机访问栈内任意元素这在某些回溯算法里特别方便比如你需要查看栈底或者修改栈中某个元素时stack根本做不到vector却可以直接v[i]访问。2.2 deque与list的适用场景deque中文叫双端队列头尾操作都是O(1)。它的应用场景非常集中滑动窗口、双向BFS、需要两头操作的队列。滑动窗口问题是deque的经典战场。你需要维护一个窗口里的最大值或最小值单调队列的实现就依赖deque的两头操作。具体做法是遍历数组用一个双端队列存下标保证队首是当前窗口的最大或最小元素每次新元素进来从队尾弹出所有比它小或大的元素同时从队首弹出已经滑出窗口的下标。dequeint dq; for (int i 0; i n; i) { while (!dq.empty() a[dq.back()] a[i]) dq.pop_back(); dq.push_back(i); while (!dq.empty() dq.front() i - k) dq.pop_front(); if (i k - 1) cout a[dq.front()] ; }这段代码就是典型的滑动窗口最大值模板说实话背下来不丢人因为它太常用了。再来看list。说实话list在竞赛里的出场率并不高一是因为它的常数太大二是因为竞赛题很少要求你维护一个需要频繁在中间插入删除的序列。但有一种情况list很有用当你需要在多个容器之间搬移元素又不希望元素反复拷贝时。list的splice操作可以在O(1)时间内把一个链表的一段拼接到另一个链表这是其他容器做不到的。不过我的建议是一般情况下别碰list。它的每个元素单独分配内存在内存里东一块西一块链表的节点在遍历时cache miss率极高实际跑起来往往比vector慢好几倍。竞赛选手要对“常数”敏感list的常数在STL容器里属于偏大的那一档。3. 关联容器与无序容器实战技巧3.1 set与map基本操作与细节set和map内部都是红黑树元素自动有序操作复杂度都是O(log n)。竞赛里经常用它们来维护有序集合、做离散化、查找前驱后继等等。set的基本操作就是插入、删除、查找和遍历setint s; s.insert(5); s.insert(2); s.insert(8); s.erase(5); auto it s.find(2); // 查找返回迭代器找不到返回end() bool has s.count(2); // 判断是否存在返回1或0 s.lower_bound(3); // 返回第一个 3 的元素的迭代器 s.upper_bound(3); // 返回第一个 3 的元素的迭代器注意set的insert返回值是pairiterator, boolbool表示是否插入成功。这个在去重场景下很好用if (s.insert(x).second) { // x是第一次出现 }map则是在set的基础上增加了一个键值对映射。常用操作也不多但有一个点经常有人出错用[]访问不存在的键时map会自动创建这个键并赋默认值。这个特性有时候很方便比如统计词频mapstring, int cnt; for (auto word : words) cnt[word];但有时候会带来麻烦。如果你只是想查一下某个键存不存在用了[]就会多插入一个空元素。这时候要用find或countif (mp.count(key)) { ... } // 判断存在 auto it mp.find(key); // 查找 if (it ! mp.end()) { /* 读it-second */ }再强调一个竞赛里的重要操作遍历map的时候是按键有序的。这个特性可以帮你省去排序的步骤比如你想按字典序输出统计结果直接用map就能搞定。另外multiset和multimap允许重复键在需要维护可重复集合的场景比如对顶堆问题里很有用。但注意erase的时候如果你写s.erase(x)它会删除所有等于x的元素而s.erase(s.find(x))只删一个。这两个的区别在竞赛里能直接决定你代码对不对。3.2 unordered系列与自定义哈希unordered_set和unordered_map底层是哈希表查找插入都是均摊O(1)比红黑树快得多。但正如我前面说的它有哈希碰撞的风险。在竞赛里最常见的坑是这样的某个题的数据故意设计成大量哈希碰撞导致你的unordered_map退化到O(n)直接超时。怎么解决两个办法一是换成set/map用O(log n)换保险二是自定义哈希函数打乱默认的哈希规则。我常用的自定义哈希写法是这样struct custom_hash { static uint64_t splitmix64(uint64_t x) { x 0x9e3779b97f4a7c15; x (x ^ (x 30)) * 0xbf58476d1ce4e5b9; x (x ^ (x 27)) * 0x94d049bb133111eb; return x ^ (x 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x FIXED_RANDOM); } }; unordered_mapint, int, custom_hash mp;这个模板网上流传很广原理是引入随机种子再通过位运算打散原始哈希值让攻击者无法预测你的哈希分布。说实话竞赛里只要数据范围不是特别大大多数情况下直接用默认哈希也不会出事。但一旦遇到专门构造的数据你有这个模板就能救自己一命。另外注意unordered系列的迭代器遍历是无序的如果你需要按序输出老老实实把元素倒到vector里排序。3.3 priority_queue深度用法priority_queue优先队列底层是二叉堆默认是大根堆也就是堆顶是最大的元素。竞赛里很多要用到贪心、Dijkstra、哈夫曼编码的场景都靠它。基本用法priority_queueint pq; // 大根堆 pq.push(3); pq.push(1); pq.push(5); int x pq.top(); // 5 pq.pop(); priority_queueint, vectorint, greaterint minHeap; // 小根堆这里有个语言细节要讲清楚priority_queue的模板参数有三个第一个是元素类型第二个是底层容器第三个是比较器。默认情况下底层容器是vector比较器是less。现在Compare为less时它是个大根堆这是因为堆顶始终是Compare比较逻辑下的“最大”元素。你要是想用小根堆就得把Compare换成greater。但竞赛里更常见的是存结构体比如Dijkstra里要存“当前距离节点编号”这样的pair默认的pair比较是先比第一个再比第二个。这样如果你用pairint,int堆顶会优先取距离最大的所以你要存距离的相反数或者自定义比较器priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; pq.push({0, start}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] true; for (auto [v, w] : g[u]) { if (dist[v] d w) { dist[v] d w; pq.push({dist[v], v}); } } }这段代码是Dijkstra的标准写法pair默认小根堆距离最小的在堆顶。注意里面有个vis数组的判断这是为了避免同一个节点被重复松弛导致的大量无用计算。还有一个自定义比较器的写法要说明它和sort里的lambda不太一样。priority_queue的比较器类型需要在模板里指定不能直接用lambda临时对象需要用decltypeauto cmp [](const Node a, const Node b) { return a.w b.w; }; priority_queueNode, vectorNode, decltype(cmp) pq(cmp);注意这个cmp的返回值和你的直觉是反的返回true表示a的优先级低于b。如果你觉得绕最简单的方法是直接重载结构体的运算符然后默认用大根堆效果一样。4. 常用操作技巧与陷阱排查4.1 迭代器失效场景详解迭代器失效是STL里最容易出bug的地方而且这种bug一旦出现极难排查。我在这里把各容器迭代器失效的情况给你总结清楚。vector和string插入或删除操作后所有指向该元素及之后的迭代器、指针、引用都可能失效。扩容后所有迭代器都失效。典型错误写法// 错误示例在for循环里erase for (auto it v.begin(); it ! v.end(); it) { if (*it % 2 0) v.erase(it); }这段代码之所以错是因为erase之后it已经失效了再执行it就是未定义行为。正确的写法是用迭代器接收erase的返回值它指向被删元素的下一个元素for (auto it v.begin(); it ! v.end();) { if (*it % 2 0) it v.erase(it); else it; }deque在中间插入或删除会让所有迭代器失效在头部尾部操作则只影响被操作位置的迭代器。list、set、map、unordered系列删除操作只让指向被删元素的迭代器失效其他迭代器不受影响。注意这里有个很常用的写法mapint, int mp; for (auto it mp.begin(); it ! mp.end();) { if (it-second 0) it mp.erase(it); else it; }这个写法是安全的因为map的erase返回被删元素的下一个元素的迭代器。但要注意成员函数erase返回迭代器这个特性是从C11才有的老版本编译器可能不支持。4.2 排序与查找的组合应用排序是竞赛里绕不开的操作STL里的sort是基于快排的优化版本平均复杂度O(n log n)。但sort不是稳定的排序如果你需要稳定排序用stable_sort。sort的基本用法sort(a.begin(), a.end()); // 默认升序 sort(a.begin(), a.end(), greaterint()); // 降序 sort(v.begin(), v.end(), [](const Node a, const Node b) { if (a.x ! b.x) return a.x b.x; return a.y b.y; }); // 自定义规则这里有个细节sort的比较器必须满足严格弱序strict weak ordering要求也就是对于任意两个元素比较结果不能自相矛盾。最常见的错误是写return a b原因是在等价的情况下返回true会导致sort出现未定义行为。正确写法永远是return a b这种严格小于。查找方面lower_bound和upper_bound是在有序序列上做二分查找复杂度O(log n)auto it lower_bound(v.begin(), v.end(), x); // 第一个 x 的位置 auto it upper_bound(v.begin(), v.end(), x); // 第一个 x 的位置 int pos it - v.begin(); // 转成下标这个组合在竞赛里的用法太多了。比如有一个有序数组你要统计一个区间[l,r)内有几个数落在[L,R]之间就是两行代码的事。再比如你要在数组里插入一个元素并保持有序可以先找插入位置再insert。但记住lower_bound必须配合有序数组使用如果你在无序数组上调用结果完全是垃圾。4.3 字符串处理与容器转换string虽然是容器但它有一些专属操作需要单独掌握。竞赛里字符串处理非常常见我把最常用的几个列出来。子串截取string s hello world; string sub s.substr(0, 5); // hello查找size_t pos s.find(world); // 找不到返回npos if (pos ! string::npos) { ... }拼接和比较直接用和比较运算符string重载了这些操作非常方便。数字和字符串互转这是个高频需求int x stoi(123); // 字符串转int long long y stoll(123); // 字符串转long long string s to_string(123); // 数字转字符串注意stoi这些函数在遇到非法输入时会抛异常竞赛里一般数据没问题所以直接用就行不用try-catch。但要注意如果数字太大stoi会爆int要用stoll。还有split操作标准库没有直接提供split但可以用getline配合istringstream实现string s a,b,c; istringstream ss(s); string token; vectorstring parts; while (getline(ss, token, ,)) { parts.push_back(token); }如果你需要把字符数组转成string直接用构造函数string s(arr)。反过来string转字符数组用s.c_str()但注意c_str返回的指针是只读的不能用来修改字符串内容。5. 高频竞赛场景的容器组合拳5.1 典型例题场景拆解只讲容器用法不讲题总觉得少了点什么。我这里挑几个最典型的竞赛场景看看容器是怎么组合起来的。第一个是“合并区间”类题目。给定一堆区间把有重叠的合并。做法是先用vector存区间然后按左端点排序再依次遍历合并vectorpairint, int segs; sort(segs.begin(), segs.end()); vectorpairint, int res; for (auto [l, r] : segs) { if (res.empty() || l res.back().second) { res.push_back({l, r}); } else { res.back().second max(res.back().second, r); } }这里用到了vector的排序、back()访问、pair比较等操作一气呵成。第二个是“对顶堆”求动态中位数。这个场景需要一个大根堆存较小的一半一个小根堆存较大的一半两个堆的总和就是整个序列。核心操作是每次插入新数后保持两个堆的大小平衡并确保大根堆堆顶小于等于小根堆堆顶priority_queueint down; priority_queueint, vectorint, greaterint up; // 插入x后调整 if (down.empty() || x down.top()) down.push(x); else up.push(x); if (down.size() up.size() 1) { up.push(down.top()); down.pop(); } if (up.size() down.size()) { down.push(up.top()); up.pop(); }这里两个priority_queue就完成了有序序列的维护非常简洁。第三个是“滑动窗口第K大”这个可以用multiset实现。multiset是红黑树有序且支持重复元素维护窗口时插入新元素、删除滑出的元素然后用迭代器找到第K大。这个方案虽然比单调队列慢但代码简单得多适合应对不是最卡时间的题。5.2 空间与时间开销的把控竞赛中的时间限制通常卡得很紧有时候你的算法复杂度没错但就是因为常数太大过不了。STL容器之间常数差异很大我经验总结如下从快到慢大致是vector unordered_set/unordered_map deque set/map list。vector是最快的因为连续内存cache友好。unordered系列虽然O(1)但哈希计算也有开销。set/map基于红黑树每次操作都是指针跳转cache miss严重。还有一个很容易被忽视的点容器复用可以显著提速。如果你在一个循环里反复创建小容器比如100万次循环里每次new一个vector那光是分配内存的开销就能拖垮整个程序。正确做法是把容器定义在循环外每次用clear()清空再使用。注意clear()不会释放容量所以复用的时候不会重新分配内存vectorint tmp; for (int i 0; i n; i) { tmp.clear(); // 往tmp里塞数据处理... }这个技巧在BFS、DFS需要维护临时状态时特别有用。另外要养成习惯能用int不用long long能用数组不用vector。有些题对空间限制很严格vector的容量是2的幂次增长可能造成空间浪费。当你明确知道元素上限时用普通数组反而更安全。6. 常见问题与避坑实录6.1 高频问题的报错与根源我在训练和点评里积累了不少大家常犯的STL错误这里按现象列个速查表。现象可能原因解决办法编译报错no match for operator[]对const容器使用了非const的[]使用find或at()运行时崩溃Segmentation fault迭代器失效后继续使用按第4.1节原理重新设计循环输出结果乱序用了unordered系列但期望有序输出遍历后排序或改用set/mapsort结果不对比较器不满足严格弱序确保只使用或不使用或栈溢出递归层数太深或容器占用栈空间太大大数组定义成全局变量erase后死循环erase之后迭代器未更新使用it container.erase(it)用[]访问map导致意外插入误用了operator[]改成find或count还有一个经常碰到的坑是vector 。这个容器不是标准vector它对bool做了位压缩所以v[i]返回的是一个代理对象不是bool。这会导致一些操作出问题比如你写auto isTrue v[0]得到的是一个奇怪的代理类型而不是bool。竞赛里建议直接用vector 或者bitset代替vector 。6.2 我的调试经验与习惯最后分享几个我自己在实战中养成的习惯算不上什么高明技巧但确实帮我避免了很多无意义的debug时间。第一写完后立刻检查容器操作是否可能越界。比如用v[i]前确认i v.size()用pq.top()前确认!pq.empty()用it-second前确认it ! container.end()。这些检查在思路里过一遍比事后调试快得多。第二善用auto减少类型错误。特别是multiset的迭代器类型、unordered_map的迭代器类型手写完整类型太容易出错。auto既能少打字又能避免类型不匹配导致的编译问题。但注意auto在循环里要用引用否则会拷贝元素尤其容器元素是大结构体时拷贝开销会拖慢程序for (auto [key, val] : mp) { ... } // 用引用避免拷贝 for (const auto item : v) { ... } // 只读访问也用const引用第三竞赛结束前留时间去跑极端数据。我给自己的规矩是写完题至少找一组最大规模的数据测试看会不会超时、会不会内存爆掉。很多时候你以为写对了一测就发现容器退化严重或内存超限。STL容器这东西说白了就是经验活。你用得多了自然就会在某些题目里条件反射地选出最合适的容器。多看别人的代码也很有帮助尤其是那些时间卡得极紧的题解旁边能附上复杂度分析能学到很多教科书上没有的细节处理。希望这篇汇总能帮你建立自己的“STL容器操作地图”在赛场上少一些犹豫多一些从容。