Cheatsheet: C++

Last updated on April 25, 2026 pm

本文整理 C++ 标准库（STL）常见容器的底层实现、核心特性、复杂度分析及适用场景，面向技术面试复习使用。

快速导航

顺序容器：vector、deque、list、array、forward_list
关联容器：set、map、multiset、multimap
无序容器：unordered_set、unordered_map 及其 multi 版本
容器适配器：stack、queue、priority_queue
STL 算法：sort、binary_search、lower_bound 等
智能指针：unique_ptr、shared_ptr、weak_ptr
字符串：string 常用操作

常见容器

顺序容器

vector

底层实现：动态数组，元素在内存中连续存储
核心特性：
- 随机访问 $O(1)$ ：通过下标直接访问，CPU 缓存友好
- 动态扩容：容量不足时自动扩容（通常 2 倍），均摊 $O(1)$
- 尾操作高效：尾部插入/删除 $O(1)$ ，中间操作 $O(n)$
- 内存紧凑：无额外开销，空间局部性最佳
适用场景：频繁随机访问、数据量已知或尾部增删为主的场景

常用操作：

// 构造
vector<int> v;
vector<int> v(n);           // n 个 0
vector<int> v(n, val);      // n 个 val
vector<int> v2(v1);         // 拷贝构造
vector<int> v2(move(v1));   // 移动构造 (C++11)

// 元素访问
v[i]                        // 下标访问，无边界检查
v.at(i)                     // 有边界检查，越界抛异常
v.front()                   // 首元素
v.back()                    // 末元素

// 迭代器
v.begin(), v.end()          // 首尾迭代器
v.rbegin(), v.rend()        // 反向迭代器

// 容量
v.size()                    // 元素个数
v.empty()                   // 是否为空
v.capacity()                // 当前容量
v.reserve(n)                // 预留空间（不创建元素）
v.shrink_to_fit()           // 释放多余容量 (C++11)

// 修改
v.push_back(x)              // 尾部添加
v.pop_back()                // 尾部删除
v.insert(it, x)             // 在 it 前插入，返回新元素迭代器
v.insert(it, n, x)          // 插入 n 个 x
v.erase(it)                 // 删除 it 位置元素，返回下一个迭代器
v.erase(first, last)        // 删除区间 [first, last)
v.clear()                   // 清空
v.resize(n)                 // 调整大小，多删少补 0
v.resize(n, val)            // 调整大小，多删少补 val
v.swap(v2)                  // 交换两个 vector

// C++11 新增
v.emplace_back(args...)     // 原地构造，比 push_back 更高效
v.emplace(it, args...)      // 在 it 前原地构造

复杂度：

操作	复杂度	说明
随机访问	$O(1)$	连续内存
push_back	$O(1)$ amortized	均摊，扩容时 $O(n)$
emplace_back	$O(1)$ amortized	原地构造，避免拷贝
pop_back	$O(1)$	尾部删除
front/back	$O(1)$	首尾访问
insert	$O(n)$	中间插入，需移动元素
erase	$O(n)$	中间删除，需移动元素
clear	$O(n)$	逐个析构
resize	$O(n)$	需构造/析构元素
reserve	$O(n)$	重新分配内存

迭代器失效：
- insert、emplace：若引起重新分配，则所有迭代器失效；否则插入点之后失效
- push_back、emplace_back：若引起重新分配，则所有迭代器失效
- erase：被删除元素及之后迭代器失效
- resize、clear：所有迭代器失效
- reserve、shrink_to_fit：若引起重新分配，则所有迭代器失效

deque

底层实现：分块数组（chunked array），多块定长缓冲区 + 中央控制结构
核心特性：
- 双端操作 $O(1)$ ：头尾插入/删除都是常数时间，优于 vector
- 随机访问 $O(1)$ ：通过块指针快速定位，略慢于 vector
- 无需重新分配：头尾扩展只需添加新块，不会移动已有元素
- 迭代器更复杂：迭代器需要维护块指针和块内偏移
适用场景：双端队列、滑动窗口、需要两端操作的场景
vs vector：deque 头操作 $O(1)$ vs vector $O(n)$ ；vector 缓存局部性更好

常用操作：

// 构造
deque<int> dq;
deque<int> dq(n, val);

// 元素访问
dq[i]                       // 下标访问 $O(1)$
dq.at(i)                    // 有边界检查
dq.front()                  // 首元素
dq.back()                   // 末元素

// 迭代器
dq.begin(), dq.end()

// 容量
dq.size(), dq.empty()

// 修改 - 双端操作是核心优势
dq.push_front(x)            // 头部添加 $O(1)$
dq.push_back(x)             // 尾部添加 $O(1)$
dq.pop_front()              // 头部删除 $O(1)$
dq.pop_back()               // 尾部删除 $O(1)$
dq.insert(it, x)            // 中间插入 $O(n)$
dq.erase(it)                // 中间删除 $O(n)$
dq.clear()

复杂度：

操作	复杂度	说明
随机访问	$O(1)$	分段连续，略慢于 vector
push_front	$O(1)$	头部插入，优于 vector
push_back	$O(1)$	尾部插入
pop_front	$O(1)$	头部删除，优于 vector
pop_back	$O(1)$	尾部删除
insert/erase	$O(n)$	中间操作需移动元素
front/back	$O(1)$	首尾访问

vs vector：
- deque 支持 $O(1)$ 头部插入/删除，vector 是 $O(n)$
- deque 不会重新分配内存（除非极端情况）
- vector 内存更紧凑，缓存友好性更好

array（C++11）

底层实现：静态数组封装，大小在编译期确定，栈上分配
核心特性：
- 零开销抽象：性能和原生数组完全一致，无额外开销
- 标准容器接口：支持 .size()、迭代器、STL 算法、范围 for
- 值语义：支持拷贝、赋值、作为函数返回值（原生数组不行）
- 安全访问：提供 .at() 边界检查版本
适用场景：大小固定的场景，需要容器特性但又不想用动态内存

常用操作：

#include <array>

array<int, 5> arr;           // 大小必须是编译期常量
array<int, 5> arr = {1,2,3,4,5};
array<int, 5> arr = {1};     // 第一个为 1，其余为 0

// 元素访问
arr[i]                      // 无边界检查
arr.at(i)                   // 有边界检查
arr.front(), arr.back()     // 首尾
arr.data()                  // 返回原生指针

// 容量
arr.size()                  // 返回 N
arr.empty()                 // 恒为 false（除非 N=0）
arr.max_size()              // 等于 size()

