1. 容器 (Containers)

容器是用来存放数据的集合。它们可以分为三类：序列式容器、关联式容器和无序关联式容器。

A. 序列式容器 (Sequence Containers)

元素按线性顺序排列。

通用API (大部分容器共有):

• 构造函数: Container(), Container(size_type n), Container(n, const value_type& val), Container(InputIt first, InputIt last), Container(const Container& other), Container(std: :initializer_list<T>)
• 大小/容量:
  • empty(): 判断是否为空。
  • size(): 返回元素数量。
  • max_size(): 返回可容纳的最大元素数量。
• 迭代器:
  • begin() / cbegin(): 返回指向第一个元素的迭代器。
  • end() / cend(): 返回指向末尾之后位置的迭代器。
  • rbegin() / crbegin(): 返回指向反向序列第一个元素的迭代器。
  • rend() / crend(): 返回指向反向序列末尾之后位置的迭代器。
• 修改器:
  • clear(): 清空所有元素。
  • insert(): 在指定位置插入元素。
  • erase(): 删除指定位置或范围的元素。
  • swap(): 与另一个同类型容器交换内容。

序列式容器特有API:

• 元素访问:
  • front(): 访问第一个元素。
  • back(): 访问最后一个元素。
  • operator[]: 访问指定索引的元素（不检查越界，仅vector, deque, array, string）。
  • at(): 访问指定索引的元素（检查越界，会抛出std::out_of_range异常）。
• 修改器:
  • push_back(): 在末尾添加元素 (vector, deque, list, string)。
  • pop_back(): 移除末尾元素 (vector, deque, list, string)。
  • push_front(): 在开头添加元素 (deque, list, forward_list)。
  • pop_front(): 移除开头元素 (deque, list, forward_list)。
  • resize(): 改变容器大小。
  • emplace() / emplace_back() / emplace_front(): C++11引入，在指定位置就地构造元素，避免拷贝。

B. 关联式容器 (Associative Containers)

元素根据键值自动排序，底层通常是红黑树。

通用API:

• 查找操作 (效率高，O(log n)):
  • find(const Key& key): 查找键，返回迭代器或end()。
  • count(const Key& key): 返回键匹配的元素数量（set/map中为0或1）。
  • lower_bound(const Key& key): 返回第一个不小于key的元素的迭代器。
  • upper_bound(const Key& key): 返回第一个大于key的元素的迭代器。
  • equal_range(const Key& key): 返回一个pair，包含上述两个bound的结果。
• 修改器:
  • insert(value): 插入元素/键值对。返回pair<iterator, bool>（map/set）或iterator（multimap/multiset）。
  • erase(key) / erase(iterator): 删除元素。
  • emplace(): C++11引入，就地构造元素。
• map特有API:
  • operator[]: 如果键存在，返回其值的引用；如果不存在，则插入一个新元素并返回其值的引用。
  • at(const Key& key): C++11引入，访问键对应的值，若键不存在则抛出异常。

C. 无序关联式容器 (Unordered Associative Containers)

C++11引入，元素无序，基于哈希表实现。

API与关联式容器类似，但查找、插入、删除的平均时间复杂度为O(1)，最坏为O(n)。没有lower_bound/upper_bound等依赖排序的API。

D. 容器适配器 (Container Adapters)

它们不是独立的容器，而是对现有序列式容器（默认是std::deque）的接口进行封装，提供特定的行为模式。

2. 迭代器 (Iterators)

迭代器是泛型指针，提供对容器中元素的访问。根据能力分为五类：

1. 输入迭代器 (Input Iterator): *it (读), it++ (单次向前)。
2. 输出迭代器 (Output Iterator): *it = val (写), it++ (单次向前)。
3. 前向迭代器 (Forward Iterator): *it (读/写), it++ (多次向前)。
4. 双向迭代器 (Bidirectional Iterator): *it (读/写), it++, it-- (双向移动)。
5. 随机访问迭代器 (Random Access Iterator): *it (读/写), it++, it--, it + n, it - n, it[n], it1 - it2。

迭代器相关辅助函数 (C++11+):

