整理C提高篇的笔记时STL常用容器这一块是我花时间最多、回头补看次数也最多的章节。基础语法阶段只要记住规则就行但容器不一样——它是每天都要用的工具而且用不好不会报错只是程序变慢、内存变大、甚至莫名崩溃。这篇笔记围绕STL里最常用的九个容器展开string、vector、deque、stack、queue、list、set/multiset、map/multimap把每个容器的特点、常用接口、底层逻辑和实操里容易踩的坑一次说透。如果你是刚学完C基础、准备进入提升阶段的自学者或者平时容器用得多但没仔细想过为什么这篇应该能帮你把散落的知识点串成一条完整的线。1. 先给九个容器分好类序列式、关联式和适配器各管什么1.1 序列式容器数据摆成一排但排列方式差别很大STL容器最常见的分类口径是三种序列式容器、关联式容器和容器适配器。序列式容器包括vector、deque、list它们的特点是数据在逻辑上线性排列元素之间有明确的前后顺序而且这个顺序由你来控制——插入到哪个位置它就在哪个位置。vector的底层是一块连续内存跟数组类似。尾插尾删效率极高但中间插入删除要搬动后面所有元素它的优势是可以像数组一样按下标随机访问而且遍历时CPU缓存命中率很高。deque是双端队列底层由分段的连续内存拼接而成头尾插入删除都是O(1)随机访问比vector慢一点但比list快得多。list是双向链表每个元素单独分配节点靠前后指针连接已知位置的情况下任意插入删除都是O(1)代价是不支持随机访问要查某个元素只能从头遍历。1.2 关联式容器数据自带一套排序和查找系统关联式容器包括set、multiset、map、multimap。它们的共同点是底层用红黑树实现元素插入后自动按key排序。set和multiset存的是单个值map和multimap存的是键值对pair。set的值本身就是key自动去重、自动升序multiset允许重复值map的key唯一每个key对应一个valuemultimap的key可以重复。1.3 容器适配器不直接存储数据只是包装其他容器容器适配器包括stack、queue、priority_queue这个概念很多初学者会忽略。适配器的含义是不自己实现存储逻辑而是基于某个已有容器封装一层接口把能用的操作限制到最小——stack只允许栈顶push/popqueue只允许队尾入、队头出priority_queue每次pop出来的是优先级最高的元素。对刚接触STL的人来说这张分类表比任何接口列表都重要因为你所有关于该用哪个容器的纠结最后都会回到这张表上容器底层结构是否自动排序随机访问常规插入删除头尾操作vector连续数组否O(1)尾O(1)中间O(n)头O(n)deque分段连续否O(1)略慢中间O(n)头尾O(1)list双向链表否O(n)已知位置O(1)头尾O(1)set/multiset红黑树是不支持O(log n)无此概念map/multimap红黑树是不支持O(log n)无此概念2. string与vector最常用的两个序列容器细节全在接口背后2.1 string不是基本类型它本质上也是一个容器很多人写C时把string当基本类型用其实string的本质是一个管理字符数组的类模板它同样拥有begin()/end()、size()/empty()这些容器标配接口。与vector 相比string针对字符串场景加了很多便捷方法但这也意味着它继承了容器的所有坑。常用接口里我最想提醒注意这几个。find返回的是size_t类型找不到时返回string::nposnpos的值是unsigned long的最大值而不是-1。如果你把返回值存到int里再跟npos比较类型转换会带来诡异结果。substr从指定位置截取指定长度只传一个参数时截到末尾。频繁拼接字符串时尽量用reserve提前预留空间避免反复扩容引发的拷贝。#include string #include iostream int main() { std::string s hello cpp world; size_t pos s.find(cpp); if (pos ! std::string::npos) { std::cout found at pos std::endl; // 输出 6 } std::string sub s.substr(6, 3); // cpp // 提前预留空间再反复拼接 std::string result; result.reserve(100); result a; result.append(bc); return 0; }2.2 vector的扩容机制capacity和size必须分清vector的size是当前实际元素个数capacity是当前分配的内存能容纳多少元素。每次push_back导致元素个数超过capacity时vector会申请一块更大的内存通常是原来的1.5倍或2倍把旧元素全部搬移过去再释放旧内存。这个过程叫扩容是vector性能的主要成本来源。reserve(n)只分配内存不构造元素resize(n)则会实际构造或销毁元素。如果你已经大概知道要存多少元素直接reserve(n)完全可以避免反复扩容。比如一个循环里push_back十万次就算按2倍增长也要扩容十几次每次都有内存分配和大规模拷贝开销肉眼可见。提前reserve一次整个循环顺畅得多。2.3 用swap收缩vector容量还有一个常被忽略的操作vector在大批量数据清空后capacity不会自动缩小因为释放内存太昂贵。如果程序里有一个大vector跑完一轮就清空之后又长期闲置内存就白白占着。可以用一个临时空vector交换一下std::vectorint v(1000000, 7); v.clear(); // 此时v.size()是0但v.capacity()仍是百万级别 std::vectorint().swap(v); // 交换后旧数据被临时vector析构容量释放这个技巧在课程里经常一笔带过但做长时间运行的后台服务时这种内存回收真的会影响服务稳定性。2.4 vector里删除元素的正确姿势从C11开始vector的erase会返回下一个有效元素的迭代器。遍历删除时如果不接收这个返回值继续用旧迭代器自增轻则漏删元素重则未定义行为for (auto it v.begin(); it ! v.end();) { if (*it % 2 0) { it v.erase(it); } else { it; } }3. deque与list一个在头尾灵活操作一个用内存换插入删除3.1 deque分段连续内存的伪双端数组deque最大的价值是头尾都能O(1)插入删除而且支持下标随机访问。它的底层不是一整块连续内存而是由一个中控器指针数组加上若干段缓冲区组成逻辑上连续物理上分段。因为物理分段deque的随机访问比vector慢——需要先定位到哪一段缓冲区再算段内偏移。实际使用中deque尽量不要做中间插入。它中间插入同样是O(n)但分段结构导致搬动逻辑比vector更复杂真实开销常常比vector还高。deque的正确使用场景就是队头插入队尾删除这种模式。3.2 list双向链表插入删除的自由换不来按位置查找list底层是双向链表每个节点单独分配。只要迭代器已经指向目标位置插入和删除都是O(1)因为只需要修改前后节点的指针。代价就是不支持随机访问想拿到第100个元素必须从链头开始遍历。list有三个成员函数是别的容器没有的。splice可以把一个list的元素整体挪到另一个list的指定位置只需要改指针复杂度O(1)。remove直接删除所有等于某个值的元素比遍历加erase组合方便。sort是成员函数因为std::sort要求随机访问迭代器而list的迭代器是双向的只能用它自带的归并排序。std::listint l1 {3, 1, 4, 1, 5}; std::listint l2 {9, 2, 6}; l1.sort(); // l1: 1 1 3 4 5 l2.sort(); // l2: 2 6 9 l1.merge(l2); // l1: 1 1 2 3 4 5 6 9l2变空merge要求两个list都已排序否则结果不对这个细节我一开始也栽过。3.3 vector、deque、list三者怎么选这一组的选型逻辑可以总结成一句话默认用vector确实需要高频头尾操作时用deque只在需要频繁中间插入且不靠下标访问时用list。见过一个项目把频繁中间插入的数据用vector硬扛数据量上来后每次插入都是大搬家整个模块性能崩掉。换list后插入确实变成O(1)了但随之而来的是缓存命中率明显下降元素访问变慢。这就是取舍。实际工程里还有一种普遍倾向是优先选vector——连续内存布局对CPU缓存极其友好现代处理器缓存未命中的代价远高于一次内存分配。list的节点散落在内存各处二三十万量级的链表遍历就能明显感觉到比vector慢。list插入快所以性能更好是常见误区只有在插入极多、遍历极少时才成立。4. set与map自动排序去重不是魔法红黑树在底层干活4.1 红黑树保证了什么set和map的底层都是红黑树一种自平衡的二叉搜索树它保证任何插入、删除、查找操作都是O(log n)。所谓自平衡就是数据无论怎么插入树的高度都维持在log n量级不会退化成长链表。红黑树的平衡靠节点颜色和约束规则实现规则细节不用手写但理解它的存在有助于理解set和map的两个天然特性第一元素永远有序插入后自动按key升序排列第二插入重复元素不会覆盖原值。4.2 set的insert返回值set的insert返回一个pairiterator, boolfirst是插入位置的迭代器second表示这次插入是否真的执行了false表示容器里已存在同值元素。multiset允许重复所以insert只返回iterator。std::setint s; auto ret s.insert(10); if (ret.second) { // 插入成功 } auto ret2 s.insert(10); // ret2.second falses.size()仍为1如果key是一个构造开销较大的类型可以考虑用emplace代替insert它直接在树节点上原地构造省去一次临时对象的拷贝或移动。4.3 map的operator[]是一个隐蔽的坑map最大的坑是operator[]。m[key]这个操作如果key不存在会自动创建一个默认值键值对插进去然后返回这个value的引用。这是C里少见的读操作会改变容器内容的场景。判断key是否存在必须要用find或者countstd::mapstd::string, int m; m[apple] 3; m[banana] 5; if (m.find(cherry) ! m.end()) { // 存在才执行 } if (m.count(cherry) 0) { // 不存在 }如果你错误地写if (m[cherry] 0)这条判断执行完之后map里就多出了一个{cherry, 0}。在高并发的读场景下这种意外的插入甚至会引发数据竞争。4.4 自定义排序规则set和map默认按key升序自定义结构体作为key时需要传一个仿函数作为比较器struct Person { std::string name; int age; }; struct CompareByAge { bool operator()(const Person a, const Person b) const { return a.age b.age; } }; std::setPerson, CompareByAge persons;比较器必须满足严格弱排序也就是ab为真时ba必须为假否则容器行为未定义。实战里最常见的错误是只比较一个字段当两个对象该字段相同时被当成等值后插入的直接被丢弃。设计自定义key时用唯一字段或组合字段做完整比较。4.5 map的遍历产物是pairmap的每个元素都是pairconst Key, T。遍历拿到的迭代器要取value得用it-second不要拿it-first当value用。C17的结构化绑定可以写得更干净容器元素形式key是否允许重复自动排序setvalue即key不允许是multisetvalue即key允许是mappairkey,value不允许是multimappairkey,value允许是for (const auto [key, value] : m) { std::cout key - value std::endl; }5. 容器适配器stack、queue、priority_queue背后站着别的容器5.1 适配器的本质是限制接口不是新的数据结构stack、queue、priority_queue这三个容器不直接持有数据它们内部持有另一个容器对象只对外暴露有限的接口。stack默认基于dequequeue默认基于dequepriority_queue默认基于vector并在其上维护堆结构。理解这一点最大的好处是你知道可以替换底层容器也明白为什么它们没有迭代器——不允许遍历正是适配器的语义要求。适配器默认底层特性典型场景stackdeque后进先出括号匹配、表达式求值queuedeque先进先出BFS、消息队列priority_queuevector按优先级出队TopK、任务调度5.2 stack和queue的接口很简单但限制也很多stack只有push、pop、top、empty、sizequeue是push、pop、front、back、empty、size。它们都没有迭代器不能遍历只能按规定的顺序访问。想查看stack中间某个元素只能弹出来再放回去或者干脆用deque自己控制。5.3 priority_queue的排序规则很多人在这里栽跟头priority_queue默认是大顶堆top取出来的是最大元素它的比较器参数用的是std::less这点和set正好反过来特别容易记混。想实现小顶堆用greater#include queue #include vector #include iostream int main() { // 默认大顶堆 std::priority_queueint pq; pq.push(3); pq.push(7); pq.push(1); while (!pq.empty()) { std::cout pq.top() ; // 输出7 3 1 pq.pop(); } std::cout std::endl; // 小顶堆 std::priority_queueint, std::vectorint, std::greaterint minpq; minpq.push(3); minpq.push(7); minpq.push(1); while (!minpq.empty()) { std::cout minpq.top() ; // 输出1 3 7 minpq.pop(); } return 0; }自定义类型用priority_queue时需要在类型里重载operator或者写一个仿函数。注意仿函数的规则和sort一样返回true表示第一个参数优先级低于第二个这跟直觉相反每次写我都要想一遍。5.4 stack的默认底层为什么是deque而不是vector一个容易被问到的问题stack默认底层为什么是deque因为deque尾部插入删除是O(1)而且不需要像vector那样扩容搬动元素。stack对栈顶操作频率极高deque的尾部操作和vector几乎一样快同时deque不需要一整块连续内存在内存碎片较多的场景更不容易分配失败。5.5 三个适配器的应用场景算法题里全是它们stack对应函数调用栈模拟、括号匹配、表达式求值。queue对应BFS广度优先搜索的待访问队列、异步消息队列。priority_queue对应任务调度按优先级取任务、Top K问题、求前K个最大或最小值的场景。做算法题或者业务开发时这三个数据结构出场率极高底层机制理解到位才能准确估算操作的复杂度。6. 迭代器失效问题容器操作里最隐蔽的陷阱与正确的删除姿势6.1 什么是迭代器失效迭代器在概念上就像一个指向容器元素的指针。某些容器操作之后迭代器可能仍然指向一块内存但内存已经不属于这个容器了或者已经被别的元素覆盖。这时解引用它结果不可预测。这比崩溃更讨厌——崩溃还能帮你定位未定义行为有时候会把错误数据带到很远的地方才爆发。6.2 vector的失效场景根源是内存搬移vector的失效有两个源头。第一是扩容push_back触达capacity时整体搬迁到新内存所有迭代器全部失效。第二是插入和删除引起的元素搬动中间插入后插入点及之后的迭代器全失效erase之后被删元素及其后的迭代器全失效。解决办法也简单提前reserve避免扩容erase时接收返回值插入操作之后重新获取迭代器不要保留旧的。6.3 每种容器的失效规则不一样deque比较微妙头尾插入删除时除了被删元素自己的迭代器其他基本不失效标准还要求指针和引用也不失效但中间插入删除会让全部迭代器失效。list非常宽松插入、删除、splice都不会让其他元素的迭代器失效只有被删元素自身的迭代器失效因为链表节点独立分配改指针不影响其他节点。set和map同样宽松插入不影响任何迭代器删除不影响其他元素的迭代器红黑树节点独立分配删一个节点不改变其他节点的关联关系。6.4 循环内删除元素的标准写法不同容器的循环删除写法照着抄就能避开坑// vector/deque接收erase返回值 for (auto it v.begin(); it ! v.end();) { if (条件) { it v.erase(it); } else { it; } } // list/set/mapC11之后erase同样返回下一个迭代器 for (auto it s.begin(); it ! s.end();) { if (条件) { it s.erase(it); } else { it; } }6.5 erase-remove惯用法删除容器中所有满足条件的元素最正统的写法是erase和remove组合叫erase-remove惯用法。remove并不真正删除元素而是把不需要删除的元素往前搬返回值指向新的逻辑尾部erase再把这个尾部到end之间的残留元素真正删掉v.erase(std::remove_if(v.begin(), v.end(), [](int x) { return x % 2 0; }), v.end());这个写法只适用于vector和deque。list不要用标准库为它专门提供了remove_if成员函数。6.6 一个练手项目里反复出现的崩溃举一个练手项目里的典型问题。某个社区系统的在线用户列表用vector存用户ID用户频繁进出时边遍历边删除。几千个用户时没感觉量级到几万后用户频繁退出时CPU占用飙升还会偶发崩溃。排查下来两个根因一是erase之后迭代器没有更新继续用旧迭代器自增二是vector频繁扩容导致迭代器整体失效。改完后先reserve到峰值再统一用erase返回值更新迭代器问题就消失了。从那以后我再不敢小看迭代器失效它根本不是课本理论是实实在在的线上事故。7. 容器选型实战同样的功能性能差距可能来自一个数据类型7.1 选型的一句话总结选型逻辑可以压缩成几步默认vector除非有明确理由换需要高频头尾操作就选deque需要频繁中间插入删除且不按下标访问就选list需要自动排序去重或按key快速查找就选set/map只要先进后出、先进先出或按优先级取用适配器。7.2 各操作复杂度对照操作vectordequelistset/map尾部插入O(1)均摊O(1)O(1)O(log n)头部插入O(n)O(1)O(1)O(log n)中间插入O(n)O(n)O(1)*O(log n)按下标访问O(1)O(1)O(n)不支持按值查找O(n)O(n)O(n)O(log n)*list的O(1)前提是已经持有目标位置的迭代器否则查找本身是O(n)。7.3 两个容易忽略的工程维度缓存与内存碎片理论复杂度之外CPU缓存行为往往比复杂度更重要。vector的连续内存遍历时一个缓存行能装下多个元素list的节点散落在不同地址每次跳转都可能缓存未命中。所以哪怕list的插入删除复杂度是O(1)遍历性能经常比vector差一个数量级。内存碎片是list的另一个隐患大量小节点在堆上反复分配释放会造成碎片在长时间运行的服务里比性能问题更难排查。7.4 按场景给结论需要数组但容量未知时vector加reserve是最常用组合。需要队列头淘汰、尾部追加这种模式时deque最合适。需要排序去重时set需要按ID查详情时map。需要取前K个最大或最小值时priority_queue。需要记录操作历史并频繁在中间回退时list是唯一合理的选择。7.5 最后一个实操建议学STL容器不要死记接口最好的方式是每个容器亲手写一遍增删改查再对比一次性能。我整理这份笔记时专门写了一个小测试向vector、deque、list分别插入十万个元素再遍历实测下来vector最快、deque次之、list最慢这个数据比任何理论都更能加深印象。你也可以用类似方式做一组性能对比不用多精确能直观感受差异就够了。容器是STL这座大厦的地基把地基的脾气摸透后面学算法、泛型编程都会顺畅很多。