// 修改
arr.fill(val)               // 全部填充为 val
arr.swap(arr2)              // 交换两个 array（大小必须相同）

// 迭代器
arr.begin(), arr.end()

复杂度：所有操作都是 $O(1)$
vs 原生数组：
- 有 .size() 方法，可作为容器使用
- 支持迭代器、STL 算法
- 支持拷贝赋值（原生数组不行）

forward_list（C++11 单向链表）

底层实现：单向链表，每个节点只存储 next 指针
核心特性：
- 最小内存开销：比 list 少一个 prev 指针（在 64 位系统节省 8 字节/节点）
- 单向遍历：只能从头到尾遍历，不支持反向迭代器
- 头操作 $O(1)$ ：push_front、pop_front、insert_after
- 无 size() 方法：获取长度需遍历 $O(n)$ （为了节省存储）
- 无尾指针：因此没有 push_back、back()、.size()
适用场景：内存极度敏感、只需单向遍历、头插为主的场景

常用操作：

#include <forward_list>

forward_list<int> fl;
forward_list<int> fl(n, val);

// 元素访问 - 只有 front()
fl.front()                  // 首元素，无 back()

// 迭代器
fl.begin(), fl.end()        // 只有正向迭代器
fl.before_begin()           // 首元素之前的位置

// 修改
fl.push_front(x)            // 头部插入 $O(1)$
fl.pop_front()              // 头部删除 $O(1)$

// insert/erase 需用 before_begin
fl.insert_after(it, x)      // 在 it 之后插入，返回新位置
fl.insert_after(it, n, x)   // 插入 n 个
fl.erase_after(it)          // 删除 it 之后元素，返回下一个
fl.erase_after(first, last) // 删除区间

fl.clear()

// 特有操作
fl.splice_after(it, fl2)    // 将 fl2 移到 it 之后
fl.merge(fl2)               // 合并有序链表
fl.sort()
fl.reverse()
fl.unique()
fl.remove(x)
fl.remove_if(pred)

复杂度：

操作复杂度

push_front $O(1)$

pop_front $O(1)$

insert_after $O(1)$

erase_after $O(1)$

查找 $O(n)$
vs list：内存占用更小（少一个 prev 指针），只支持单向遍历，不支持 push_back/pop_back

操作	复杂度
push_front	$O(1)$
pop_front	$O(1)$
insert_after	$O(1)$
erase_after	$O(1)$
查找	$O(n)$

list（双向链表）

底层实现：双向链表，每个节点存储 prev 和 next 指针
核心特性：
- 插入删除 $O(1)$ ：已知位置时，插入/删除操作只需调整指针
- 无随机访问：不支持 []，访问第 n 个元素需遍历 $O(n)$
- 双向遍历：支持正向和反向迭代器
- 稳定迭代器：insert、splice 不使任何迭代器失效
- 内存开销大：每个节点有额外两个指针开销，缓存局部性差
独有优势：splice 操作可实现 $O(1)$ 元素移动（其他容器做不到）
适用场景：频繁中间插入删除、需要稳定迭代器的场景

常用操作：

list<int> lst;
list<int> lst(n, val);

// 元素访问
lst.front()                 // 首元素
lst.back()                  // 末元素
// 无 [] 操作，不支持随机访问

// 迭代器
lst.begin(), lst.end()

// 修改
lst.push_front(x)           // 头部插入 $O(1)$
lst.push_back(x)            // 尾部插入 $O(1)$
lst.pop_front()             // 头部删除 $O(1)$
lst.pop_back()              // 尾部删除 $O(1)$
lst.insert(it, x)           // 在 it 前插入，返回新位置 $O(1)$
lst.erase(it)               // 删除 it 位置，返回下一个 $O(1)$
lst.clear()

// list 特有操作（面试重点！）
lst.splice(it, lst2)              // 将 lst2 全部移到 it 前，清空 lst2，$O(1)$
lst.splice(it, lst2, it2)         // 将 lst2 中 it2 移到 it 前，$O(1)$
lst.splice(it, lst2, first, last) // 将 [first,last) 移到 it 前，$O(n)$

lst.merge(lst2)               // 合并两个有序 list，结果有序，lst2 变空，$O(n)$
lst.merge(lst2, comp)         // 带自定义比较函数

lst.sort()                  // 链表专用排序，$O(n \log n)$，优于 std::sort
lst.sort(comp)

lst.unique()                // 删除连续重复元素，$O(n)$
lst.unique(pred)            // 带谓词

lst.reverse()               // 反转链表，$O(n)$

lst.remove(x)               // 删除所有值为 x 的元素，$O(n)$
lst.remove_if(pred)         // 删除满足条件的元素

lst.swap(lst2)

复杂度：

操作	复杂度	说明
push_front/back	$O(1)$	两端插入
pop_front/back	$O(1)$	两端删除
insert/erase	$O(1)$	已知位置（关键！）
splice	$O(1)/O(n)$	单个元素 $O(1)$ ，区间 $O(n)$
front/back	$O(1)$	首尾访问
查找	$O(n)$	需遍历
sort	$O(n \log n)$	链表专用排序
merge	$O(n)$	合并有序链表
reverse	$O(n)$	反转
unique	$O(n)$	去重

面试要点：
- splice 是 list 独有的高效操作，可实现 $O(1)$ 元素移动
- sort 使用归并排序，比 std::sort 更适合链表
- 迭代器失效：insert、splice 不使任何迭代器失效；erase 只使被删元素迭代器失效

有序关联容器（基于红黑树）

set

底层实现：红黑树（自平衡二叉搜索树），保证高度平衡
核心特性：
- 自动排序：元素始终有序（默认升序），遍历时按序输出
- 唯一性：不允许重复元素，插入重复值会失败
- 对数操作：插入、删除、查找都是 $O(\log n)$
- 稳定迭代器：除被删除元素外，其他迭代器在插入时不失效
- 有序查询：支持 lower_bound、upper_bound 等范围查询
适用场景：需要有序唯一集合、范围查询、按序遍历的场景

常用操作：

set<int> s;
set<int, greater<int>> s;  // 降序

// 插入
s.insert(x)                 // 插入 x，返回 pair<iterator,bool>
s.emplace(args...)          // 原地构造插入，更高效
s.insert(it_hint, x)        // 带提示位置的插入，若提示正确则为 $O(1)$ amortized

// 删除
s.erase(x)                  // 删除值为 x 的元素，返回删除个数（0 或 1）
s.erase(it)                 // 删除迭代器指向元素，$O(1)$
s.erase(first, last)        // 删除区间
s.clear()                   // 清空

