容器分类与选择：像整理书包一样管理数据

在日常生活中，我们经常需要把各种东西装在不同的容器里：书包里的书本按科目分类，文具盒放笔，零食袋装零食。如果拿一个巨大的塑料袋把所有东西混在一起，想找语文书时就要翻半天。编程中也一样，数据需要合适的“容器”来存放，才能让程序跑得快、写起来省力。

STL（标准模板库）提供了多种容器，就像超市里不同功能的购物车、收纳盒、保鲜袋。学会区分它们的特点，能在写代码时一眼挑出最合适的“工具”。

从超市购物说起（重温并深化）

你和妈妈去超市买零食。你需要一个购物车（放大量商品），如果需要精确地找到某个品牌的薯片，说不定用带分隔的收纳盒更方便。如果购物车上自带一个小篮子专门放易碎品，那就更棒了。编程里，数据也需要不同的“购物车”——容器。不同容器有各自的特点：有的擅长快速在尾部添加删除，有的擅长快速查找，有的能自动排序。选不对容器，就像用自行车运一吨沙子——虽然也能做到，但效率极低。

STL容器主要分为两大类：序列式容器和关联式容器。另外还有容器适配器（在已有容器上封装新接口，如stack、queue、priority_queue）。我们先理解两类核心容器。

序列式容器（Sequential Containers）——就像排队买冰淇淋

序列式容器中的元素按插入顺序线性排列，每个元素有自己的位置（下标或迭代器偏移）。就像同学们在教室里的座位，按照学号顺序坐好。

vector（动态数组）——你的铅笔盒

特点：连续内存，支持随机访问（O(1)），尾插尾删O(1)，中间插入删除O(n)。
生活例子：铅笔盒里有10支笔，你想拿第3支笔，直接数到第3个就行（随机访问）。如果最后再放一支笔也很方便（尾插）。但如果在中间插入一支笔，后面的笔都要往后挪（O(n)）。
适用场景：需要频繁随机访问，且主要在尾部修改。比如存储游戏得分、学生成绩列表、天气温度记录。
迭代器类型：随机访问迭代器。

deque（双端队列）——食堂打饭窗口

特点：分段连续内存，头尾插入删除O(1)，中间O(n)，支持随机访问（但比vector慢一点）。
生活例子：食堂排队打饭，新来的同学可以站到队尾（尾插），也可以插队到最前面（头插），但中间插队就要让所有人重新排队（中间插入慢）。想找队伍里第5个同学，虽然能数到，但不如直接看学号快。
适用场景：需要频繁在头和尾两端操作，比如任务调度队列、浏览历史前进后退（最近浏览的网页在头部，更早的在尾部）。
迭代器类型：随机访问迭代器（非连续，但有类似支持）。

list（双向链表）——教室里的手拉手游戏

特点：非连续内存，每个节点有前驱和后继指针，插入删除O(1)（已知位置时），不支持随机访问。
生活例子：同学们手拉手站成一圈，每个人只记得前后是谁。想加入一个新同学，只要让他拉住两个人的手就行（插入快）。但是如果你想找到第5个同学，必须从第1个开始一个一个数过去（不能随机访问）。
适用场景：频繁在中间插入删除，且不需要快速随机访问。例如实现多项式计算中的项插入、文字处理软件的撤销/重做操作。
迭代器类型：双向迭代器。

forward_list（单向链表，C++11）——单行道

特点：比list更省内存（只存后继指针），但只能从头到尾单向遍历。
生活例子：单行道上的一排自行车，每辆车只记得后面的车，忘记前面的车。如果你要找第3辆车，必须从第一辆开始往后数。
适用场景：对内存要求极苛刻，且只需要前向遍历。例如哈希表的链表拉链法、稀疏图的邻接表。
迭代器类型：前向迭代器。

array（固定数组，C++11）——名字牌

特点：大小编译时固定，连续内存，支持随机访问，不能动态增长。
生活例子：班级里每个同学的座位是固定的，你不能随意增加座位。但是你知道每个学号对应谁，直接看学号就行。
适用场景：已知元素个数，且不需要改变数组大小。例如存储数学矩阵的固定维度、一年12个月的天数。
迭代器类型：随机访问迭代器（本质是原生指针）。

特点：元素唯一，自动升序（可用自定义比较器）。
生活例子：班级里统计谁参加过运动会，每个人只能记一次，而且名单会自动按学号排序。
适用场景：去重、会员名单、成绩排名（自动排序）。

multiset

允许重复元素，其余同set。
生活例子：统计考试成绩时，可能会有多个同学考同样的分数，但你仍然想记录所有分数，而且自动排序。

map

键值对，键唯一，按键排序，用[]访问或插入，O(log n)。
生活例子：学生学号对应姓名，按学号排序。用ap[学号]就可以快速找到名字。
适用场景：词典（中文-英文）、成绩单（学号-分数）。

multimap

允许键重复，不能用[]，用equal_range获取所有匹配。
生活例子：一个学生可能选修多门课（学号对应多个课程名），这样同一个键（学号）可以对应多个值。

无序关联容器（Unordered，C++11）——像手机通讯录的快速查找

