STL 标准模板库全面解析：容器、算法与迭代器的核心应用
一、STL 概述与六大组件
STL（Standard Template Library）是 C++ 的标准模板库，通过模板实现数据结构与算法的泛型编程，大幅提升代码复用性。其核心由六大组件构成：
1. 核心组件架构
- 容器（Containers）：封装数据结构，如
vector、list、map； - 算法（Algorithms）：实现通用操作，如
sort、find、for_each； - 迭代器（Iterators）：连接容器与算法，类似指针接口；
- 仿函数（Functors）：重载
()运算符的类，作为算法策略（如比较函数）； - 适配器（Adapters）：修饰容器 / 迭代器 / 仿函数的接口（如
stack基于deque实现）； - 空间配置器（Allocators）：管理内存分配与释放（如
vector的动态扩容）。
2. 容器与算法的连接
迭代器是 STL 的 "胶水"，所有算法通过迭代器操作容器元素。例如：
vector<int> v = {1, 2, 3};
for (auto it = v.begin(); it != v.end(); ++it) { // 迭代器遍历cout << *it << " ";
}
sort(v.begin(), v.end()); // 算法通过迭代器排序
二、容器分类与核心用法
容器分为序列式容器（元素有序排列）和关联式容器（基于树或哈希结构）。
1. 序列式容器
vector：动态数组
- 特点：支持随机访问，尾部增删高效，扩容时会重新分配空间并复制数据。
- 核心操作：
vector<int> v; v.push_back(10); // 尾部插入 v.insert(v.begin(), 5); // 在begin位置插入5 v.erase(v.end() - 1); // 删除尾元素 int val = v[2]; // 随机访问（等价于v.at(2)） - 扩容机制：每次扩容会申请更大空间（通常为原大小的 2 倍），导致原有迭代器失效。
deque：双端队列
- 特点：头尾增删高效（O (1)），支持随机访问，内部通过中控器管理分段缓冲区。
- 核心操作：
deque<int> d; d.push_front(1); // 头部插入 d.push_back(10); // 尾部插入 d[0] = 5; // 访问首元素
list：双向链表
- 特点：任意位置增删高效（O (1)），不支持随机访问，迭代器仅能前后移动。
- 核心操作：
list<int> l = {3, 1, 2}; l.sort(); // 链表专属排序（标准算法不支持） l.reverse(); // 反转链表 l.insert(l.begin(), 0); // 头部插入
stack/queue：适配器容器
- stack：后进先出（LIFO），默认基于
deque实现：stack<int> st; st.push(5); // 入栈 st.pop(); // 出栈 int top = st.top(); // 访问栈顶 - queue：先进先出（FIFO），默认基于
deque实现：queue<int> q; q.push(10); // 入队 q.pop(); // 出队 int front = q.front(); // 访问队首
2. 关联式容器
set/multiset：有序集合
- 特点：元素自动排序（默认升序），
set不允许重复，multiset允许。 - 核心操作：
set<int> s; s.insert(3); // 插入（自动去重） auto it = s.find(2); // 查找，返回迭代器 int cnt = s.count(5); // 统计元素个数（set中只能是0或1）// 插入时返回pair判断是否成功 pair<set<int>::iterator, bool> ret = s.insert(1); if (ret.second) cout << "插入成功"; - 自定义排序：通过仿函数修改比较规则：
set<int, greater<int>> s; // 降序排列
map/unordered_map：键值对映射
- map：基于红黑树，有序，查找 O (logN)；
- unordered_map：基于哈希表，无序，查找 O (1)。
- 核心操作：
map<string, int> m; m["apple"] = 10; // 插入/修改 int price = m["apple"]; // 访问（不存在时自动插入默认值）auto it = m.find("banana"); // 查找 m.erase(it); // 删除迭代器指向的元素
三、迭代器类型与应用
迭代器定义了算法操作容器的接口，按功能分为 5 类：
1. 迭代器分类
| 类型 | 功能描述 | 支持操作 | 对应容器示例 |
|---|---|---|---|
| 输入迭代器 | 只读，单遍扫描，向前移动 | ++、==、!=、* | istream_iterator |
| 输出迭代器 | 只写，单遍扫描，向前移动 | ++、* | ostream_iterator |
| 前向迭代器 | 读写，多遍扫描，向前移动 | ++、==、!=、* | forward_list |
| 双向迭代器 | 读写，前后移动 | ++、--、==、!=、* | list、set |
| 随机访问迭代器 | 读写，任意位置跳跃访问 | ++、--、+n、-n、[] | vector、deque |
2. 迭代器失效场景
- vector/deque：插入 / 删除元素可能导致迭代器失效（扩容或删除中间元素时）；
- list/set/map：插入元素不影响其他迭代器，删除元素仅使被删元素的迭代器失效。
四、算法分类与常用接口
算法分为质变算法（修改元素内容）和非质变算法（不修改内容）。
1. 遍历与查找算法
- for_each：遍历容器执行函数：
vector<int> v = {1, 2, 3}; for_each(v.begin(), v.end(), [](int x) { cout << x << " "; }); - find：查找元素，返回迭代器：
auto it = find(v.begin(), v.end(), 2); if (it != v.end()) cout << "找到元素"; - binary_search：二分查找（需有序容器）：
sort(v.begin(), v.end()); bool exists = binary_search(v.begin(), v.end(), 2);
2. 排序与生成算法
- sort：排序（默认升序，可自定义比较函数）：
vector<int> v = {3, 1, 2}; sort(v.begin(), v.end(), greater<int>()); // 降序 - random_shuffle：随机打乱元素（需先设置随机种子）：
srand(time(NULL)); random_shuffle(v.begin(), v.end()); - accumulate：累加元素：
int sum = accumulate(v.begin(), v.end(), 0); // 从0开始累加
3. 集合与数值算法
- set_intersection：求交集（需有序容器）：
vector<int> v1 = {1, 2, 3}, v2 = {2, 3, 4}, v3(3); auto it = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin()); v3.erase(it, v3.end()); // 截断无效元素 - merge：合并有序容器：
vector<int> v4(6); // 预分配足够空间 merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v4.begin());
五、仿函数与适配器的实战应用
1. 仿函数（函数对象）
- 定义：重载
()运算符的类，可像函数一样调用：struct Add {int operator()(int a, int b) { return a + b; } };Add add; int result = add(10, 20); // 调用仿函数 - 内建仿函数：C++ 标准库提供的仿函数，如：
vector<int> v = {3, 1, 2}; sort(v.begin(), v.end(), greater<int>()); // 降序排序（使用内建关系仿函数）
2. 适配器（Adapter）
- 函数适配器：修改仿函数的接口，如
bind（C++11）绑定参数：#include <functional> using namespace std::placeholders; // for _1, _2...auto add = [](int a, int b) { return a + b; }; auto add10 = bind(add, _1, 10); // 固定第二个参数为10 int r = add10(5); // 等价于add(5, 10) - 迭代器适配器：如
reverse_iterator反向遍历容器：vector<int> v = {1, 2, 3}; for (auto it = v.rbegin(); it != v.rend(); ++it) {cout << *it << " "; // 输出3 2 1 }
六、STL 容器嵌套与性能优化
1. 容器嵌套使用
- 示例：vector 嵌套 vector
vector<vector<int>> v; v.push_back({1, 2}); v.push_back({3, 4, 5});// 遍历 for (auto& row : v) {for (int val : row) {cout << val << " ";}cout << endl; }
2. 性能优化技巧
- vector 预留空间：
reserve(n)避免多次扩容：vector<int> v; v.reserve(100); // 预留100个元素空间 - 收缩 vector 容量：通过
swap技巧释放多余空间：vector<int>(v).swap(v); // 用临时容器交换，释放冗余空间 - 优先选择合适容器：
- 需要随机访问：选
vector； - 频繁头尾操作：选
deque； - 频繁中间插入删除：选
list； - 快速查找：选
unordered_map（无序）或map（有序）。
- 需要随机访问：选
七、STL 经典面试问题与解答
-
vector 扩容时迭代器为什么会失效？
答：扩容时会分配新内存并复制数据，原迭代器指向的旧内存被释放，因此失效。 -
set 和 unordered_set 的区别？
答：set基于红黑树，有序，查找 O (logN)；unordered_set基于哈希表，无序，平均查找 O (1)。 -
为什么 list 不能用标准算法排序？
答：list 的迭代器是双向迭代器，不支持随机访问，而标准sort算法需要随机访问迭代器，因此 list 提供专属sort成员函数。
通过深入理解 STL 的容器、算法与迭代器，开发者能高效构建复杂数据结构与算法，提升代码的复用性和性能。在实际开发中，需根据场景选择合适的容器，并注意迭代器失效与性能优化，充分发挥 STL 的强大能力。