// 查找 - 面试重点！
s.find(x)                   // 查找 x，返回迭代器，找不到返回 s.end()
s.count(x)                  // 统计 x 个数（set 中只能是 0 或 1）

// 范围查询 - 面试高频！
s.lower_bound(x)            // 第一个 >= x 的元素，返回迭代器
s.upper_bound(x)            // 第一个 > x 的元素，返回迭代器
s.equal_range(x)            // 返回 pair<lower, upper>，set 中范围最多一个元素

// 容量
s.size(), s.empty()
s.max_size()

// 迭代器（有序遍历）
s.begin(), s.end()          // 升序
s.rbegin(), s.rend()        // 降序

// 其他
s.contains(x)               // C++20，判断是否包含，返回 bool
s.swap(s2)

复杂度：

操作	复杂度	说明
insert/emplace	$O(\log n)$	红黑树插入
erase	$O(\log n)$	删除
find	$O(\log n)$	查找
count	$O(\log n)$	计数
lower_bound	$O(\log n)$	下界查询
upper_bound	$O(\log n)$	上界查询
equal_range	$O(\log n)$	范围查询
size/empty	$O(1)$
begin/end	$O(1)$

面试要点：
- lower_bound(x)：找第一个 不小于 x 的元素（>=）
- upper_bound(x)：找第一个大于 x 的元素 (>)
- 用 lower_bound 和 upper_bound 可实现范围查询
- 遍历得到的是 有序序列
- 迭代器指向 const 元素（不可修改，会破坏有序性）

multiset / multimap

底层实现：与 set/map 相同（红黑树），但允许键重复
核心特性：
- 允许重复：相同值的元素可共存，按插入顺序排列（C++11 起）
- 范围查找：equal_range 返回重复元素的范围
- 计数操作：count 返回重复键的数量 $O(\log n + k)$
- 删除策略：erase(key) 删除所有匹配键，erase(it) 删除单个
适用场景：需要存储重复值的有序集合、多重映射关系

常用操作：

multiset<int> ms;

ms.insert(x)                // 插入（允许重复）
ms.count(x)                 // 返回 x 的个数，$O(\log n + k)$，k 为个数
ms.find(x)                  // 返回第一个找到的迭代器
ms.equal_range(x)           // 返回等于 x 的所有元素范围
ms.erase(x)                 // 删除所有值为 x 的元素
ms.erase(it)                // 删除单个元素

复杂度：与 set 相同，但 count、equal_range、erase(x) 为 $O(\log n + k)$

map

底层实现：红黑树存储 pair<const Key, T>，按 Key 排序
核心特性：
- 有序 key-value：按键自动排序，遍历时按键序输出
- 唯一键：每个 key 对应唯一 value
- [] 副作用：mp[key] 在 key 不存在时会自动插入默认值
- 迭代器特性：迭代器指向 pair<const Key, T>，key 不可修改
- at() 安全访问：带边界检查，不存在抛 out_of_range
适用场景：需要按键查找的有序字典、范围查询、区间操作

自定义排序（面试重点！）：

// 方式 1：使用标准库提供的比较器
map<int, string, greater<int>> mp;     // 降序排列
map<int, string, less<int>> mp;          // 升序（默认）

// 方式 2：自定义比较函数对象（类似 priority_queue）
struct Person {
    string name;
    int age;
};

// 按 age 降序，age 相同按 name 升序
struct ComparePerson {
    bool operator()(const Person& a, const Person& b) const {
        if (a.age != b.age)
            return a.age > b.age;        // age 大的排前面
        return a.name < b.name;          // name 小的排前面
    }
};

map<Person, int, ComparePerson> mp;      // Person 作为 key，需自定义比较

// 方式 3：使用 Lambda（C++14 起）
auto cmp = [](const string& a, const string& b) {
    return a.length() < b.length();        // 按字符串长度排序
};
map<string, int, decltype(cmp)> mp(cmp);   // 需将 lambda 传入构造函数

// 方式 4：使用 std::function（灵活但性能稍差）
map<string, int, function<bool(const string&, const string&)>> mp(
    [](const string& a, const string& b) {
        return a > b;                     // 降序
    }
);

⚠️ 重要：map 的比较函数必须定义 严格弱序（Strict Weak Ordering）：

反自反性：cmp(a, a) 必须为 false
非对称性：若 cmp(a, b) 为 true，则 cmp(b, a) 必须为 false
传递性：若 cmp(a, b) 和 cmp(b, c) 为 true，则 cmp(a, c) 为 true
不可比较相等性：!(cmp(a, b) || cmp(b, a)) 表示 a 和 b 等价

常用操作：

map<string, int> mp;
map<string, int, greater<string>> mp;  // 降序

// 插入
mp[key] = value             // 若 key 存在则覆盖，不存在则创建（value 默认构造）
mp.insert({key, value})     // 返回 pair<iterator,bool>
mp.insert(make_pair(k, v))
mp.emplace(k, v)            // 原地构造

// 访问
mp[key]                     // 访问/创建，若不存在会插入默认值
mp.at(key)                  // 访问，不存在抛 out_of_range
mp.find(key)                // 返回迭代器，找不到返回 mp.end()
mp.count(key)               // 0 或 1

// 范围查询（同 set）
mp.lower_bound(key)         // 第一个 >= key 的 pair
mp.upper_bound(key)         // 第一个 > key 的 pair
mp.equal_range(key)

// 遍历 - 按 key 有序
for (auto& [k, v] : mp) {    // C++17 结构化绑定
    cout << k << " " << v << endl;
}
for (auto it = mp.begin(); it != mp.end(); ++it) {
    cout << it->first << " " << it->second << endl;
}

// 修改
mp.erase(key)               // 按 key 删除
mp.erase(it)                // 按迭代器删除
mp.clear()

// 检查存在性（C++20）
if (mp.contains(key)) { }

复杂度：

操作	复杂度
operator[]	$O(\log n)$
at/find	$O(\log n)$
insert/emplace	$O(\log n)$
erase	$O(\log n)$
lower/upper_bound	$O(\log n)$

注意：mp[key] 在 key 不存在时会自动插入默认值（对于 int 是 0），这可能带来副作用

无序关联容器（Hash）

unordered_set / unordered_map

