STL容器 完整详解

STL（Standard Template Library，标准模板库）是C++标准库的核心组成部分，提供了一套通用、高效的数据结构与算法模板。容器（Container） 是STL的三大核心组件（容器、迭代器、算法）之一，负责存储和管理一组元素，封装了常用的数据结构，开发者无需重复造轮子即可快速实现复杂的数据管理逻辑。

一、STL容器概述

1. 核心概念

STL容器是模板类，支持存储任意类型的元素（基础类型、自定义结构体、类对象等），通过模板参数实现类型通用。所有容器都遵循统一的接口规范，配合迭代器可直接使用STL算法（排序、查找、遍历等）。

2. 容器的分类

STL容器按存储方式和特性分为四大类：

类别	核心特点	代表容器
序列式容器	元素按插入顺序线性排列，可通过位置索引访问	vector、deque、list、array、forward_list
有序关联式容器	元素按键值自动排序，底层红黑树实现，支持快速查找	set、multiset、map、multimap
无序关联式容器	元素无固定顺序，底层哈希表实现，平均O(1)查找	unordered_set、unordered_map、unordered_multiset、unordered_multimap
容器适配器	封装底层容器，对外提供受限的专用接口	stack、queue、priority_queue

3. 容器与迭代器、算法的关系

• 迭代器：容器和算法之间的桥梁，提供统一的方式遍历容器元素，屏蔽不同容器的底层实现差异。
• 算法：通过迭代器操作容器元素，不直接依赖容器类型，同一种算法可适配多种容器。

---

二、序列式容器

序列式容器的元素顺序由插入时机和位置决定，与元素值无关，支持按位置访问元素。

2.1 vector 动态数组

底层实现

连续的线性内存空间，本质是可自动扩容的数组。当存储空间不足时，会重新申请更大的内存（通常扩容为原大小的1.5~2倍），将原有元素拷贝到新空间，释放旧空间。

核心特点

• 支持随机访问（下标[]或at()），时间复杂度O(1)；
• 尾部插入/删除（push_back/pop_back）平均O(1)，中间插入/删除需要移动元素，O(n)；
• 内存连续，缓存友好，遍历效率极高；
• 扩容会导致所有指向容器的迭代器、指针、引用失效。

常用成员函数

vector<int> v;
v.push_back(10);    // 尾部插入元素
v.pop_back();       // 尾部删除元素
v.size();           // 元素个数
v.empty();          // 是否为空
v.clear();          // 清空所有元素
v.insert(v.begin()+2, 5); // 指定位置插入
v.erase(v.begin()+1);     // 删除指定位置元素
v[0];               // 下标访问（不检查越界）
v.at(0);            // 下标访问（越界抛异常）
v.capacity();       // 当前容量（可容纳的最大元素数）
v.reserve(100);     // 预分配容量，避免频繁扩容

适用场景

绝大多数需要线性存储、频繁尾部增删、随机访问的场景，是最常用的STL容器。

2.2 deque 双端队列

底层实现

分段连续内存 + 中控器（map数组），由多段独立的固定大小数组组成，中控器记录每段数组的地址，整体逻辑上是连续的。

核心特点

• 头尾两端都支持O(1)插入/删除（push_front/pop_front/push_back/pop_back）；
• 支持随机访问，但效率低于vector；
• 中间插入删除效率低，O(n)；
• 扩容时不会移动原有元素，仅新增分段数组，迭代器失效范围小。

常用成员函数

deque<int> dq;
dq.push_front(1);   // 头部插入
dq.push_back(2);    // 尾部插入
dq.pop_front();     // 头部删除
dq.pop_back();      // 尾部删除
dq.front();         // 头部元素
dq.back();          // 尾部元素

适用场景

需要频繁在两端增删元素的场景，如滑动窗口、BFS队列等。

2.3 list 双向链表

底层实现

带头尾指针的双向循环链表，每个元素存储在独立的节点中，节点包含数据域和前后指针。

核心特点

• 不支持随机访问，访问元素必须遍历，O(n)；
• 已知迭代器位置时，插入/删除元素仅需修改指针，O(1)；
• 内存不连续，缓存不友好，遍历效率低于vector；
• 插入删除操作仅使当前元素的迭代器失效，其他迭代器不受影响。

特有成员函数

list<int> l;
l.sort();           // 链表专属排序（算法sort要求随机访问迭代器，list不支持）
l.unique();         // 去除相邻重复元素
l.merge(other_list); // 合并两个有序链表
l.splice(l.begin(), other_list); // 将另一个链表的元素移动到指定位置

适用场景

频繁在中间位置插入删除元素、不需要随机访问的场景。

2.4 array 静态数组

C++11引入，封装原生数组的固定大小容器，大小在编译期确定，不可扩容。

• 支持随机访问，效率和原生数组一致；
• 提供size()、empty()等容器接口，比原生数组更安全；
• 栈上分配内存，无需手动管理。

array<int, 5> arr = {1,2,3,4,5}; // 大小必须是编译期常量

2.5 forward_list 单向链表

C++11引入，单向链表，比list更节省空间，但只能正向遍历，功能受限，仅适用于极致空间优化的场景。

---

三、有序关联式容器

关联式容器的元素按键（key） 自动排序，底层为红黑树（平衡二叉搜索树），查找、插入、删除均为O(logn)时间复杂度。

3.1 set / multiset

核心特点

• set：存储唯一的键，元素不允许重复，自动按升序排序；
• multiset：允许键重复，其余特性与set一致；
• 元素本身就是键，不能直接修改元素值（修改会破坏排序），只能删除后重新插入。

