搞竞赛的都清楚，算法思路想明白只是第一步，真正让代码“跑得起来、交得上去”的，往往是你对STL容器操作的熟练程度。STL容器在竞赛里承担的角色很实在：帮你省掉手写平衡树、手写堆、手写链表的那些体力活，把时间留给核心逻辑。无论你是刚开始刷模拟题，还是已经在为各类算法竞赛备赛，熟悉常用容器的基本操作，都能让你在赛场上少很多卡壳瞬间。
我第一次参加校级选拔赛时，就栽在priority_queue自定义排序上，当场折腾了十分钟没调出来。后来把容器基本操作按“建、插、查、删、遍历”五个动作归纳成套路，再遇到同类结构题基本不慌。这篇分享就把我整理出来的STL容器竞赛常用基本操作全部梳理一遍，从选型思路到具体写法，再到容易翻车的细节，一次性说透。
1. 为什么竞赛里STL容器的熟练度直接决定你能否“写完即对”
1.1 STL容器在竞赛中的定位：不再手写，把精力留给算法本身
很多初学者容易陷入一个误区，觉得STL是“偷懒工具”，会基本操作就行。实际完全不是这样。竞赛里高频考察的图论、贪心、二分、动态规划，几乎都要借助容器来承载状态和中间结果。如果你能像背自己的名字一样背出容器操作，写题速度会快很多；反过来，如果你在赛场上还要查文档回忆lower_bound返回的是迭代器还是下标，心态很容易崩。
我个人的体会是，STL容器在竞赛中承担的职责可以分成三类：序列容器负责存储和索引、容器适配器负责模式化存取、关联容器负责有序或快速查找。理解这个定位之后，你会发现很多题其实根本不需要自己设计数据结构，直接用现成容器组合就能达到要求的时间复杂度。
1.2 选容器的核心判据：序列、适配、关联，三个维度先想清楚
比赛时拿到一道题，不要急着敲代码，先花三十秒想清楚数据需要怎么存取。如果只关心按顺序遍历，vector足够；如果一侧插入删除频繁，deque或list更合适；如果需要先进后出直接用stack，先进先出用queue，每次取最大或最小用priority_queue；如果要在有序集合中查找、删除、求前驱后继，set和map就是标准答案。但这里有个很关键的思维习惯：容器不是越复杂越好，而是越匹配越好。
举个我常举的例子，判断数组中是否存在重复元素，有人会开一个map统计次数，也有人会用unordered_set直接插入顺便去重。如果题目只要求判断存在性，unordered_set的O(1)插入查找最舒服；但如果后续还要求输出有序去重结果，那set反而一步到位。选容器本质是在权衡时间、内存和代码复杂度三者之间的关系，这个判断能力比背任何操作都重要。
2. vector和string：竞赛中使用率最高的两个容器
2.1 vector常用操作与复杂度记忆表
vector应该算竞赛里出现频率最高的容器，没有之一。它本质是动态数组，支持随机访问，也和数组一样能用下标操作。基础构造包括vector v直接创建空向量、vector v(n)创建长度为n的向量、vector v(n, x)创建n个初始值为x的元素。添加元素用push_back()，删除末尾元素用pop_back()，这两者均摊复杂度都是O(1)，也是vector最核心的两个入口。
vector的下标访问和迭代器访问都要熟练。v[i]适合直接随机读，begin()和end()配合sort、lower_bound这类算法是竞赛中的标准动作。要注意size()返回的是size_t类型，如果不加处理直接和负数比较会产生很隐蔽的bug。我自己处理这类问题时习惯写成if ((int)v.size() > n)这种显式转换，虽然代码看着没那么优雅，但至少不会踩无符号比较的坑。
vector还提供insert和erase操作，但因为底层原理是数组，除末尾外插入和删除都需要搬移元素，最坏复杂度是O(n)。竞赛里如果要做大量中间插入删除，一定不要死磕vector，换list甚至直接手写数组更稳。另外，vector的clear()只会清空元素不会释放内存，比赛内存紧张时可以用vector ().swap(v)的方式来真正释放，不过多数场景下直接用局部变量作用域结束自动析构就够了。
2.2 string操作：substr、find、replace在字符串题里的常见组合
string在竞赛字符串处理题里的地位，相当于vector对数组题的地位。基本操作里，s.length()和s.size()等价，不需要区分；s.substr(pos, len)用来截取子串，特别适合处理分段解析的题目；s.find(sub)返回子串第一次出现的位置，找不到时返回string::npos，很多人栽在这里，以为返回的是-1。实际上string::npos是size_t类型能表示的最大值，直接拿它和int比较时容易出问题。
有个很推荐的组合写法：当你要反复查找并处理子串时，用pos = s.find(pattern)，然后while (pos != string::npos)持续处理，每次处理完从pos + pattern.size()开始继续找。这种模式在模拟字符串替换、去除子串的题目里非常实用。另外，字符串连接虽然可以直接用+，但如果在一个大循环里频繁拼接，尽量用s += c代替s = s + c，因为后者会产生临时对象，效率差不少。
string还有一个容易被忽视的用法，就是直接当作字符数组来用。s[i]可以修改具体字符，配合sort(s.begin(), s.end())可以对字符串排序，配合reverse(s.begin(), s.end())可以翻转。很多回文串题和排列题，直接用string会比char数组顺手太多，而且不用手动管理结尾的\0，不容易出现越界写的问题。
2.3 使用vector和string时容易被忽略的性能坑
第一个坑是reserve的使用。如果你提前知道vector要装很多元素，比如要push_back约十万个整数，最好先调用v.reserve(100000)。这样可以避免vector在扩容时反复申请内存、复制旧元素的损耗。我见过有人因为没有reserve，导致原本O(n)的插入实际跑成好几倍常数，直接在大数据点上超时。
第二个坑是用vector 。这个类型在STL里是个特殊存在，底层按位存储，返回的引用是代理对象，不能像普通bool那样直接取地址。竞赛里如果只是想开一个标记数组，最好用vector 或者bitset，省得在语法细节上浪费排查时间。同理，string的reserve也需要按需使用，因为字符串拼接的频繁扩容会让均摊复杂度变差。
第三个坑是拷贝开销。vector和string被当成参数传给函数时是深拷贝，代价不小。竞赛里常见做法是函数传引用或者传指针，比如void dfs(vector & v)。有人刚接触STL时习惯写值传递，数据量小看不出来，数据量一大就会平白多出大量内存复制，轻则超时，重则生成临时对象导致额外空间耗尽。
3. stack、queue、deque与priority_queue：适配器容器的正确打开方式
3.1 stack和queue的基本操作与典型应用场景
stack在竞赛中最经典的应用就是括号匹配、单调栈、表达式求值和深搜辅助栈。基本操作只有push、pop、top、empty、size这几个，注意pop只删除元素不返回值，如果写int x = st.pop()会直接编译报错。正确写法是先int x = st.top()，再st.pop()。这个细节看起来基础，但在模拟单调栈的题目里特别容易手滑。
queue的应用主要是广搜和按层处理。操作包括push入队、pop出队、front取队首、back取队尾。BFS模板里几乎固定就是q.push(start)、访问队首、逐层pop，直到queue为空。需要提醒的是，queue没有迭代器，不能随机访问，如果你想看队内某个元素，必须按顺序取出来再放回去，这在实际问题中通常说明你选错容器了。
如果既需要队首操作又需要队尾操作，优先考虑deque。deque支持push_front、pop_front、push_back、pop_back，还支持下标访问，虽然随机访问性能比vector稍弱，但双端操作都是O(1)。滑动窗口最大最小值这类经典题，标准解法就是deque维护单调结构，两端的回缩和插入都极其自然。
3.2 priority_queue的定义、自定义比较器与堆的替代关系
priority_queue是竞赛中手写堆的最佳替代品，默认是大根堆，也就是top()返回最大元素。基本操作是push、pop、top、empty、size，没有clear，如果需要清空，直接重新定义一个新的优先队列对象。由于top是取不删、pop是删不取，要把堆顶取出来用，一样要先int x = pq.top()，再pq.pop()。
很多人最大的困惑在于如何实现小根堆和自定义排序。小根堆最简单的写法是priority_queue<int, vector , greater > pq，这个greater 是库自带的小于反器，比较好记。但要注意，自定义结构体时默认需要重载小于号。当时我在一次模拟赛里遇到按“分数高优先，分数相同按编号小优先”的排序，写错了比较器方向，导致整个堆行为完全反了，赛后才发现是大于号小于号的语义混淆。
比较器方向有个万无一失的记忆方式：仿函数内部返回true的条件，表示两个元素中谁优先被放到更低的位置。template里写的比较器返回true时，代表第一个元素优先级低于第二个元素，所以在堆顶的实际上是“按比较逻辑排最后”的元素。多写几次就习惯了，但我还是建议直接在代码里测试三到五个元素，快速验证堆顶是否符合预期，这比死记规则有效率得多。
3.3 deque的特点与双端操作使用场景
deque看起来什么都能干，既能push_front又能push_back，既能下标访问又有迭代器，但它在竞赛中往往不是首选的“全能容器”，而是用于特定双端场景的工具。它的底层实现是分段连续空间，不是像vector那样的单一连续数组，所以中间插入删除仍然较慢，但是两端操作是均摊O(1)。正因为两端都能高效操作，deque在单调队列优化动态规划里非常常用。
在实际写单调队列时，通常用deque dq存储下标而非直接存储值。每处理一个新元素，先从队尾弹出所有已不具备潜力的旧元素，再把新下标压入，然后从队首取出一个合法范围内的下标作为当前答案。整个过程只用push_back、pop_back、front、pop_front，代码模版固定，不容易出错。用deque存下标这个习惯，能帮你减少很多数组越界和边界讨论。
deque有一个序列式容器的共性陷阱：end()指向的是末尾元素之后的位置，不是最后一个元素。访问最后一个元素应该用back()，删除最后一个元素用pop_back()。如果直接对end()解引用就是未定义行为，这种错误有时候不会立刻崩溃，但会随机污染数据，非常难排查。
4. set、map与它们的多键版本：有序容器的一整套技巧
4.1 set/multiset和map/multimap的基础操作
set和map在竞赛里主要用于需要保持数据有序的场景。set内部是红黑树，插入、删除、查找复杂度均为O(log n)，支持迭代器从小到大遍历。基础操作包括insert、erase、find、count、lower_bound、upper_bound、size、empty。find(key)会返回指向该元素的迭代器，如果找不到就返回end()。很多人习惯用count来判断是否存在，因为set和map的count只会返回0或1，这样写当然没错，但语义上find更直接一些。
multiset允许重复元素，count返回的是实际重复数量。需要注意，multiset的erase(key)会一次性删除所有等于key的元素，如果只想删除一个，必须用erase(it)，其中it是find返回的迭代器。这个坑我踩过一次，当时想弹出一个元素，结果整个等于该值的元素全没了，后面的贪心逻辑直接错掉。map和multimap同理，map的erase(key)按键删除， multimap如果只想删一个也要用迭代器。
map的基本操作更丰富，可以用m[key]直接访问，如果key不存在会自动创建并赋默认值。这一点很方便，但也意味着只查询不插入时会改变map内容，需要留意。在只读查询场景下，建议使用m.find(key)或者m.count(key)来判断是否存在，避免因为下标访问导致意外插入，影响题目中某些计数逻辑。
4.2 lower_bound/upper_bound在竞赛判定位次、区间问题中的正确姿势
在set和map上使用lower_bound和upper_bound是竞赛中很关键的操作。两者都返回迭代器，lower_bound(k)返回第一个不小于k的元素位置，upper_bound(k)返回第一个大于k的元素位置。在普通数组上是同样的语义，在有序容器上则充分利用内部结构实现O(log n)查询，而不需要像vector那样依赖二分算法底层遍历。
在处理区间查询时，我习惯的套路是：设itL = s.lower_bound(l)，itR = s.upper_bound(r)，然后从itL遍历到itR就得到了区间[l, r]内的所有元素。这个写法比逐个判断元素在不在区间里要干净很多，复杂度也稳定。另一个高频场景是求前驱和后继，找一个元素的上一个元素用prev(lower_bound(k))，找下一个元素用upper_bound(k)。但prev操作在迭代器已经是begin()时需要格外小心，迭代器递减到无效位置会导致崩溃。
对map使用lower_bound，返回的是pair<const Key, T>的迭代器，it->first是键，it->second是值。如果要找第一个不小于key的映射项，直接用auto it = mp.lower_bound(key)就够。这里有个小技巧：查找“最接近某值的键”时，可以先lower_bound，再比较一下它和前一个键的距离，哪边更近取哪边，很多最近距离类题目都能用这个思路快速求解。
4.3 自定义结构体作为key的比较器写法
很多题需要把自定义结构体放进set或map当key，这时候必须提供排序规则。比较器的本质是提供“严格弱序”，必须满足:对于a和b，comp(a,b)为true表示a排在b前面，并且不能同时存在comp(a,b)和comp(b,a)都为true的情况。结构体内部重载小于号是最常见的做法，例如按x升序、x相同按y升序，就直接return x < t.x || (x == t.x && y < t.y)。这个写法记住一个关键点，最后一定要返回false表示相等，切忌只写x < t.x而忽略y，否则相等的x不同y会被错误视为同一个元素。
如果不方便重载小于号，也可以用仿函数。比如set<Node, Cmp>，Cmp内部实现operator()重载。仿函数的好处是可以封装更复杂的比较逻辑，或者在函数外部直接复用。但要严格保证比较规则不会因为状态变化而改变，否则红黑树结构会被破坏，后续查找删除全乱套。这一点很隐蔽，我在做一道动态键值调整的题时就吃过亏，运行结果不稳定，最后才发现比较器里引用了一个会变化的外部状态。
5. unordered系列与哈希选型：追求O(1)时要付出什么代价
5.1 unordered_set/unordered_map的基本操作与适用场景
哈希容器在竞赛中负责把查找复杂度降到均摊O(1)。unordered_set的基础操作跟set对齐，insert、erase、find、count、size、empty都差不多，没有lower_bound和upper_bound，因为内部无序。unordered_map可以使用下标访问、find、count、erase，语义也和map类似，只是不保证元素有序。
使用场景很典型：需要快速判断元素是否存在、需要统计频次、需要按键快速取值的题，都优先考虑哈希容器。例如两数之和那道经典题，边遍历边把互补数放进哈希表，之后每次查询都是O(1)，整体O(n)解决。如果把同样的逻辑交给map，就会退化到O(n log n)，数据量大时有明显差异。
哈希容器也有代价。首先是常数较大，虽然理论均摊O(1)，但在小规模数据下反而不如有序容器甚至直接数组。其次是键必须可哈希，C++标准库对基本类型、string、智能指针等都提供了默认哈希，但自定义结构体要自己写哈希函数。如果数据构造极端，还可能被哈希碰撞拖慢，竞赛里如果出现这类问题，通常换map更稳妥。
5.2 哈希容器的重载哈希函数写法
当你需要把自定义结构体放入unordered_set或unordered_map时，必须提供哈希函数和相等比较。常见做法是对结构体实现operator==，再特化模板hash 。例如一个二维坐标点，可以取(x * 13331 + y)作为哈希值，配合内置的散列策略一般够用。代码通常长这样：
struct Node { int x, y; bool operator==(const Node& other) const { return x == other.x && y == other.y; } }; struct NodeHash { size_t operator()(const Node& n) const { return n.x * 13331u + n.y; } }; unordered_set<Node, NodeHash> us;需要注意的是，哈希函数返回size_t，计算时要考虑值域和溢出。有人直接用x * 100000 + y，如果y能取到很大值，可能碰撞严重。实际上竞赛里大多数题目这种简单组合都能过，但如果卡常数或数据构造比较极端，可以换更大质数或调整组合方式。相等比较必须与语义一致，哈希相同但结构体不相等与哈希不同但结构体相等都会导致容器异常行为。
5.3 什么时候该放弃哈希容器回到有序容器
有一类题目虽然名字叫“按值查”，但实际还要求按顺序输出或找前驱后继。这时哈希容器完全无能为力，必须用set或map。例如统计频率后按频率排序取前K个，就需要先map统计、再把统计结果塞到vector里排序，或者用有序容器直接维护。
还有一类题是动态维护有序序列，不断插入删除并查询第K大，这类题哈希容器根本没法做，set加维护计数器才能实现。我见过有人明明用set更简单，却为了追求哈希的O(1)硬写自定义结构，结果代码量翻倍、bug频出。选型时记住：哈希只解决“查”的问题，解决不了“序”的问题。序列有序性要求一旦出现，老老实实用红黑树容器才是正解。
另外，当你不确定评测数据是否卡哈希时，优先使用map通常更安全。很多大型评测环境下，哈希容器在数据量中等时的常数经常比想象中大，反而是平衡树稳定得多。除非题目明确要求O(n)且内存充足，否则别为了理论复杂度牺牲代码稳定度。
6. 竞赛现场最容易翻车的五个容器操作细节
6.1 迭代器失效的典型场景
迭代器失效是全STL最容易踩的坑，大多数情况出现在修改容器的同时还在用之前的迭代器。vector的insert和push_back可能触发扩容，导致所有迭代器、指针、引用全部失效；deque的插入删除也会导致迭代器失效；而set、map由于节点独立，插入删除通常只影响被删节点和相关迭代器。
我在做一次模拟题时，想在set删除某个迭代器指向的元素后，继续使用该迭代器的值，结果编译运行都没报错，但数据错得离谱。原因就是迭代器在erase后已经变成野指针，再解引用就是未定义行为。正确的删除方式是先用一个变量保存要用的值，再执行erase(it)，或者借助C++11之后的it = container.erase(it)返回下一个有效迭代器。
vector上还有一个容易被忽略的失效场景：用v.begin()作为参数传给算法，随后又执行push_back。这个瞬间就可能让原先begin()失效。所以在写涉及迭代器和算法混合用的代码时，尽量把增删操作集中到一段，避免在遍历循环里穿插修改容器的动作。
6.2 使用count还是find来判断元素是否存在的差异
对map和set来说，count和find都能判断存在性，但语义和额外开销略有差异。count返回匹配数量，在set里最多是1，在multiset里会实际统计重复个数，可能需要O(n)时间扫描相等区域。find返回迭代器，复杂度O(log n)，更能代表“查找”的本质。
实际统计频率时map直接用m[key]++最方便，但是如果只判断存在，我推荐用find(id != m.end())这种写法，因为读代码的人一眼能看出意图。有些题目中multiset的count在重复元素很多时可能超时，这时改用find或者lower_bound/upper_bound来推导当前区间长度更高效。这个小细节在数据量大时常常成为卡常数的一部分。
另外，unordered_set和unordered_map的count和find也需要辨别使用。count在重复存储的容器里同样可能扫描一长串相同哈希值的元素，虽然有哈希桶的约束，但极端情况下也有代价。整体上我习惯统一用find判断存在，只有在要统计重复数时才用count。
6.3 erase在map/set循环中的安全删除方式
在循环里删除set或map节点，新手最容易犯错。错误的写法是直接在for (auto it = s.begin(); it != s.end(); it++)内部执行s.erase(it)，然后继续it++，这时it已经失效。C++11之后可以这样写：
for (auto it = s.begin(); it != s.end(); ) { if (需要删除) it = s.erase(it); else ++it; }erase返回下一个迭代器的机制就是为这种场景设计的。multimap里按key删除全部元素直接用erase(key)，但按条件删除单个元素时同样要用迭代器删除，并且注意删除后不能继续用it。类似的问题也出现在vector的删除中，remove配合erase或者遍历中手动跳过才是正解，在循环里erase会导致后面的元素移动和迭代器失效。
6.4 容器嵌套与pair组合的访问姿势
竞赛中经常出现“map<string, vector >”“priority_queue<pair<int, int>>”“set<pair<int, int>>”这类嵌套结构。访问方式其实很统一：外层容器先通过find或begin找到内层容器，然后内层容器再按自己的规则操作。比如map<string, vector >，要往某个key对应的vector里加元素，直接mp[key].push_back(x)即可，原来的键不会重复插入，但如果只是查询就一定先判断是否存在。
在priority_queue里放pair有个默认顺序，那就是先比较first再比较second。多数竞赛题需要按“值、下标”存储，直接priority_queue<pair<int, int>>即可让堆按值排序，值相同按下标排。如果需要特定规则，比如要求最小值优先，就换成greater<pair<int, int>>。使用pair时还有一点值得记住：可以用auto [val, idx] = pq.top()这种结构化绑定语法，很省事，但要注意结构化绑定拷贝的语义。
嵌套多层的时候，代码可读性会下降，我一般会给嵌套容器起别名。比如using NodeMap = map<string, vector >; 这样后面写NodeMap::iterator时就不用写一大堆尖括号。合理地用别名并不是偷懒，而是降低出错率，尤其在比赛手速很快的情况下，少敲一些模板类型就是少一分出错的概率。
6.5 自定义排序与比较器的不稳定因素
很多排序类问题会要求“相同分数按名字字典序”“先按时间升序再按优先级降序”。这种规则写在sort的比较函数里比写在结构体重载符里灵活。sort自定义比较器是一个普通函数或lambda，不要用等于返回true的情况，因为sort要求比较器满足严格弱序，两个元素如果相等或等价，必须返回false。
我踩过的另一个坑是在lambda表达式里捕获外部动态数组做比较。例如：
vector<int> value(n); sort(id.begin(), id.end(), [&](int a, int b) { return value[a] > value[b]; });这种写法没问题，但前提是value中途不能被修改。如果排序对象依赖不断变化的全局状态，排序结果就会完全不可控。还有一点：比较器一定要接受const引用参数，避免值拷贝带来的性能损失，在多元素排序上这点差别很明显。
7. 从零开始的一份“容器速查清单”与最终建议
7.1 我建议你背下来的容器操作速查表
经过多次比赛实践，我把最常用的操作浓缩成一张速查表，下面列出的是我每次模拟赛前都会快速扫一遍的内容。
| 容器 | 关键操作 | 复杂度 | 主要用途 |
|---|---|---|---|
| vector | push_back, pop_back, operator[], size, clear | 尾部O(1)，随机访问O(1) | 动态数组、邻接表、排序 |
| string | substr, find, +=, operator[], length | find O(n)，拼接均摊O(1)内 | 字符串处理、模拟题 |
| stack | push, pop, top, empty | O(1) | 单调栈、括号、DFS辅助 |
| queue | push, pop, front, back | O(1) | BFS、层序处理 |
| deque | push_front, pop_front, push_back, pop_back | 两端O(1) | 单调队列、滑动窗口 |
| priority_queue | push, pop, top, empty | 入堆出堆O(log n) | 贪心、哈夫曼、Dijkstra堆优化 |
| set / multiset | insert, erase, find, lower_bound, upper_bound | O(log n) | 有序去重、前驱后继、区间遍历 |
| map / multimap | operator[], insert, find, count, lower_bound | O(log n) | 键值映射、统计、排序辅助 |
| unordered_set / unordered_map | insert, erase, find, count | 均摊O(1) | 查重、快速映射、Hash映射 |
这张表不是让你机械背诵，而是帮你形成条件反射：看到“求最大最小”想priority_queue，看到“去重排序”想set，看到“是否存在/频次统计”想unordered_map，看到“按大小找边界”想map的lower_bound。把这些对应关系练成肌肉记忆之后，再做真题会觉得顺畅很多。
7.2 最后一点实战体会
其实STL容器操作本身不难，难的是在高压环境下用对、用准。我个人从踩坑到熟练的经历证明，最有效的训练方式不是背文档，而是给自己设限：连续刷五十道题，全部只准用STL容器，不手写平衡树和堆。这个过程会逼你反复练习自定义比较器、迭代器删除、嵌套访问等高频动作，练完基本就能形成条件反射。
如果你现在还是偶尔要在priority_queue比较器上卡壳，或者对set的erase迭代器写法不自信，我的建议很简单：把这些写法直接存进自己的代码模板。比赛允许使用事前准备的头文件和代码片段，一份整理好的常用容器模板可以帮你省下大量现场查错时间。但模板一定要自己敲一遍，理解每一行在干什么，否则调大赛场上的未知bug会更痛苦。希望这篇关于STL容器竞赛常用基本操作的梳理能帮你少走一些弯路，也祝你下次模拟赛写容器的时候，手稳心不慌。