底层实现：哈希表（散列表），拉链法或开放寻址法处理冲突
核心特性：
- 平均 $O(1)$ ：哈希函数分布良好时，查找/插入/删除接近常数时间
- 无序存储：遍历顺序与插入顺序无关，与键值哈希值相关
- rehash 开销：负载因子过高时会重新哈希，导致一次操作 $O(n)$
- 迭代器不稳定：rehash 时所有迭代器失效
- 自定义哈希：可为任意类型定义哈希函数（需满足 std::hash 要求）
负载因子：load_factor() = size() / bucket_count()，默认最大 1.0
适用场景：只需快速查找、不需要顺序、哈希冲突不严重的场景

常用操作：

#include <unordered_set>
#include <unordered_map>

unordered_set<int> us;
unordered_map<string, int> um;

// 构造与设置
unordered_set<int> us;
us.reserve(n);               // 预留桶数量，减少 rehash
us.max_load_factor(0.7);   // 设置负载因子，默认 1.0

// 基本操作（同 set/map）
us.insert(x)
us.emplace(args...)
us.erase(x) / us.erase(it)
us.find(x)                  // 返回迭代器，找不到返回 us.end()
us.count(x)                 // 0 或 1
us.contains(x)              // C++20
us.clear()
us.size(), us.empty()

// unordered_map 特有
um[key] = value
um.at(key)
um.find(key)
um.insert({k, v})
um.emplace(k, v)

// 桶操作（了解即可）
us.bucket_count()           // 当前桶数
us.bucket_size(i)           // 第 i 个桶的元素数
us.load_factor()            // 当前负载因子（size/bucket_count）
us.rehash(n)                // 设置桶数为 >= n

复杂度：

操作	平均	最坏	说明
insert/emplace	$O(1)$	$O(n)$	均摊，rehash 时最坏
erase	$O(1)$	$O(n)$
find/count	$O(1)$	$O(n)$	哈希冲突严重时退化
operator[]	$O(1)$	$O(n)$	map 专用

vs set/map：
- 优点：平均操作更快 $O(1)$ ，不需要元素可比较（只需可哈希）
- 缺点：无序遍历、最坏情况 $O(n)$ 、需要自定义哈希函数、内存开销大

自定义哈希函数：

struct PairHash {
    size_t operator()(const pair<int,int>& p) const {
        return hash<int>()(p.first) ^ (hash<int>()(p.second) << 1);
    }
};
unordered_set<pair<int,int>, PairHash> us;

unordered_multiset / unordered_multimap

底层实现：与 unordered_set/map 相同（哈希表），但允许键重复
核心特性：
- 桶内链式存储：相同哈希值的元素在同一桶内形成链表
- 查找退化：count、equal_range、erase(key) 需遍历桶内元素
- 迭代器稳定性：只有 rehash 使迭代器失效，插入/删除不影响其他元素
- 删除策略：erase(key) 删除桶内所有匹配键
适用场景：需要存储重复键的哈希表，如统计频率、多重索引

常用操作：

unordered_multiset<int> ums;
ums.insert(x)               // 允许重复
ums.count(x)                // 返回 x 的个数（需遍历桶）
ums.equal_range(x)          // 返回等于 x 的所有元素
ums.find(x)                 // 返回第一个找到的

注意：由于允许重复，count、equal_range、erase(x) 可能更慢

容器选择速查表（面试重点）

场景需求	推荐容器	理由
频繁随机访问	`vector`	$O(1)$ 随机访问，缓存友好
频繁头尾插入/删除	`deque`	两端 $O(1)$
频繁中间插入/删除	`list` / `forward_list`	已知位置 $O(1)$
需要有序遍历 + 去重	`set`	自动排序，唯一键
需要有序遍历 + 允许重复	`multiset`	自动排序，允许重复
需要 key-value 有序	`map`	按键排序
只需快速查找，无需顺序	`unordered_set/map`	平均 $O(1)$
实现 LRU Cache	`list` + `unordered_map`	list 维护顺序，map 快速查找
LIFO 场景	`stack`	后进先出
FIFO 场景	`queue`	先进先出
TopK 问题	`priority_queue`	堆结构天然支持
固定大小数组	`array`	栈分配，无动态开销

迭代器失效总结（面试必考！）

容器	使迭代器失效的操作
`vector`	`insert`、`push_back`、`emplace_back`（可能 reallocate，全部失效）；`erase`（被删及之后失效）；`resize`、`clear`、reserve、shrink_to_fit
`deque`	`insert`、`erase`（所有迭代器失效，除了头尾操作）；`resize`、`clear`
`list`	只有 `erase` 使被删元素迭代器失效；`insert`、`splice` 不使任何迭代器失效
`forward_list`	同 `list`
`set/map`	`erase` 使被删元素迭代器失效；`insert`、`emplace` 不使迭代器失效（树结构稳定）
`unordered_set/map`	`erase` 使被删元素迭代器失效；`rehash` 使全部迭代器失效

安全删除技巧：

// vector/list/set/map 通用
for (auto it = c.begin(); it != c.end(); ) {
    if (shouldRemove(*it)) {
        it = c.erase(it);  // erase 返回下一个有效迭代器
    } else {
        ++it;
    }
}

适配器（Adapters）

容器适配器是基于其他容器实现的包装器，提供特定接口。

stack（栈 - LIFO）

底层实现：容器适配器，默认封装 deque，可选 vector 或 list
核心特性：
- 后进先出：只允许在栈顶操作，天然支持函数调用栈、括号匹配等场景
- 无迭代器：不提供遍历功能，只能访问栈顶元素
- 底层可定制：stack<int, vector<int>> 使用 vector 作为底层
- 操作受限：仅 push、pop、top、empty、size
适用场景：表达式求值、括号匹配、DFS 深度优先搜索、回溯算法

常用操作：

#include <stack>

stack<int> st;                           // 默认 deque
stack<int, vector<int>> st2;            // 基于 vector
stack<int, list<int>> st3;              // 基于 list

// 基本操作
st.push(x)               // 压栈 $O(1)$
st.pop()                 // 出栈 $O(1)$
st.top()                 // 访问栈顶 $O(1)$
st.empty()               // 是否为空 $O(1)$
st.size()                // 元素个数 $O(1)$

// 比较
if (st1 == st2) { }      // 元素逐个比较

复杂度：所有操作均为 $O(1)$
注意：pop() 不返回元素，需先 top() 获取再 pop()

queue（队列 - FIFO）