基于哈希表，平均O(1)查找，最坏O(n)。元素无特定顺序。

unordered_set / unordered_multiset

类似set，但无顺序，哈希查找更快。
生活例子：手机通讯录直接按名字查找，不用排序，一秒找到联系人。

unordered_map / unordered_multimap

哈希映射，平均O(1)查找。
生活例子：统计一篇文章中每个单词出现次数，用单词作为键，出现次数作为值。查找极快。

容器适配器（Container Adapters）——对已有容器加“外壳”

适配器是对底层容器进行接口限制，提供特定操作。就像把购物车改装成专用的小推车。

stack（栈）——一叠盘子

后进先出：最后放上去的盘子最先被拿走。
生活例子：浏览器后退按钮（最后访问的页面先返回）、代码函数的调用栈。
默认用deque，也可指定vector或list。

queue（队列）——排队买票

先进先出：先排队的人先买票。
生活例子：打印任务队列、食堂打饭。
默认deque。

priority_queue（优先队列）——医院急诊室

最大堆（默认）：优先级最高的元素最先出队。
生活例子：医院里病情严重的病人先治疗，即使他来得晚。
默认用vector。

它们不提供迭代器，只能通过专用成员操作。例如push、pop、top（stack/priority_queue）、front/back（queue）。

容器选择决策树（帮你快速决定）

在写程序前，问自己几个问题：

是否需要随机访问（按索引访问）？
- 是 → vector（默认首选）或 deque（如果头尾操作多）
- 否 → 转到2
是否频繁在中间插入删除？
- 是 → list（双向）或 forward_list（内存紧张）
- 否 → 转到3
是否需要按某种顺序自动组织数据？
- 是 → set/map（有序）或 unordered_set/map（无序但快）
- 否 → vector/deque（按插入顺序）
是否需要特殊操作（栈/队列/优先队列）？
- 是 → stack/queue/priority_queue

提示：如果只是简单存储少量数据，用vector几乎总是最省心的选择，它的性能和内存布局都很优秀。

常见错误与避坑指南

新手在使用容器时容易踩的坑，这里帮你提前排雷：

1. 误用 `vector<bool>` 特化

C++中vector<bool>是一个特化版本，它不像普通vector那样存储真实的bool对象，而是按位压缩存储。这会导致一些问题：

不能取元素的地址（&v[0]会编译错误）
迭代器解引用返回的是代理对象，不是bool& 解决方法：如果必须存储bool，考虑使用deque<bool>或vector<char>。

2. 迭代器失效

在容器中插入或删除元素后，已有的迭代器可能失效（指向被移动或删除的内存）。

vector：在容量改变或中间插入/删除后，所有迭代器失效。
deque：在中间插入/删除会使所有迭代器失效；头尾操作仅使被操作元素的迭代器失效。
list：只有被删除元素的迭代器失效，插入不影响其他迭代器。
map/set：只有被删除元素的迭代器失效。

解决方法：在循环中插入/删除后，及时更新迭代器（使用erase的返回值）。

3. 混淆 `map` 和 `unordered_map` 的使用场景

map：需要按关键字有序遍历、需要区间查找（lower_bound/upper_bound）时使用。
unordered_map：仅需要快速查找，不关心顺序时使用。注意：哈希函数可能造成冲突，最坏性能差。

#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <string>

int main() {
    // ==================== 1. vector 存储学生成绩 ====================
    std::vector<double> scores = {85.5, 92.0, 78.5, 88.0};
    scores.push_back(95.5);  // 尾部添加新成绩
    std::cout << "第3个学生的成绩是: " << scores[2] << std::endl;  // 随机访问

    // ==================== 2. deque 存储待办任务 ====================
    std::deque<std::string> tasks = {"写作业", "做数学题"};
    tasks.push_front("起床");   // 头部插入
    tasks.push_back("睡觉");   // 尾部插入
    std::cout << "第一件事: " << tasks.front() << ", 最后一件事: " << tasks.back() << std::endl;

    // ==================== 3. list 存储多项式各项 ====================
    std::list<int> poly = {3, 0, -1};  // 表示 3x^2 + 0x - 1
    auto it = poly.begin();
    ++it;  // 指向0
    poly.insert(it, 2); // 插入成 3,2,0,-1  (3x^3 + 2x^2 + 0x -1)
    for (int coeff : poly) std::cout << coeff << " ";
    std::cout << std::endl;

    // ==================== 4. set 去重并排序 ====================
    std::set<int> numbers = {5, 3, 5, 1, 3, 2};  // 最终存储 {1,2,3,5}
    std::cout << "不同数字个数: " << numbers.size() << std::endl;

    // ==================== 5. map 学号到姓名的映射 ====================
    std::map<int, std::string> students;
    students[1001] = "小明";
    students[1002] = "小红";
    students[1001] = "小刚";  // 覆盖：学号1001现在对应小刚
    std::cout << "学号1001姓名: " << students[1001] << std::endl;

    // ==================== 6. unordered_map 统计单词出现次数 ====================
    std::unordered_map<std::string, int> wordCount;
    wordCount["apple"] = 3;   // apple出现3次
    wordCount["banana"] = 2;
    std::cout << "apple出现次数: " << wordCount["apple"] << std::endl;

    // ==================== 7. stack 模拟撤销操作 ====================
    std::stack<std::string> undoStack;
    undoStack.push("删除文字");
    undoStack.push("插入图片");
    undoStack.push("改变颜色");
    std::cout << "最新操作: " << undoStack.top() << std::endl;  // 改变颜色
    undoStack.pop();  // 撤销改变颜色
    std::cout << "撤销后最新操作: " << undoStack.top() << std::endl;  // 插入图片

    // ==================== 8. queue 模拟打印队列 ====================
    std::queue<int> printQueue;
    printQueue.push(101);  // 文档1
    printQueue.push(102);  // 文档2
    printQueue.push(103);  // 文档3
    std::cout << "正在打印文档: " << printQueue.front() << std::endl;  // 101
    printQueue.pop();  // 打印完成

    // ==================== 9. priority_queue 模拟急诊室 ====================
    std::priority_queue<int> emergencyRoom;  // 默认最大堆，数字越大优先级越高
    emergencyRoom.push(3);  // 轻度
    emergencyRoom.push(5);  // 重度
    emergencyRoom.push(1);  // 轻微
    std::cout << "第一个治疗的病人优先级: " << emergencyRoom.top() << std::endl;  // 5 (重度)

    return 0;
}

