C++ STL 容器与算法

六大组件

组件	作用	例子
容器	存储数据	vector, list, map, set
算法	操作数据	sort, find, transform
迭代器	连接容器与算法	begin(), end()
仿函数	行为像函数的对象	greater<int>()
适配器	改造接口	stack, queue, priority_queue
空间配置器	内存管理	allocator

三大核心容器

vector — 动态数组

vector<int> v = {1, 2, 3};
v.push_back(4);        // 尾部追加，O(1) 均摊
v.pop_back();          // 尾部删除
v[0] = 10;             // 随机访问 O(1)
v.insert(v.begin()+1, 99); // 中间插入 O(n)

// 遍历
for (auto &x : v) cout << x << " ";
for (auto it = v.begin(); it != v.end(); ++it) cout << *it;

选择：需要随机访问 + 尾部追加 → vector。

list — 双向链表

list<int> l = {1, 2, 3};
l.push_front(0);       // 头部插入 O(1)
l.push_back(4);        // 尾部插入 O(1)
l.insert(next(l.begin()), 99); // 中间插入 O(1) — 真正的优势

// ⚠️ 不能 l[0] 随机访问
// ✅ 自带 sort（比 std::sort 更适合链表）
l.sort();

选择：频繁中间插入/删除，不需要随机访问 → list。

map — 红黑树

map<string, int> m;
m["apple"] = 5;                    // 插入或更新 O(log n)
m.insert({"banana", 3});           // 插入（不覆盖已有键）

if (m.count("apple")) { }          // 判断存在
auto it = m.find("apple");         // 查找
if (it != m.end()) cout << it->second;

// 遍历（按键排序）
for (auto &[k, v] : m) cout << k << ": " << v;

选择：键值对 + 有序遍历 → map。无序用 unordered_map（哈希表 O(1)）。

常用算法

#include <algorithm>

vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

sort(v.begin(), v.end());                          // 升序
sort(v.begin(), v.end(), greater<int>());          // 降序

auto it = find(v.begin(), v.end(), 5);             // 查找
int cnt = count(v.begin(), v.end(), 1);            // 计数

reverse(v.begin(), v.end());                       // 翻转
auto it2 = unique(v.begin(), v.end());             // 去重（需先排序）

// Lambda 配合算法
auto pos = find_if(v.begin(), v.end(),
                   [](int x) { return x > 5; });   // 找第一个 >5
transform(v.begin(), v.end(), v.begin(),
          [](int x) { return x * 2; });            // 全部 ×2

性能速查

操作	vector	list	map	unordered_map
随机访问	O(1)	❌	❌	❌
头插	O(n)	O(1)	—	—
尾插	O(1)	O(1)	—	—
中间插	O(n)	O(1)	—	—
查找	O(n)	O(n)	O(log n)	O(1)
内存	连续	碎片	树节点	桶+链表