底层实现：容器适配器，默认封装 deque，可选 list
核心特性：
- 先进先出：队尾入队、队头出队，天然支持 BFS、任务调度
- 双端访问：可同时访问队头 front() 和队尾 back()
- 无迭代器：不支持遍历，只能访问两端元素
- 底层限制：不能用 vector（vector 没有 pop_front）
适用场景：BFS 广度优先搜索、任务队列、缓冲处理、生产者-消费者模型

常用操作：

#include <queue>

queue<int> q;                            // 默认 deque
queue<int, list<int>> q2;                // 基于 list

// 基本操作
q.push(x)                // 入队（队尾）$O(1)$
q.pop()                  // 出队（队头）$O(1)$
q.front()                // 访问队头 $O(1)$
q.back()                 // 访问队尾 $O(1)$
q.empty()                // 是否为空 $O(1)$
q.size()                 // 元素个数 $O(1)$

// 比较
if (q1 == q2) { }

复杂度：所有操作均为 $O(1)$

priority_queue（优先队列 - 堆）

底层实现：容器适配器，基于 vector + 堆操作（push_heap、pop_heap）
核心特性：
- 堆结构：默认大顶堆（最大元素在 top），可用 greater 改为小顶堆
- 不完全有序：只保证堆顶是最大/最小，其余元素仅满足堆性质
- 无迭代器：不支持遍历，只能访问堆顶
- 原地建堆：heapify 过程利用 vector 的连续内存，缓存友好
底层实现：vector 存储完全二叉树，父节点 $i$ 的子节点为 $2i+1$ 、 $2i+2$
适用场景：TopK 问题、合并 K 个有序数组、任务调度（按优先级）、Dijkstra 算法

常用操作：

#include <queue>

// 构造
priority_queue<int> pq;                  // 最大堆（默认 less<T>）
priority_queue<int, vector<int>, greater<int>> pq;  // 最小堆

// 基本操作
pq.push(x)               // 入堆 $O(\log n)$
pq.pop()                 // 出堆（最大值）$O(\log n)$
pq.top()                 // 访问堆顶 $O(1)$
pq.empty()               // 是否为空 $O(1)$
pq.size()                // 元素个数 $O(1)$

// C++11 新增
pq.emplace(args...)      // 原地构造，比 push 更高效
pq.swap(pq2)             // 交换两个优先队列

// 自定义比较函数（面试重点！）
struct Task {
    int priority;
    int timestamp;
    bool operator>(const Task& other) const {  // 用于 greater
        if (priority == other.priority)
            return timestamp > other.timestamp;
        return priority > other.priority;
    }
};
priority_queue<Task, vector<Task>, greater<Task>> pq;  // 最小堆

// 或者使用函数对象
struct cmp {
    bool operator()(const Task& a, const Task& b) {
        if (a.priority == b.priority)
            return a.timestamp > b.timestamp;  // 时间小的优先
        return a.priority < b.priority;       // 优先级大的优先
    }
};
priority_queue<Task, vector<Task>, cmp> pq;

复杂度：

操作复杂度

push $O(\log n)$

emplace $O(\log n)$

pop $O(\log n)$

top $O(1)$

empty/size $O(1)$
底层实现：vector 存储完全二叉树，父节点索引 $i$ 的左右子节点为 $2i+1$ 、 $2i+2$
面试要点：
- 默认 less<T> 产生大顶堆（最大元素在 top）
- greater<T> 产生小顶堆（最小元素在 top）
- 自定义比较函数时，返回 true 表示 a 的优先级低于 b（即 b 会在 a 上面）

操作	复杂度
push	$O(\log n)$
emplace	$O(\log n)$
pop	$O(\log n)$
top	$O(1)$
empty/size	$O(1)$

常见输入输出

基础输入输出

cin / cout：

#include <iostream>

int a;
cin >> a;

int x, y;
cin >> x >> y;  // 可以连续读取

string s;
cin >> s;       // 读到空白符（空格、换行、制表）为止

cout << a << endl;
cout << "Value: " << x << " " << y << endl;

cin 状态检查：

if (cin >> x) {          // 检查是否成功读取
    // 成功
}

if (cin.fail()) {        // 检查是否失败
    cin.clear();         // 清除错误状态
    cin.ignore(1000, '\n');  // 忽略缓冲区内容
}

while (cin >> x) { }     // 读到 EOF 或错误时停止

读取字符串

cin >> string：读到空白符停止

getline：读取整行（包含空格）：

1 2	`string line; getline(cin, line); // 读取一行，包括换行符前的所有字符`

混合使用时的注意点：

int n;
cin >> n;
cin.ignore();            // 吃掉 n 后的换行符！
getline(cin, line);      // 现在能正确读取下一行

多组输入处理

不定长输入 / 读到 EOF：

int x;
while (cin >> x) {       // Windows: Ctrl+Z 结束；Linux: Ctrl+D 结束
    // 处理 x
}

已知数据组数：

int T;
cin >> T;
while (T--) {
    // 处理每组数据
}

特定结束标志：

int a, b;
while (cin >> a >> b) {
    if (a == 0 && b == 0) break;  // 0 0 表示结束
    // 处理
}

字符串流 stringstream

整行解析：

#include <sstream>

string line;
getline(cin, line);

stringstream ss(line);
int x;
while (ss >> x) {        // 从行中逐个读取数字
    // 处理 x
}

类型转换：

// int -> string
stringstream ss;
ss << 123;
string s = ss.str();     // "123"

// string -> int
stringstream ss2("456");
int x;
ss2 >> x;                // x = 456

// C++11 更简洁的方式
int x = stoi("123");     // string to int
long y = stol("456");
double z = stod("3.14");

string s = to_string(789);  // "789"

分割字符串：

string line = "apple,banana,cherry";
stringstream ss(line);
string item;
while (getline(ss, item, ',')) {  // 按逗号分割
    cout << item << endl;
}

输出格式控制（iomanip）

精度控制：

#include <iomanip>

double x = 3.14159265;

cout << fixed << setprecision(2) << x;  // 3.14（固定小数位）
cout << scientific << x;                  // 科学计数法 3.14e+00
cout << defaultfloat << x;                // 恢复默认

宽度与对齐：

cout << setw(10) << 123;        // 总宽度 10，右对齐（默认）
cout << left << setw(10) << 123;  // 左对齐
cout << right << setw(10) << 123; // 右对齐
cout << setfill('0') << setw(5) << 123;  // 00123

进制控制：

int x = 255;
cout << hex << x;               // ff（十六进制）
cout << oct << x;               // 377（八进制）
cout << dec << x;               // 255（十进制，默认）
cout << hex << uppercase << x;  // FF（大写十六进制）
cout << showbase << hex << x;   // 0xff（显示前缀）
cout << noshowbase << dec;      // 恢复

