引言在前两篇文章中我们学习了vector和stringstream。vector是连续存储的动态数组尾部操作高效但在中间和头部操作代价高昂。实际开发中我们还需要在不同场景下选择更合适的容器需要在头部和尾部都能高效操作→deque双端队列需要在任意位置高效插入删除→list双向链表需要按键值快速查找→map红黑树实现的有序映射本文将深入讲解这三个容器的底层原理、核心操作和适用场景。第一部分deque 双端队列一、底层结构dequedouble-ended queue双端队列由多个固定大小的连续空间组成通过一个中控器Map 数组管理这些空间的地址。为什么 deque 支持头尾高效操作push_front在第一个 Bucket 的前面写入如果满了就分配新 Bucket 挂到中控器前面push_back在最后一个 Bucket 的后面写入如果满了就分配新 Bucket 挂到中控器后面不需要像vector那样移动所有元素deque 的迭代器结构二、创建与初始化#include deque #include iostream using namespace std; int main() { // 1. 默认构造 dequeint d1; // 2. 初始化列表 dequeint d2 {1, 9, 2, 0, 8, 7}; // 3. 指定大小和初始值 dequeint d3(10); // 10 个 0 dequeint d4(10, 42); // 10 个 42 // 4. 从其他容器构造 dequeint d5(d2.begin(), d2.begin() 3); // {1, 9, 2} return 0; }三、元素添加dequeint d {1, 2, 3}; // 头尾添加最常用O(1) d.push_back(10); // 尾部追加 → {1, 2, 3, 10} d.push_front(4); // 头部追加 → {4, 1, 2, 3, 10} // 原地构造C11更高效 d.emplace_back(8); // 尾部原地构造 d.emplace_front(6); // 头部原地构造 // 指定位置插入 d.insert(d.begin() 2, 99); // 在第3个位置插入 99 d.insert(d.begin(), {11, 21, 33}); // 在开头插入多个 d.emplace(d.begin(), 22); // 在开头原地构造push_back vs emplace_back 的区别struct Point { int x, y; Point(int a, int b) : x(a), y(b) {} }; dequePoint dq; // push_back先构造临时对象再拷贝到 deque dq.push_back(Point(3, 4)); // emplace_back直接在 deque 内部构造省去拷贝 dq.emplace_back(5, 6);四、元素删除dequeint d {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 头尾删除 d.pop_back(); // 删除最后一个 → 10 d.pop_front(); // 删除第一个 → 1 // 删除指定位置 d.erase(d.begin() 2); // 删除第三个元素 d.erase(d.begin(), d.begin() 3); // 删除前三个 d.erase(d.end() - 3, d.end()); // 删除后三个 // 清空 d.clear();五、元素访问dequeint d {10, 20, 30, 40, 50}; // 下标访问支持随机访问 int a d[0]; // 10 int b d[2]; // 30 // at() 带越界检查 int c d.at(1); // 20 // 头尾元素 int first d.front(); // 10 int last d.back(); // 50六、完整示例#include iostream #include deque using namespace std; // 重载 操作符方便打印 deque templateclass T ostream operator(ostream cout, dequeT d) { for (auto it d.begin(); it ! d.end(); it) { cout *it ; } cout endl; return cout; } // 查找指定元素返回迭代器 dequeint::iterator findInDeque(dequeint deq, int item) { auto it deq.begin(); while (it ! deq.end()) { if (*it item) return it; it; } return it; // 返回 end() 表示未找到 } int main() { dequeint d {1, 9, 2, 0, 8, 7}; d.push_back(10); d.push_front(4); d.emplace_back(8); d.emplace_front(6); d.insert(d.begin() 2, {11, 21, 33}); cout size: d.size() endl; cout d; // 删除前3和后3 d.erase(d.begin(), d.begin() 3); d.erase(d.end() - 3, d.end()); cout d; // 交互式删除 int v; while (true) { cout 删除的元素(-1结束): ; cin v; if (v -1) break; auto it findInDeque(d, v); if (it ! d.end()) { d.erase(it); cout 删除成功 endl; } else { cout 查无此元素 endl; } } cout 最终: d; cout 头部: d.front() , 尾部: d.back() endl; return 0; }七、deque vs vector 对比对比项vectordeque底层结构一块连续内存多块连续内存 中控器头部插入push_front❌ O(n)✅ O(1)尾部插入push_back✅ O(1)✅ O(1)随机访问[i]✅ O(1)✅ O(1)稍慢中间插入insertO(n)O(n)内存释放shrink_to_fit()自动回收空闲 Bucket迭代器失效扩容时全部失效只在当前 Bucket 失效选择建议场景推荐只需尾部操作vector更简单缓存更友好需要头尾操作deque需要随机访问 头部操作deque频繁随机访问vector连续内存缓存命中率高第二部分list 双向链表一、底层结构list是双向循环链表每个节点有prev和next两个指针。C11 标准保证了list的节点在内存中独立分配插入删除不会导致迭代器失效被删除的那个除外。二、创建与初始化#include list #include iostream using namespace std; int main() { // 默认构造 listint l1; // 初始化列表 listint l2 {9, 2, 1, 3, 4}; // 指定大小 listint l3(10); // 10 个 0 listint l4(10, 42); // 10 个 42 return 0; }三、元素添加listint l {1, 2, 3}; // 头尾添加 l.push_back(20); // 尾部 l.push_front(12); // 头部 // 原地构造 l.emplace_back(8); // 尾部原地构造 l.emplace_front(22); // 头部原地构造 // 指定位置插入 l.insert(l.begin(), 99); // 在开头插入 l.insert(l.begin(), {10, 11, 12}); // 插入多个四、元素删除listint l {1, 2, 3, 4, 5, 6, 7, 8}; // 头尾删除 l.pop_back(); // 删尾部 l.pop_front(); // 删头部 // 删除指定位置 auto it l.begin(); it; it; // 移到第三个元素 l.erase(it); // 按值删除list 特有的高效操作 l.remove(2); // 删除所有值为 2 的元素 // 条件删除 l.remove_if([](int x) { return x 5; }); // 删除所有小于 5 的元素为什么 list 的remove()是 O(n) 但比vector高效vector的erase remove需要移动元素list的remove()只修改指针不需要移动元素五、list 特有操作listint l {5, 2, 8, 1, 9, 3}; // 排序list 自带 sort不需要用 std::sort l.sort(); // 升序1 2 3 5 8 9 l.sort(greater()); // 降序9 8 5 3 2 1 // 反转 l.reverse(); // 链表原地反转 // 去重需要先排序 l.sort(); l.unique(); // 删除连续重复的元素 // 合并两个有序链表 listint l2 {4, 6, 10}; l.merge(l2); // l2 被清空合并到 l为什么 list 自带 sort()std::sort()需要随机访问迭代器支持it nlist只有双向迭代器只支持和--不能用于std::sort()list::sort()内部使用归并排序专为链表设计六、仿函数与条件操作// 仿函数重载了 operator() 的类 class LessFive { private: int threshold; public: LessFive(int t) : threshold(t) {} bool operator()(int item) { return item threshold; } }; int main() { listint l {9, 2, 1, 8, 3, 4, 7}; // 删除所有小于 5 的元素 l.remove_if(LessFive(5)); // 结果9, 8, 7 return 0; }仿函数 vs 函数指针 vs Lambda方式代码特点函数指针remove_if(func)简单但无法保存状态仿函数remove_if(LessFive(5))可以保存状态thresholdLambdaremove_if([](int x){return x5;})C11最简洁七、完整示例#include iostream #include list #include functional using namespace std; int main() { listint l {9, 2, 1, 3, 4}; // 添加 l.push_back(20); l.push_front(12); l.emplace_front(22); l.emplace_back(8); l.insert(l.begin(), {10, 11}); // 遍历 for (int item : l) cout item ; cout endl; // 删除前三个元素list 迭代器不支持 n只能循环 auto it l.begin(); int count 3; while (count 0) { auto delIt it; it; l.erase(delIt); --count; } for (int item : l) cout item ; cout endl; cout 头部: l.front() endl; // 按值删除 l.remove(2); // 排序 l.sort(greater()); for (int item : l) cout item ; cout endl; // 反转 l.reverse(); for (int item : l) cout item ; cout endl; // 条件删除 l.remove_if([](int x) { return x 5; }); for (int item : l) cout item ; cout endl; return 0; }八、list vs vector vs deque 对比对比项vectordequelist底层连续数组分段连续双向链表随机访问[i]✅ O(1)✅ O(1)❌头部插入❌ O(n)✅ O(1)✅ O(1)尾部插入✅ O(1)✅ O(1)✅ O(1)任意插入删除O(n)O(n)✅ O(1)内存占用最小中等最大每节点2指针缓存友好✅ 最好较好❌ 最差迭代器失效扩容时全失效部分失效仅删除的失效自带排序❌ 用 std::sort❌ 用 std::sort✅ list::sort第三部分map 有序映射一、底层结构map的底层是红黑树一种自平衡二叉搜索树保证了元素按键值自动排序默认升序查找、插入、删除都是O(log n)遍历得到有序序列二、pair 键值对#include map #include string using namespace std; int main() { // 创建 pair 的方式 pairint, string p1; p1.first 1001; p1.second disen; pairint, string p2(1002, Lucy); pairint, string p3 {1003, Mike}; // C11 auto p4 make_pair(1004, Tom); // 自动推导类型 cout K: p1.first , V: p1.second endl; return 0; }三、创建与插入#include map #include string #include iostream using namespace std; int main() { // 1. 初始化列表 mapint, string m1 { {1, A}, {2, C}, {5, D}, {3, B} }; // 2. 指定排序规则greater 降序 mapint, string, greater m2 { {1, A}, {2, C}, {5, D}, {3, B} }; // 3. 插入元素 m1.insert({4, Lucy}); m1.insert(make_pair(6, Tom)); m1.emplace(7, Jerry); // 原地构造最高效 // 4. [] 操作符最方便 m1[1] Mack; // key1 已存在更新 value m1[6] Jack; // key6 不存在插入新元素 return 0; }[]操作符 vsinsertvsemplace操作key 存在时key 不存在时m[k] v更新value插入新元素insert({k, v})忽略不插入插入emplace(k, v)忽略不插入插入最高效四、遍历与查找mapint, string m {{1,A}, {2,C}, {5,D}, {3,B}}; // 遍历按键升序 for (auto it m.begin(); it ! m.end(); it) { cout K: it-first , V: it-second endl; } // 输出顺序1:A, 2:C, 3:B, 5:D自动按键排序 // 范围 for for (const auto kv : m) { cout kv.first → kv.second endl; } // 查找 auto it m.find(3); if (it ! m.end()) { cout 找到: it-second endl; } else { cout 不存在 endl; }五、完整示例#include iostream #include map #include string #include functional using namespace std; int main() { mapint, string, greater m { {1, A}, {2, C}, {5, D}, {3, B} }; // 遍历 for (auto it m.begin(); it ! m.end(); it) { cout K: it-first , V: it-second endl; } cout string(30, -) endl; // 插入测试 m.emplace(make_pair(2, BC)); // key2 已存在不会插入 m.insert({{5, Disen}, {4, Lucy}}); // 5 存在不插入4 插入 m[1] Mack; // 更新 key1 m[6] Jack; // 插入 key6 // 再次遍历 for (auto it m.begin(); it ! m.end(); it) { cout K: it-first , V: it-second endl; } return 0; }运行结果第四部分三大顺序容器选择指南总结一、核心操作速查操作vectordequelistmap头部插入❌✅ push_front✅ push_front—尾部插入✅ push_back✅ push_back✅ push_back—随机访问✅ [i]✅ [i]❌✅ [k]任意插入insertinsertinsertinsert/emplace排序std::sortstd::sortlist::sort自动排序底层数组分段数组双向链表红黑树二、一句话记忆vector动态数组尾插尾删快随机访问扩容代价高deque多数组组合头尾都快支持随机访问适合双端操作list双向链表任意位置 O(1) 插入删除不支持随机访问自带 sortmap红黑树实现的键值对容器按键自动排序查找 O(log n)