常用操作

set<int> s;
s.insert(10);       // 插入元素
s.erase(10);        // 删除值为10的元素
s.count(10);        // 统计元素出现次数（set中只能是0或1）
s.find(10);         // 查找元素，返回迭代器，找不到返回s.end()
s.lower_bound(5);   // 返回第一个>=5的元素迭代器
s.upper_bound(5);   // 返回第一个>5的元素迭代器

3.2 map / multimap

核心特点

• 存储键值对（key-value），按键自动排序，键唯一且不可修改；
• map：键不允许重复；multimap：允许键重复；
• 元素类型为pair<key_type, value_type>，通过first访问键，second访问值。

常用操作

map<string, int> mp;
mp["apple"] = 5;    // 下标访问，键不存在时自动插入默认值（int为0）
mp.insert({"banana", 3}); // 插入键值对
mp.erase("apple");  // 删除指定键的元素
mp.count("banana"); // 统计键的出现次数
mp.find("banana");  // 查找键，返回迭代器
// 遍历
for(auto it=mp.begin();it!=mp.end();it++){
    cout<<it->first<<" "<<it->second<<endl;
}

注意：map的operator[]存在副作用——若键不存在，会自动插入该键和默认值，只读查找时建议用find()避免意外插入。

3.3 通用特性

• 所有有序关联式容器默认按升序排序，可通过模板参数指定排序规则（如set<int, greater<int>>实现降序）；
• 插入删除操作仅影响当前节点的迭代器，其他迭代器保持有效。

---

四、无序关联式容器

C++11引入，底层为哈希表（散列表），元素无固定排序，平均情况下查找、插入、删除为O(1)，最坏情况（哈希冲突严重）退化为O(n)。

4.1 分类与特点

• unordered_set：无序唯一键集合
• unordered_multiset：无序可重复键集合
• unordered_map：无序键值对，键唯一
• unordered_multimap：无序键值对，键可重复

4.2 与有序关联式容器对比

维度	有序关联式（set/map）	无序关联式（unordered_*）
底层实现	红黑树	哈希表
元素顺序	按键有序	无序
查找效率	O(logn)	平均O(1)，最坏O(n)
内存占用	较低	较高（哈希表预留空间）
适用场景	需要有序遍历、范围查询	仅需快速查找，不关心顺序
键要求	支持比较运算符（<）	支持哈希函数 + 相等判断（==）

---

五、容器适配器

容器适配器本身不是独立容器，而是封装底层序列式容器，对外提供特定的受限接口，简化特定场景的使用。

5.1 stack 栈

特点

后进先出（LIFO），只能在栈顶操作元素，默认底层容器为deque，也可指定vector或list。

常用操作

stack<int> st;
st.push(10);    // 压栈
st.pop();       // 弹栈
st.top();       // 栈顶元素
st.size();
st.empty();

适用场景

括号匹配、表达式求值、深度优先搜索（DFS）等。

5.2 queue 队列

特点

先进先出（FIFO），只能在队尾插入、队头删除，默认底层容器为deque。

常用操作

queue<int> q;
q.push(10);    // 队尾入队
q.pop();       // 队头出队
q.front();     // 队头元素
q.back();      // 队尾元素

适用场景

广度优先搜索（BFS）、任务调度、消息队列等。

5.3 priority_queue 优先队列

特点

元素按优先级自动排序，队首始终是优先级最高的元素，默认底层容器为vector，底层实现为大顶堆。 默认大顶堆：数值越大优先级越高；可通过模板参数改为小顶堆。

常用操作

priority_queue<int> pq; // 默认大顶堆
priority_queue<int, vector<int>, greater<int>> pq2; // 小顶堆
pq.push(5);
pq.pop();
pq.top(); // 优先级最高的元素

适用场景

TopK问题、最短路径算法（Dijkstra）、哈夫曼树构建等。

---

六、迭代器详解

迭代器是一种“智能指针”，提供统一的方式遍历不同容器，按功能从弱到强分为5类：

1. 输入迭代器：只读，单向遍历
2. 输出迭代器：只写，单向遍历
3. 前向迭代器：可读写，单向遍历（如forward_list）
4. 双向迭代器：可读写，双向遍历（如list、set、map）
5. 随机访问迭代器：可读写，支持跳跃访问（如vector、deque、array）

功能越强的迭代器，支持的操作越多。例如STL的sort()算法要求随机访问迭代器，因此list、set等容器无法直接使用，需使用自身的成员函数。

---

七、选型原则与注意事项

1. 容器选型优先级

• 优先使用vector：绝大多数场景下性能最优，内存连续、遍历快；
• 需要两端增删：选deque；
• 频繁中间插入删除、不随机访问：选list；
• 需要快速查找、且需要有序：选set/map；
• 仅需要快速查找、不关心顺序：选unordered_set/unordered_map；
• 专用场景：栈用stack、队列用queue、优先级排序用priority_queue。

2. 迭代器失效常见场景

• vector：插入元素导致扩容时，所有迭代器失效；删除元素时，被删元素及之后的迭代器失效；
• deque：头尾插入删除可能使所有迭代器失效；中间插入删除使所有迭代器失效；
• list/set/map：插入删除仅使当前元素的迭代器失效，其他迭代器保持有效。

3. 其他注意事项

• STL容器默认不是线程安全的，多线程环境下读写需要加锁；
• 自定义类型作为关联式容器的键时，需重载对应的比较运算符或哈希函数；
• 避免在循环中错误操作迭代器（如删除元素后继续使用失效迭代器）。