代码详解：

vector：scores[2]直接返回第三个元素，因为支持随机访问。
deque：tasks.front()和tasks.back()返回首尾引用，无需[]。
list：poly.insert(it, 2)在迭代器it之前插入，O(1)（已知位置）。
set：自动去重并排序，numbers.size()返回4。
map：students[1001]如果键不存在会自动创建并返回默认值（空字符串），然后赋予新值。
unordered_map：哈希表，平均O(1)查找。
stack：top()返回栈顶元素，pop()移除栈顶。
queue：front()返回队首，pop()移除队首。
priority_queue：top()返回最大元素（默认使用less比较器，即最大堆）。

Python中的等价容器（扩展说明）

Python的内置容器概念类似，但没有严格的迭代器分类，用法更直观。

# 1. list (类似vector)
vec = [10, 20, 30]
vec.append(40)
print("list[2] =", vec[2])

# 2. deque (需要from collections import deque)
from collections import deque
deq = deque([1, 2, 3])
deq.appendleft(0)
deq.append(4)
print("deque[0] =", deq[0], "deque[-1] =", deq[-1])

# 3. list也可以中间插入 (但O(n))
lst = [5, 10, 15]
lst.insert(1, 7)  # 在索引1处插入7，变成 [5,7,10,15]
print("list after insert:", lst)

# 4. set (自动去重，无序)
s = {3, 1, 4, 1, 5}
print("set size:", len(s))  # 4

# 5. dict (类似map)
ages = {"Alice": 12, "Bob": 14}
print("Alice age =", ages["Alice"])

# 6. collections.Counter (类似unordered_map计数)
from collections import Counter
words = Counter()
words["hello"] += 1
words["world"] += 2
print("wordCount[hello] =", words["hello"])

# 7. 栈 (用list实现)
stk = []
stk.append(1)
stk.append(2)
stk.append(3)
print("stack top =", stk[-1])   # 3，最后入栈的

# 8. 队列 (用collections.deque)
from collections import deque
q = deque()
q.append(1)
q.append(2)
q.append(3)
print("queue front =", q[0], "back =", q[-1])  # 1 和 3

# 9. 优先队列 (heapq实现最小堆，最大堆需取负数)
import heapq
nums = [5, 1, 8]
heapq.heapify(nums)  # 最小堆，nums变成 [1,5,8]
print("最小元素 =", nums[0])  # 1
# 如果要最大堆，可以存负数
import heapq
nums = [5, 1, 8]
heap_max = [-x for x in nums]
heapq.heapify(heap_max)
print("最大元素 =", -heap_max[0])  # 8

说明：

Python的list在中间插入是O(n)，因为需要移动元素；如果频繁中间插入，应使用deque或list的bisect模块。
Python的set和dict默认是无序的（Python 3.7+ dict保持插入顺序，但并不是有序容器）。
优先队列用heapq实现最小堆，若要最大堆，可以存负数或使用heapq._heapify_max（不常用）。

总结与注意事项

要点

序列容器按插入顺序，关联容器按值排序或哈希。
vector是“默认容器”，大部分情况性能好；deque适合两端操作；list适合中间插入删除。
需要快速查找用unordered_set/map（平均O(1)），需要有序范围查找用set/map（O(log n)）。
容器适配器提供了栈、队列、优先队列的便捷接口。

注意事项

在C++中，vector<bool>是一个特化版本，它不是一个真正的容器，而是位压缩存储，使用时需注意。
关联容器的迭代器是双向迭代器，不能随机跳跃，但map的迭代器解引用得到pair<const Key, Value>。
Python的set元素必须可哈希（即不可变类型），list不能作为set元素，但tuple可以。
选择容器时，不仅要看操作频率，还要考虑内存占用和缓存友好度：vector最友好，list最差。

容器的分类与选择指南