C++ STL 容器完全指南（三）：deque、list 与 map 深度详解

引言

在前两篇文章中，我们学习了vector和stringstream。vector是连续存储的动态数组，尾部操作高效但在中间和头部操作代价高昂。实际开发中，我们还需要在不同场景下选择更合适的容器：

• 需要在头部和尾部都能高效操作？→deque（双端队列）

• 需要在任意位置高效插入删除？→list（双向链表）

• 需要按键值快速查找？→map（红黑树实现的有序映射）

本文将深入讲解这三个容器的底层原理、核心操作和适用场景。

第一部分：deque 双端队列

一、底层结构

deque（double-ended queue，双端队列）由多个固定大小的连续空间组成，通过一个中控器（Map 数组）管理这些空间的地址。

为什么 deque 支持头尾高效操作？

• push_front：在第一个 Bucket 的前面写入，如果满了就分配新 Bucket 挂到中控器前面

• push_back：在最后一个 Bucket 的后面写入，如果满了就分配新 Bucket 挂到中控器后面

• 不需要像vector那样移动所有元素

deque 的迭代器结构：

二、创建与初始化

#include <deque> #include <iostream> using namespace std; int main() { // 1. 默认构造 deque<int> d1; // 2. 初始化列表 deque<int> d2 = {1, 9, 2, 0, 8, 7}; // 3. 指定大小和初始值 deque<int> d3(10); // 10 个 0 deque<int> d4(10, 42); // 10 个 42 // 4. 从其他容器构造 deque<int> d5(d2.begin(), d2.begin() + 3); // {1, 9, 2} return 0; }

三、元素添加

deque<int> d = {1, 2, 3}; // 头尾添加（最常用，O(1)） d.push_back(10); // 尾部追加 → {1, 2, 3, 10} d.push_front(4); // 头部追加 → {4, 1, 2, 3, 10} // 原地构造（C++11，更高效） 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) {} }; deque<Point> dq; // push_back：先构造临时对象，再拷贝到 deque dq.push_back(Point(3, 4)); // emplace_back：直接在 deque 内部构造，省去拷贝 dq.emplace_back(5, 6);

四、元素删除

deque<int> 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();

五、元素访问

deque<int> 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 template<class T> ostream& operator<<(ostream& cout, deque<T>& d) { for (auto it = d.begin(); it != d.end(); ++it) { cout << *it << " "; } cout << endl; return cout; } // 查找指定元素，返回迭代器 deque<int>::iterator findInDeque(deque<int>& deq, int item) { auto it = deq.begin(); while (it != deq.end()) { if (*it == item) return it; ++it; } return it; // 返回 end() 表示未找到 } int main() { deque<int> 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 对比

选择建议：

第二部分：list 双向链表

一、底层结构

list是双向循环链表，每个节点有prev和next两个指针。C++11 标准保证了list的节点在内存中独立分配，插入删除不会导致迭代器失效（被删除的那个除外）。

二、创建与初始化

#include <list> #include <iostream> using namespace std; int main() { // 默认构造 list<int> l1; // 初始化列表 list<int> l2 = {9, 2, 1, 3, 4}; // 指定大小 list<int> l3(10); // 10 个 0 list<int> l4(10, 42); // 10 个 42 return 0; }

三、元素添加

list<int> 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}); // 插入多个

四、元素删除

list<int> 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 特有操作

list<int> 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(); // 删除连续重复的元素 // 合并两个有序链表 list<int> l2 = {4, 6, 10}; l.merge(l2); // l2 被清空，合并到 l

为什么 list 自带 sort()？

• std::sort()需要随机访问迭代器（支持it + n）

• list只有双向迭代器（只支持++和--），不能用于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() { list<int> l = {9, 2, 1, 8, 3, 4, 7}; // 删除所有小于 5 的元素 l.remove_if(LessFive(5)); // 结果：9, 8, 7 return 0; }

仿函数 vs 函数指针 vs Lambda：

七、完整示例

#include <iostream> #include <list> #include <functional> using namespace std; int main() { list<int> 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 对比

第三部分：map 有序映射

一、底层结构

map的底层是红黑树（一种自平衡二叉搜索树），保证了：

• 元素按键值自动排序（默认升序）

• 查找、插入、删除都是O(log n)

• 遍历得到有序序列

二、pair 键值对

#include <map> #include <string> using namespace std; int main() { // 创建 pair 的方式 pair<int, string> p1; p1.first = 1001; p1.second = "disen"; pair<int, string> p2(1002, "Lucy"); pair<int, string> p3 = {1003, "Mike"}; // C++11 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. 初始化列表 map<int, string> m1 = { {1, "A"}, {2, "C"}, {5, "D"}, {3, "B"} }; // 2. 指定排序规则（greater 降序） map<int, 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"; // key=1 已存在，更新 value m1[6] = "Jack"; // key=6 不存在，插入新元素 return 0; }

[]操作符 vsinsertvsemplace：

四、遍历与查找

map<int, 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() { map<int, 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")); // key=2 已存在，不会插入 m.insert({{5, "Disen"}, {4, "Lucy"}}); // 5 存在不插入，4 插入 m[1] = "Mack"; // 更新 key=1 m[6] = "Jack"; // 插入 key=6 // 再次遍历 for (auto it = m.begin(); it != m.end(); ++it) { cout << "K:" << it->first << ", V:" << it->second << endl; } return 0; }

运行结果：

第四部分：三大顺序容器选择指南

总结

一、核心操作速查

二、一句话记忆

• vector：动态数组，尾插尾删快，随机访问，扩容代价高

• deque：多数组组合，头尾都快，支持随机访问，适合双端操作

• list：双向链表，任意位置 O(1) 插入删除，不支持随机访问，自带 sort

• map：红黑树实现的键值对容器，按键自动排序，查找 O(log n)