布尔值输出：

1 2	`cout << boolalpha << true; // 输出 "true" cout << noboolalpha << true; // 输出 "1"`

文件输入输出

基础文件操作：

#include <fstream>

// 写入文件
ofstream out("output.txt");
out << "Hello, World!" << endl;
out << 123 << " " << 3.14 << endl;
out.close();

// 读取文件
ifstream in("input.txt");
string line;
while (getline(in, line)) {
    cout << line << endl;
}
in.close();

文件状态检查：

ifstream in("data.txt");
if (!in) {                       // 检查是否成功打开
    cerr << "无法打开文件!" << endl;
    return 1;
}

if (in.eof())  { /* 到达文件尾 */ }
if (in.fail()) { /* 操作失败 */ }
if (in.bad())  { /* 严重错误 */ }
if (in.good()) { /* 一切正常 */ }

打开模式：

ofstream out("file.txt", ios::out);       // 写入（默认，会覆盖）
ofstream out("file.txt", ios::app);       // 追加写入
ofstream out("file.txt", ios::trunc);     // 截断（清空）后写入
ifstream in("file.txt", ios::in);         // 读取（默认）
fstream io("file.txt", ios::in | ios::out); // 读写

// 二进制模式
ofstream out("data.bin", ios::binary);

快速输入输出优化

关闭同步与解绑：

1 2	`ios::sync_with_stdio(false); // 关闭 C++ 流与 C 流的同步 cin.tie(nullptr); // 解除 cin 与 cout 的绑定`

必须在程序开头、任何 I/O 操作前调用
使用后不要混用 cin/cout 与 scanf/printf

大量输出优化：

// 使用 '\n' 代替 endl（endl 会强制刷新缓冲区）
cout << "Hello\n";  // 快
cout << "Hello" << endl;  // 慢，会 flush

// 批量输出后统一刷新
cout << ... << '\n';
cout << ... << '\n';
cout.flush();  // 最后统一刷新

printf / scanf（C 风格）

常用格式说明符：

int x; scanf("%d", &x);           // 整数
long long y; scanf("%lld", &y);   // 长整数
double d; scanf("%lf", &d);     // double
float f; scanf("%f", &f);       // float
char c; scanf(" %c", &c);       // 字符（前导空格吃掉空白）
char s[100]; scanf("%s", s);    // 字符串（不含空格）
scanf("%d,%d", &a, &b);         // 按格式 "12,34" 读取

输出格式：

printf("%d\n", x);              // 整数
printf("%lld\n", x);             // long long
printf("%.2f\n", d);             // 保留 2 位小数
printf("%10d\n", x);             // 宽度 10，右对齐
printf("%-10d\n", x);            // 宽度 10，左对齐
printf("%010d\n", x);             // 宽度 10，前补 0
printf("%x\n", x);               // 十六进制
printf("%o\n", x);               // 八进制
printf("%e\n", d);               // 科学计数法

格式控制速查表

功能	iostream	printf
固定小数位	`fixed << setprecision(2)`	`%.2f`
宽度 10 右对齐	`setw(10) << right`	`%10d`
宽度 10 左对齐	`setw(10) << left`	`%-10d`
前补 0	`setfill('0') << setw(5)`	`%05d`
十六进制	`hex`	`%x` / `%X`
八进制	`oct`	`%o`
科学计数法	`scientific`	`%e`

常用算法（STL Algorithm）

所有算法都在 <algorithm> 头文件中。

排序算法

sort - 快速排序（不稳定）：

#include <algorithm>

vector<int> v = {3, 1, 4, 1, 5};
sort(v.begin(), v.end());                    // 升序
sort(v.begin(), v.end(), greater<int>());    // 降序

// 自定义比较
sort(v.begin(), v.end(), [](int a, int b) {
    return a > b;  // 降序
});

// 部分排序
sort(v.begin(), v.begin() + 3);  // 只排序前 3 个

复杂度： $O(n \log n)$
不稳定排序（相等元素相对顺序可能改变）

stable_sort - 稳定排序：
1
stable_sort(v.begin(), v.end()); // 保证相等元素相对顺序不变
- 复杂度： $O(n \log n)$ 或 $O(n \log^2 n)$ （取决于内存）
- 稳定排序

partial_sort - 部分排序（前 k 小）：

1 2	`// 将最小的 k 个元素放到前面并排序，其余无序 partial_sort(v.begin(), v.begin() + k, v.end());`

nth_element - 快速选择（第 k 小）：

1
2
3

// 将第 k 小元素放到位置 k，左边都小于它，右边都大于它
nth_element(v.begin(), v.begin() + k, v.end());
// 类似快速排序的 partition，复杂度平均 O(n)

reverse - 反转：
1
reverse(v.begin(), v.end());

rotate - 旋转：

1
2
3

// 将 [first, middle) 移到末尾，[middle, last) 移到开头
rotate(v.begin(), v.begin() + k, v.end());
// 如 {1,2,3,4,5} k=2 -> {3,4,5,1,2}

查找算法

find / find_if - 线性查找：

auto it = find(v.begin(), v.end(), x);  // 找值等于 x 的元素
if (it != v.end()) { /* 找到 */ }

// 条件查找
auto it = find_if(v.begin(), v.end(), [](int x) {
    return x > 5;
});

复杂度： $O(n)$

binary_search - 二分查找（要求有序）：
1
2
// 要求容器已升序排列 bool found = binary_search(v.begin(), v.end(), x);
- 复杂度： $O(\log n)$
- 只返回是否存在，不返回位置

lower_bound / upper_bound - 二分找位置：

// 第一个 >= x 的位置
auto it = lower_bound(v.begin(), v.end(), x);
// 第一个 > x 的位置
auto it = upper_bound(v.begin(), v.end(), x);

复杂度： $O(\log n)$
配合 distance 获取下标：int pos = distance(v.begin(), it);

equal_range - 二分找范围：

auto range = equal_range(v.begin(), v.end(), x);
// range.first = lower_bound
// range.second = upper_bound
// 个数 = range.second - range.first

数值算法（`<numeric>`）

accumulate - 累加：

#include <numeric>

int sum = accumulate(v.begin(), v.end(), 0);          // 求和
int prod = accumulate(v.begin(), v.end(), 1, multiplies<int>());  // 求积

max_element / min_element - 最值：

auto it = max_element(v.begin(), v.end());
int maxVal = *it;
int maxIdx = distance(v.begin(), it);

