C++ STL 容器与迭代器

更新时间：2026-08-25。本文是 languages/cpp/ 主题入门层第 2 篇。STL（标准模板库）是 C++ 的"标准武器库"，容器 + 迭代器 + 算法三者配合，让大部分日常编程不用自己造轮子。选对容器，本身就是性能优化。

本文要回答的问题

• vector、list、map、unordered_map 怎么选？各自的时间复杂度？
• 迭代器是什么？为什么算法能"与容器无关"？
• 为什么 vector 通常比 list 快（尽管 list 插入是 O(1)）？

一、容器全景：四大类

类别	容器	特点	典型场景
顺序容器	vector	动态数组，连续内存	默认首选
顺序容器	list	双向链表	频繁中间插入删除
顺序容器	deque	双端队列	头尾都插入
关联容器	map / set	有序，红黑树	需要有序遍历
关联容器	unordered_map / unordered_set	哈希表，无序	快速查找
适配器	stack / queue / priority_queue	封装底层容器	特定数据结构

二、vector：默认首选

#include <vector>

std::vector<int> v;
v.push_back(1);         // 末尾追加
v.push_back(2);
v[0];                   // 随机访问 O(1)
v.size();               // 元素个数
v.reserve(100);         // 预分配容量，避免多次扩容

连续内存：vector 的元素在内存里连续存放，这对缓存极友好（顺序访问命中缓存行），是它快于 list 的根本原因。

扩容开销：push_back 超出容量时会重新分配更大的内存并拷贝所有元素（O(n)）。用 reserve 预分配可以避免。

三、迭代器：容器与算法的桥梁

迭代器是"泛化的指针"，让算法与容器解耦：

std::vector<int> v = {3, 1, 2};

// 迭代器遍历
for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it;   // *it 解引用，像指针
}

// 范围 for（底层也是迭代器）
for (int x : v) {
    std::cout << x;
}

迭代器类型	能力	容器
随机访问	it + n、it[n]	vector、deque
双向	++、--	list、map
前向	只能 ++	forward_list

四、map vs unordered_map

#include <map>
#include <unordered_map>

std::map<std::string, int> om;          // 有序：红黑树，O(log n)
std::unordered_map<std::string, int> hm; // 无序：哈希表，平均 O(1)

om["a"] = 1;
hm["a"] = 1;

特性	map	unordered_map
查找/插入复杂度	O(log n)	平均 O(1)，最坏 O(n)
有序性	按键有序	无序
内存占用	较小	较大（哈希桶）
适用	需要有序遍历、范围查询	纯快速查找

经验法则：只查不遍历用 unordered_map；需要有序或范围查询用 map。

五、算法：sort、find 等

#include <algorithm>

std::vector<int> v = {5, 2, 8, 1};

std::sort(v.begin(), v.end());              // 排序
auto it = std::find(v.begin(), v.end(), 8); // 查找
int cnt = std::count(v.begin(), v.end(), 1);// 计数

算法接收迭代器范围（begin/end），因此同一套算法能用在所有容器上——这就是"算法与容器解耦"。

六、容器选择与性能（衔接主线）

为什么 vector 通常比 list 快？

// list 插入是 O(1)，但遍历很慢
std::list<int> l;
for (int i = 0; i < 1000000; i++) l.push_back(i);

// vector 遍历是顺序读，缓存命中率高
std::vector<int> v;
v.reserve(1000000);
for (int i = 0; i < 1000000; i++) v.push_back(i);

虽然 list 的插入/删除是 O(1)，但它每个节点单独分配、内存不连续，遍历时缓存命中率极低（cache miss 多），实际可能比 vector 慢好几倍。

因素	vector	list
内存连续性	连续（缓存友好）	分散（缓存不友好）
随机访问	O(1)	O(n)
中间插入	O(n)（移动元素）	O(1)

关键认知：算法的理论复杂度（O 记号）不等于实际性能——缓存局部性（L3 内存子系统）往往更关键。这正是 本站性能主线 反复强调的。

七、与本站主线衔接

• 缓存局部性：容器内存布局决定缓存命中率，见 L3 缓存。
• 内存分配：push_back 扩容触发 malloc，高频分配成热点，见 perf 剖析。
• 模板机制：STL 全部基于模板实现，见 模板与泛型编程。

一句话总结

STL = 容器（vector 默认首选）+ 迭代器（泛化指针）+ 算法（与容器解耦）；选容器别只看理论复杂度，vector 的连续内存带来的缓存友好，常常让它比 O(1) 插入的 list 更快。

---

上一篇：类与对象　下一篇：异常安全与错误处理