核心要点速览

  • 组件：容器（存储）、算法（操作）、迭代器（桥梁）、仿函数（自定义逻辑）、适配器（接口转换）、分配器（内存管理）
  • 容器分类：序列式（vector/list/deque）、关联式（有序红黑树 / 无序哈希表）、适配器（stack/queue/priority_queue）
  • 关键：底层实现、迭代器失效、容器选型、算法适用条件、内存与效率权衡

一、STL 组件

  1. 容器：类模板，封装数据结构（如 vector/map），存储数据的载体。
  2. 算法：函数模板，提供通用操作（sort/find），通过迭代器操作容器。
  3. 迭代器：类似指针的对象，提供元素访问接口，是容器与算法的桥梁。
  4. 仿函数：重载operator()的类 / 结构体（函数对象），传递自定义逻辑（比较 / 筛选）。
  5. 适配器：转换已有组件接口（含容器适配器、迭代器适配器如 reverse_iterator、函数适配器如 bind），如 stack 基于 deque 适配。
  6. 分配器：默认std::allocator，核心接口含allocate（分配）/deallocate（释放）/construct（构造）/destroy（析构）；自定义分配器可优化内存碎片（极少使用）。

二、容器：分类、特性与选型

1. 序列式容器（元素有序，依赖位置）

容器 底层实现 特性 适用场景
vector 连续动态数组 随机访问 O (1)，尾部增删 O (1)；扩容 1.5/2 倍（GCC/MSVC），中间增删 O (n)；支持reserve()/resize()；emplace_back()比push_back()高效（直接构造，避免拷贝） 频繁随机访问、尾部增删（列表 / 缓存）
list 双向链表 任意位置增删 O (1)（需定位），随机访问 O (n)；支持merge()/splice()（多重载，转移元素无需拷贝，O (1) 效率）；双向迭代器 频繁中间增删（链表 / 非 FIFO 队列）
deque 分段连续数组（缓冲区 + 中控器） 头尾增删 O (1)，随机访问 O (1)（略低于 vector）；扩容无需拷贝全部元素；无capacity()成员（分段存储无连续容量概念）；中间插入迭代器全失效；排序缓存命中率低，建议转 vector 排序 双端操作（BFS 队列）

2. 关联式容器（元素无序，依赖键值）

有序关联容器（红黑树，O (logn) 操作）

  • 包含：set（唯一键）、multiset（键可重复）、map（键值对，键唯一）、multimap（键可重复）
  • 特性：按键升序排列（默认less<Key>），支持lower_bound()/upper_bound()/equal_range()；键为 const（不可修改），但可通过迭代器修改 map 的 value；count()返回键出现次数；双向迭代器

无序关联容器（哈希表，平均 O (1) 操作）

  • 包含：unordered_set/multiset、unordered_map/multimap
  • 特性：元素无序，前向迭代器；负载因子默认 1.0，超阈值触发rehash（迭代器全失效）；哈希冲突默认用链表法解决（C++17 后部分实现用红黑树优化长链表）；自定义键需特化std::hash+operator==

map vs unordered_map 对比

维度 map（红黑树） unordered_map（哈希表）
查找效率 O (logn)（稳定） 平均 O (1)，最坏 O (n)（冲突严重）
有序性 支持（升序） 不支持
内存占用 较低 较高（冲突解决需额外空间）
迭代器 双向 前向
键值操作 []会默认构造不存在的键；可通过replace()修改 value []行为同 map，需避免误触发默认构造

3. 容器适配器（接口转换）

  • stack（LIFO）：默认底层 deque，可指定 vector 为底层（stack<int, vector<int>>），接口push()/pop()/top()；支持emplace()直接构造元素
  • queue（FIFO）：默认底层 deque，接口push()/pop()/front()/back()
  • priority_queue（最大堆）：底层仅支持 vector/deque（需随机访问迭代器），不可用 list；最小堆需指定std::greater<int>；无迭代器遍历功能

三、迭代器：类型与失效

1. 迭代器类型（按功能划分）

类型 支持操作 对应容器示例
输入迭代器 *（读）、==/!= istream_iterator
输出迭代器 *（写） ostream_iterator
前向迭代器 输入 + 输出，多遍访问 unordered_set/unordered_map
双向迭代器 前向功能 +-- list、map、set
随机访问迭代器 双向功能 ++n/-n/[] vector、deque、数组

2. 失效场景

容器 插入操作 删除操作 其他失效场景
vector 扩容则全失效，未扩容则插入位后失效 删除位后失效（需iter=erase(iter)） reserve()可能导致失效；shrink_to_fit()不必然失效
list 不失效 仅被删元素迭代器失效 -
map/set 不失效 仅被删节点迭代器失效 -
unordered_* 未 rehash 则有效，rehash 全失效 仅被删元素迭代器失效 reserve()/rehash()全失效
容器 swap 无 无 vector 可能因内存交换失效；其他容器迭代器仍有效（指向原元素）

3. 迭代器特性

  • 算法通过std::iterator_traits<Iter>获取value_type（元素类型）、difference_type（迭代器差值）等，自定义迭代器需显式定义这些类型。
  • 反向迭代器（reverse_iterator）：rbegin()指向尾元素，rend()指向首元素前；base()方法转换为原迭代器时，位置偏移一位（如rbegin().base() == end()）。
  • 插入迭代器（back_insert_iterator 等）：通过back_inserter(v)生成，配合算法自动调用push_back()，避免手动管理迭代器位置。

四、算法与仿函数

1. 常用算法

算法 功能 适用条件 注意点
sort 排序 随机访问迭代器（vector/deque） list 需用成员函数list::sort()；底层为 introsort（快排 + 堆排 + 插入排序）
binary_search 二分查找 有序序列 + 随机访问 / 双向迭代器 仅返回是否存在；需获取元素迭代器用lower_bound()
find 线性查找 所有迭代器 O (n) 效率；map/set 优先用成员函数find()（O(logn)）
for_each 遍历执行操作 所有迭代器 可传递函数 / 仿函数 /lambda；返回函数对象（可携带遍历后的状态）
remove 逻辑删除 所有迭代器 需配合erase()物理删除；不改变容器 size
unique 去重 有序序列 + 所有迭代器 需先排序，配合erase()生效；支持自定义谓词（如[](int a,int b){return abs(a-b)<=2;}）；list 有专属unique()，直接物理删除
stable_sort 稳定排序（保原始顺序） 随机访问迭代器 多字段排序场景适用；空间复杂度 O (n)，高于 sort 的 O (logn)

2. 仿函数与 lambda

  • 仿函数：可复用、带状态；标准库提供std::plus<T>（加法）、std::greater<T>（大于）等基础仿函数。
  • 谓词要求：自定义比较谓词需满足严格弱序（非自反：comp(x,x)=false；反对称：comp(x,y)=true则comp(y,x)=false；传递性），违反会导致未定义行为（容器插入异常、算法崩溃）。
  • 函数适配器：std::bind（绑定函数参数），与 C++11+ lambda 为互补关系（日常优先 lambda ，绑定类成员函数、兼容旧代码等场景std::bind更适配）。
  • 优先级：容器成员函数 > 全局算法（如map.find()比std::find()高效）。

五、容器选型决策树

  1. 需随机访问 → vector（优先）/deque（需头操作）
  2. 需频繁中间增删 → list
  3. 需按键查找 → 有序（map/set，范围查询 / 有序遍历）/ 无序（unordered_*，纯查找高效）
  4. 需 LIFO/FIFO/ 优先级 → stack/queue/priority_queue