auto it2 = min_element(v.begin(), v.end());

auto range = minmax_element(v.begin(), v.end());  // C++11，同时返回 min 和 max

inner_product - 内积：

1	`int dot = inner_product(a.begin(), a.end(), b.begin(), 0);`

集合算法（要求有序）

set_union / set_intersection / set_difference：

vector<int> a = {1, 2, 3, 4};
vector<int> b = {3, 4, 5, 6};
vector<int> result;

// 并集
set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));
// 交集
set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));
// 差集 (a - b)
set_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));
// 对称差集
set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));

merge - 归并（要求两个序列有序）：

1 2	`vector<int> result; merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));`

其他常用算法

count / count_if - 计数：

1 2	`int cnt = count(v.begin(), v.end(), x); // 统计 x 出现次数 int cnt = count_if(v.begin(), v.end(), [](int x) { return x > 5; });`

for_each - 遍历：

1	`for_each(v.begin(), v.end(), [](int& x) { x *= 2; }); // 每个元素乘 2`

transform - 变换：

vector<int> result;
transform(v.begin(), v.end(), back_inserter(result), [](int x) {
    return x * x;  // 平方
});

// 双序列变换
transform(a.begin(), a.end(), b.begin(), back_inserter(result), plus<int>());

copy / copy_if - 复制：

vector<int> dest(v.size());
copy(v.begin(), v.end(), dest.begin());

vector<int> even;
copy_if(v.begin(), v.end(), back_inserter(even), [](int x) {
    return x % 2 == 0;
});

fill - 填充：

1 2	`fill(v.begin(), v.end(), 0); // 全部填充 0 fill_n(v.begin(), 5, 1); // 前 5 个填充 1`

unique / unique_copy - 去重：

// 要求先排序！
sort(v.begin(), v.end());
auto it = unique(v.begin(), v.end());  // 去重，返回新的逻辑结尾
v.erase(it, v.end());                  // 真正删除重复元素

next_permutation / prev_permutation - 排列：

sort(v.begin(), v.end());  // 必须先排序
do {
    // 处理当前排列
} while (next_permutation(v.begin(), v.end()));  // 生成全排列

swap / iter_swap - 交换：

1
2
3

swap(a, b);                          // 交换值
iter_swap(it1, it2);                 // 交换迭代器指向的值
swap_ranges(a.begin(), a.end(), b.begin());  // 交换区间

all_of / any_of / none_of - 条件判断：

1
2
3

bool allPositive = all_of(v.begin(), v.end(), [](int x) { return x > 0; });
bool hasNegative = any_of(v.begin(), v.end(), [](int x) { return x < 0; });
bool noZero = none_of(v.begin(), v.end(), [](int x) { return x == 0; });

算法复杂度速查表

算法	复杂度	说明
`sort`	$O(n \log n)$	快速排序，不稳定
`stable_sort`	$O(n \log n)$	稳定排序
`binary_search`	$O(\log n)$	要求有序
`lower/upper_bound`	$O(\log n)$	要求有序
`find`	$O(n)$	线性查找
`count`	$O(n)$	计数
`accumulate`	$O(n)$	累加
`max/min_element`	$O(n)$	最值
`unique`	$O(n)$	去重（需先排序）
`next_permutation`	$O(n)$	下一个排列
`set_union` 等	$O(n+m)$	集合操作，要求有序

智能指针（C++11）

头文件：<memory>

智能指针自动管理内存，避免内存泄漏。

unique_ptr（独占所有权）

特点：独占所指向的对象，不能复制，只能移动

创建与使用：

#include <memory>

// 创建
unique_ptr<int> p1(new int(42));
auto p2 = make_unique<int>(42);        // C++14，推荐方式

unique_ptr<int[]> arr(new int[10]);   // 数组
auto arr2 = make_unique<int[]>(10);   // C++14

// 访问
*p1 = 100;                             // 解引用
int* raw = p1.get();                   // 获取原始指针

// 释放
p1.reset();                            // 释放内存，置空
p1.reset(new int(20));                 // 释放原内存，指向新内存

int* raw2 = p1.release();              // 释放所有权，返回原始指针（需手动 delete）

// 移动（不能复制）
unique_ptr<int> p3 = std::move(p1);    // p1 变为空，p3 获得所有权

函数参数与返回：

void process(unique_ptr<int> p) { }     // 值传递，转移所有权
void process(const unique_ptr<int>& p) { }  // 引用传递，不转移所有权

unique_ptr<int> create() {
    return make_unique<int>(42);       // 返回 unique_ptr（移动语义）
}

shared_ptr（共享所有权）

特点：多个 shared_ptr 可指向同一对象，引用计数管理生命周期

创建与使用：

// 创建
shared_ptr<int> p1(new int(42));
auto p2 = make_shared<int>(42);        // 推荐，更高效

// 复制（共享所有权）
shared_ptr<int> p3 = p1;               // 引用计数 +1
p3 = p2;                               // p1 计数 -1，p2 计数 +1

// 获取引用计数
cout << p1.use_count();                // 当前引用计数
if (p1.unique()) { /* 只有自己引用 */ }

// 访问
*p1 = 100;
int* raw = p1.get();

// 释放
p1.reset();                            // 引用计数 -1，为 0 时释放

// 检查是否为空
if (p1) { /* 非空 */ }
if (p1 == nullptr) { /* 空 */ }

循环引用问题：

struct Node {
    shared_ptr<Node> next;  // 循环引用！
};

// 解决：使用 weak_ptr
struct Node {
    weak_ptr<Node> next;    // 弱引用，不增加引用计数
};

weak_ptr（弱引用）

特点：不增加引用计数，用于打破 shared_ptr 的循环引用

使用：

shared_ptr<int> sp = make_shared<int>(42);
weak_ptr<int> wp = sp;                 // 从 shared_ptr 创建

if (auto locked = wp.lock()) {        // 尝试提升为 shared_ptr
    // locked 是 shared_ptr，可以安全使用
    cout << *locked;
} else {
    // 原对象已被释放
}

wp.expired();                          // 检查对象是否已被释放

智能指针对比

特性	`unique_ptr`	`shared_ptr`	`weak_ptr`
所有权	独占	共享	无（弱引用）
可复制	❌	✅	✅
可移动	✅	✅	✅
引用计数	无	有	无
用途	唯一所有权场景	共享所有权场景	打破循环引用

面试要点