• std::begin(container) / std::end(container): 获取容器的 begin/end 迭代器，比成员函数更通用。
• std::next(it, n=1): 返回it向前移动n步后的迭代器。
• std::prev(it, n=1): 返回it向后移动n步后的迭代器。
• std::distance(first, last): 计算两个迭代器之间的距离。
• std::advance(it, n): 将迭代器it移动n步。

3. 算法 (Algorithms)

定义在 <algorithm> 和 <numeric> 头文件中，对迭代器指定的范围进行操作。

A. 非修改性序列操作

• for_each(first, last, f): 对范围内每个元素执行f。
• find(first, last, val): 查找val。
• find_if(first, last, pred): 查找满足pred条件的元素。
• count(first, last, val): 统计val出现的次数。
• count_if(first, last, pred): 统计满足pred条件的元素数量。
• equal(first1, last1, first2): 比较两个序列是否相等。
• search(first1, last1, first2, last2): 在序列1中查找序列2。
• all_of/any_of/none_of(first, last, pred): C++11, 判断是否所有/任意/没有元素满足pred。

B. 修改性序列操作

• copy(first, last, result_first): 复制序列。
• move(first, last, result_first): C++11, 移动序列。
• transform(first, last, result_first, op): 对序列每个元素应用op后存入result。
• replace(first, last, old_val, new_val): 替换所有old_val。
• fill(first, last, val): 用val填充序列。
• generate(first, last, gen): 用生成器gen的结果填充序列。
• remove(first, last, val): “移除”所有val（实际是把不等于val的元素前移，返回新的逻辑终点）。常与container.erase()配合使用。
• unique(first, last): “移除”连续的重复元素，返回新的逻辑终点。
• reverse(first, last): 反转序列。
• rotate(first, middle, last): 旋转序列，使middle成为新的第一个元素。
• random_shuffle/shuffle(first, last, g): 随机打乱序列（shuffle是C++11推荐版本）。

C. 排序和搜索操作

（通常要求随机访问迭代器，部分也适用于双向迭代器）

• sort(first, last, comp): 对序列排序（comp是可选的比较函数）。
• stable_sort(first, last, comp): 稳定排序（保持相等元素的相对顺序）。
• partial_sort(first, middle, last): 将前N个最小元素排序并放在序列开头。
• is_sorted(first, last): 检查序列是否有序。
• 二分查找 (要求序列已排序):
  • binary_search(first, last, val): 判断val是否存在。
  • lower_bound(first, last, val): 查找第一个不小于val的元素。
  • upper_bound(first, last, val): 查找第一个大于val的元素。
  • equal_range(first, last, val): 同时获取lower_bound和upper_bound。

D. 数值操作 (<numeric>)

• accumulate(first, last, init, op): 计算序列的和（或用op进行累积）。
• iota(first, last, val): 用递增的值填充序列 (val, val+1, val+2, …)。
• inner_product(first1, last1, first2, init): 计算内积。

4. 函数对象 (Functors) 与 Lambda 表达式

许多算法接受一个可调用对象（函数指针、函数对象、Lambda）来定制其行为。

• 函数对象 (Functor): 一个重载了operator()的类的对象。
  • 预定义函数对象 (<functional>): std::plus, std::minus, std::less, std::greater, std::logical_not等。
• Lambda 表达式 (C++11+): 现代C++的首选，可以方便地在原地定义匿名函数。
  • 语法: [capture](params) -> return_type { body }
  • 示例: std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; }); // 降序排序
• std::function (<functional>): C++11引入的通用多态函数包装器，可以存储、复制和调用任何可调用目标。

总结

STL的强大之处在于其正交性：

• 容器负责存储数据。
• 算法负责处理数据。
• 迭代器作为两者之间的“胶水”，让任何算法都可以操作任何兼容的容器。

熟练掌握STL，特别是 vector, string, map, unordered_map, set 等常用容器，以及 sort, find, for_each, transform 等核心算法，是成为一名高效C++程序员的关键。C++11及后续标准引入的Lambda表达式、范围for循环、auto关键字等，进一步简化了STL的使用，使其更加强大和易用。