优先使用 make_unique / make_shared 而非直接 new：
- 效率更高（单次内存分配）
- 异常安全
unique_ptr 开销几乎为零，优先使用
shared_ptr 有引用计数开销，避免滥用
不要用原始指针初始化多个 shared_ptr（会导致双重释放）

常用 string 操作

头文件：<string>

构造与赋值

#include <string>

// 构造
string s1;                         // 空字符串
string s2 = "hello";               // 从 C 字符串
string s3("world");                // 同上
string s4(s2);                     // 拷贝构造
string s5(5, 'a');                 // "aaaaa"
string s6 = s2.substr(0, 3);       // "hel"，子串

// 赋值
s1 = "new value";
s1 = s2;
s1.assign("assigned");
s1.assign(5, 'b');                 // "bbbbb"

访问与遍历

// 下标访问
char c = s[0];                     // 无边界检查
char c2 = s.at(0);                 // 有边界检查
char first = s.front();            // 首字符
char last = s.back();              // 末字符

// 迭代器
for (auto it = s.begin(); it != s.end(); ++it) {
    cout << *it;
}
for (char c : s) {                 // 范围 for
    cout << c;
}

// 获取 C 字符串
const char* cstr = s.c_str();      // 返回 const char*

容量相关

s.size();                          // 字符串长度
s.length();                        // 同 size()
s.empty();                         // 是否为空
s.capacity();                      // 当前容量
s.reserve(100);                    // 预留空间
s.shrink_to_fit();                 // 收缩到合适大小（C++11）

修改操作

// 追加
s += " world";
s.append(" world");
s.append(3, '!');                  // 追加 "!!!"
s.push_back('!');                  // 追加单个字符

// 插入
s.insert(5, " inserted");           // 在位置 5 插入
s.insert(s.begin(), 'A');          // 在开头插入

// 删除
s.erase(5, 3);                       // 从位置 5 删除 3 个字符
s.erase(s.begin());                // 删除首字符
s.erase(s.begin(), s.end() - 3);   // 删除区间
s.clear();                           // 清空

// 替换
s.replace(5, 3, "new");            // 将 [5,8) 替换为 "new"

// 交换
s1.swap(s2);                       // 交换两个字符串

查找操作

// 查找子串或字符
size_t pos = s.find("world");              // 第一次出现的位置，找不到返回 string::npos
size_t pos = s.find("world", 5);           // 从位置 5 开始找
size_t pos = s.rfind("world");             // 最后一次出现
size_t pos = s.find_first_of("aeiou");     // 第一个元音字母
size_t pos = s.find_last_of("aeiou");      // 最后一个元音字母
size_t pos = s.find_first_not_of("abc");   // 第一个不是 a/b/c 的字符
size_t pos = s.find_last_not_of("abc");    // 最后一个不是 a/b/c 的字符

// 判断找到与否
if (pos != string::npos) { /* 找到 */ }

// 示例：查找所有出现位置
size_t pos = 0;
while ((pos = s.find("target", pos)) != string::npos) {
    cout << "找到于: " << pos << endl;
    ++pos;  // 继续往后找
}

比较操作

// 直接比较
if (s1 == s2) { }
if (s1 != s2) { }
if (s1 < s2) { }                   // 字典序比较

// compare 方法
int result = s1.compare(s2);       // 0 表示相等，<0 表示 s1<s2，>0 表示 s1>s2
int result = s1.compare(0, 3, s2);  // 比较 s1[0:3] 与 s2

子串操作

1 2	`string sub = s.substr(5); // 从位置 5 到末尾 string sub = s.substr(5, 3); // 从位置 5 开始，取 3 个字符`

数值转换（C++11）

// string -> 数值
int x = stoi("123");               // string to int
long y = stol("123456");           // string to long
long long z = stoll("123456789");  // string to long long
float f = stof("3.14");            // string to float
double d = stod("3.14159");        // string to double

// 带错误检查
size_t pos;
int x = stoi("123abc", &pos);      // x=123, pos=3（转换结束位置）

// 数值 -> string
string s1 = to_string(123);        // "123"
string s2 = to_string(3.14159);    // "3.141590"

常用面试技巧

// 反转字符串
reverse(s.begin(), s.end());

// 判断回文
bool isPalindrome = equal(s.begin(), s.begin() + s.size()/2, s.rbegin());

// 分割字符串（配合 stringstream）
string line = "a,b,c";
stringstream ss(line);
string item;
while (getline(ss, item, ',')) {
    cout << item << endl;
}

// 去除首尾空格
auto start = s.find_first_not_of(" \t\n\r");
auto end = s.find_last_not_of(" \t\n\r");
string trimmed = s.substr(start, end - start + 1);

string 操作速查表

操作	函数	复杂度
获取长度	`size()` / `length()`	$O(1)$
追加	`append()` / `+=`	$O(n)$
插入	`insert()`	$O(n)$
删除	`erase()`	$O(n)$
查找	`find()`	$O(n \cdot m)$ 最坏
子串	`substr()`	$O(n)$
比较	`compare()`	$O(\min(n,m))$

Programming

#Programming #C++

Cheatsheet: C++

https://cny123222.github.io/2026/03/30/Cheatsheet-C/

Author

Nuoyan Chen

Posted on

March 30, 2026

Licensed under

Cheatsheet: Python Previous

Math Review: Probability Theory Next

Cheatsheet: C++

常见容器

顺序容器

vector

deque

array（C++11）

forward_list（C++11 单向链表）

list（双向链表）

有序关联容器（基于红黑树）

set

multiset / multimap

map

无序关联容器（Hash）

unordered_set / unordered_map

unordered_multiset / unordered_multimap

容器选择速查表（面试重点）

迭代器失效总结（面试必考！）

适配器（Adapters）

stack（栈 - LIFO）

queue（队列 - FIFO）

priority_queue（优先队列 - 堆）

常见输入输出

基础输入输出

读取字符串

多组输入处理

字符串流 stringstream

输出格式控制（iomanip）

文件输入输出

快速输入输出优化

printf / scanf（C 风格）

格式控制速查表

常用算法（STL Algorithm）

排序算法

查找算法

数值算法（<numeric>）

集合算法（要求有序）

其他常用算法

算法复杂度速查表

智能指针（C++11）

unique_ptr（独占所有权）

shared_ptr（共享所有权）

weak_ptr（弱引用）

智能指针对比

面试要点

常用 string 操作

构造与赋值

访问与遍历

容量相关

修改操作

查找操作

比较操作

子串操作

数值转换（C++11）

常用面试技巧

string 操作速查表

数值算法（`<numeric>`）