迭代器
C++ STL（Standard Template Library，标准模板库）中迭代器与常用算法是泛型编程的核心组成部分。它们配合使用，可以对容器进行高效、统一的操作。下面是对它们的系统性总结。
一、什么是迭代器（Iterator）
迭代器是 STL 的核心，用于访问容器中的元素。迭代器本质上就是一种“广义的指针”，它提供了统一的方式来访问容器中的元素。
功能包括：
- 访问元素：通过
*it读取元素 - 遍历元素：使用
++it、--it、it + n等 - 修改元素（对于非 const 迭代器）
二、迭代器的分类（五种类型）
STL 中的迭代器按功能分为五种类型，定义在 <iterator> 中：
- 输入迭代器（Input Iterator）：只能进行单次读取操作，不能进行写入操作。
- 输出迭代器（Output Iterator）：只能进行单次写入操作，不能进行读取操作。
- 正向迭代器（Forward Iterator）：可以进行读取和写入操作，并且可以向前移动。
- 双向迭代器（Bidirectional Iterator）：除了可以进行正向迭代器的所有操作外，还可以向后移动。
- 随机访问迭代器（Random Access Iterator）：除了可以进行双向迭代器的所有操作外，还可以进行随机访问，例如通过下标访问元素。
📌 记忆技巧：每类迭代器是对上一级的扩展。
三、迭代器基本操作
以 vector<int> 为例：
#include <iostream> #include <vector> #include <iterator> int main() { // 创建一个 vector 容器并初始化 std::vector<int> vec = {1, 2, 3, 4, 5}; // 使用迭代器遍历 vector for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) { std::cout << *it << " "; } std::cout << std::endl; // 使用 auto 关键字简化迭代器类型 for (auto it = vec.begin(); it != vec.end(); ++it) { std::cout << *it << " "; } std::cout << std::endl; // 使用 C++11 范围 for 循环 for (int elem : vec) { std::cout << elem << " "; } std::cout << std::endl; return 0; } 四、const_iterator 与 reverse_iterator
const_iterator 和 reverse_iterator 是C++标准库中提供的两种迭代器类型，它们用于遍历容器（如vector、list、map等）中的元素，但各自有不同的用途和行为。
const_iterator
const_iterator 是一种不能用来修改其所指向元素值的迭代器。
-
声明方式：通常，容器类提供了一个名为
cbegin()和cend()的成员函数来返回一个const_iterator，即使在非const对象上调用这些方法也是如此。std::vector<int> vec = {1, 2, 3, 4}; for (std::vector<int>::const_iterator it = vec.cbegin(); it != vec.cend(); ++it) { // *it = 10; // 错误，无法通过 const_iterator 修改值 std::cout << *it << " "; }
reverse_iterator
reverse_iterator 则是一种允许从容器末尾向头部进行遍历的迭代器。
-
声明方式：容器类提供了名为
rbegin()和rend()的成员函数来获取reverse_iterator，分别指向容器的最后一个元素和第一个元素之前的位置。std::vector<int> vec = {1, 2, 3, 4}; for (std::vector<int>::reverse_iterator rit = vec.rbegin(); rit != vec.rend(); ++rit) { std::cout << *rit << " "; // 输出将是 4 3 2 1 } for (std::vector<int>::const_reverse_iterator rit = vec.rbegin(); rit != vec.rend(); ++rit) { std::cout << *rit << " "; // 输出将是 4 3 2 1 }
总结
- 使用
const_iterator来确保你只能读取而不能修改容器中的数据。 - 使用
reverse_iterator当你需要以逆序的方式遍历容器的内容时。
此外，还有 const_reverse_iterator 类型，它是 reverse_iterator 的常量版本，既不允许修改容器中的元素也不允许通过它改变容器的大小。这种类型的迭代器可以通过容器的 crbegin() 和 crend() 成员函数获得。
五、与 STL 算法结合使用
所有 <algorithm> 算法都基于迭代器设计：
#include <algorithm> std::vector<int> v = {5, 2, 8, 1}; std::sort(v.begin(), v.end()); // 从小到大排序 auto it = std::find(v.begin(), v.end(), 2); // 查找值为2的元素 std::reverse(v.begin(), v.end()); // 反转 六、迭代器失效（Invalidation）
迭代器失效（Iterator Invalidation）是 C++ 编程中一个非常重要但常被忽视的概念。如果对它不了解，程序可能编译通过但运行崩溃或行为异常，是调试中非常棘手的一类错误。STL 迭代器是对地址的封装，地址变了，迭代器就失效了！！！！！！！
什么是迭代器失效
迭代器失效指的是：当你对容器做某些操作（如插入、删除、重排）之后，已有的迭代器、引用或指针变得不再有效，再使用它们就会导致未定义行为（UB）。
迭代器本质上就是一个“封装了访问容器中某个元素信息”的对象，可能是一个裸指针、也可能是一个封装指针和状态的类。
如果元素被销毁了（如
erase()） 那么迭代器就指向一块无效内存；
如果元素被搬移了（如vector::insert()）那么迭代器里的地址就过时了；
如果结构被重构（如unordered_map的 rehash） 那么迭代器指向的桶或节点被换掉了；换句话说：
失效的迭代器 = 仍然保存着原始访问信息，但这个信息已经不再与容器同步
哪些容器容易失效
| 容器 | 增删元素是否可能导致迭代器失效 |
|---|---|
vector, deque, string |
插入、删除、realloc 后迭代器会失效 |
list, forward_list |
插入不会失效，删除对应元素会导致该元素的迭代器失效 |
set, map, unordered_set, unordered_map |
插入不会使已有迭代器失效，但删除某个元素会使该元素迭代器失效 |
各容器常见操作的迭代器失效表
| 容器 | insert |
erase |
push_back / push_front |
clear |
|---|---|---|---|---|
vector |
可能失效 reallocation 导致地址变更 | 删除点之后失效 | 可能失效 reallocation 导致地址变更 | 所有失效 |
list |
不失效 | 仅删除点失效 | 不失效 | 所有失效 |
deque |
可能失效 | 删除点之后失效 | 可能失效 | 所有失效 |
set / map |
不失效 | 删除点失效 | 不适用 | 所有失效 |
unordered_set / unordered_map |
插入可能失效（rehash） | 删除点失效 | 插入可能失效 | 所有失效 |
常见迭代器失效场景详解
1. vector 或 string 的插入/删除/扩容
- 扩容插入：
vector会在容量不足时发生realloc扩容（重新分配内存），地址变更，所有旧的迭代器/指针/引用会失效。 vector::erase会使被删除位置及其后的所有迭代器失效。因为vector的底层实现是连续内存数组，删除一个元素后：- 所有后续元素都会向前搬移一个位置
- 所以这些元素的原始地址全部变化
- 而 STL 迭代器是对地址的封装，地址变了，迭代器就失效了
错误示例 ：
std::vector<int> v = {1, 2, 3}; auto it = v.begin(); v.push_back(4); // 如果触发了扩容，it 失效 std::cout << *it; // 未定义行为！ std::vector<int> v = {1,2,3,4}; for (auto it = v.begin(); it != v.end(); ++it) { if (*it == 2) v.erase(it); // ❌ 之后的 ++it 已失效 } ✅ 安全做法：每次操作后重置迭代器
正确用法：
std::vector<int> v = {1,2,3,4,5}; for (auto it = v.begin(); it != v.end(); ) { if (*it % 2 == 0) it = v.erase(it); // 安全写法：用返回值更新 it else ++it; } 2. list 的插入是安全的，但删除某元素后该迭代器失效
std::list<int> l = {1, 2, 3}; auto it = l.begin(); l.erase(it); // it 失效 // std::cout << *it; // ❌ UB 为什么 std::list 的插入是“安全”的？
std::list 是一个 双向链表，其元素在内存中不连续，每个元素是一个节点，节点通过指针链接：插入时，只是修改节点的 next / prev 指针，不需要移动已有节点或重新分配内存。
- 已有迭代器仍然指向原节点
- 插入不会破坏旧节点，也不会导致地址变化
为什么删除某个元素后该迭代器会失效？
当你调用 l.erase(it) 删除某个节点时：
- 该节点的内存被释放
- 该迭代器内部的指针指向的内存被销毁了
std::list<int> l = {1, 2, 3}; auto it = std::next(l.begin()); // 指向 2 l.erase(it); // 删除 2 std::cout << *it << "n"; // ❌ it 已失效，UB 在开启调试的编译器中（如 -D_GLIBCXX_DEBUG），这句会抛出异常。
4. set / map 的删除会使该元素的迭代器失效，unordered_* 容器的插入或 rehash 可能使所有迭代器失效
| 操作 | std::set / std::map |
std::unordered_set / unordered_map |
|---|---|---|
| 插入是否导致迭代器失效？ | ❌ 不会失效 ✅ | ✅ 可能全部失效（rehash） |
| 删除是否导致迭代器失效？ | ✅ 被删的失效 | ✅ 被删的失效 |
原因：容器底层结构不同：
std::set / std::map 底层结构：红黑树（红黑平衡二叉搜索树）：
- 插入/删除操作都只是局部旋转或链调整
- 节点地址不变，不搬家、不分桶
- 所以：除被删节点外，其他节点位置稳定，迭代器不失效
std::set<int> s = {1,2,3}; auto it = s.begin(); // 指向1 s.insert(4); // 树中添加新节点 std::cout << *it; // ✅ 安全，仍输出1 std::unordered_set / unordered_map 底层结构：哈希表（带链式或桶数组）：
- 插入会导致 rehash（哈希桶重分配）
- 所有元素会搬到新桶中，地址变化
- 所以：所有迭代器都失效
- 如果你提前调用
.reserve(容量)，就可以避免 rehash，从而保证插入不失效。
这个问题触及了 哈希表结构的本质，我们来深入解释：
unordered_maprehash 会重新分配哈希桶并搬移元素位置，所以所有迭代器（包括指向元素的）都失效。哈希表（hash table） 典型结构如下：
哈希桶数组（bucket array）： +--------+--------+--------+--------+--------+ | bucket0| bucket1| bucket2| bucket3| bucket4| +--------+--------+--------+--------+--------+ | | | | | ↓ ↓ ↓ ↓ ↓ nodeA nodeB NULL nodeC nodeD每个桶是一个链表（或链式结构），用于存放哈希值落在该桶的元素。
当插入太多元素，负载因子 α = 元素数 / 桶数超过一定阈值时：
STL 会 自动扩容桶数组（rehash），比如将桶数翻倍，从 8 → 16 → 32...
rehash 会：
- 分配 新的桶数组（新的内存空间）
- 遍历旧元素，重新计算哈希值 % 新桶数，将它们重新分配到新桶中
- 每个元素的位置、所属桶、链表结构都全部变了
std::unordered_set<int> us = {1,2,3}; auto it = us.begin(); us.insert(1000); // 插入过多元素触发 rehash std::cout << *it; // ❌ UB，地址可能已变化 为什么删除操作一定会导致该元素迭代器失效？
不管是红黑树（有序容器）还是哈希表（无序容器），erase(it) 都会销毁该节点 → 这个地址失效，it 失效：
std::set<int> s = {1, 2, 3}; auto it = s.find(2); s.erase(it); std::cout << *it; // ❌ it 失效（指向被释放的节点） 补充：插入时，为什么 set/map 可以保证其他迭代器稳定？
因为 新节点永远是“新分配的”，不会干扰旧节点位置，而迭代器只要指向旧节点，就不会失效。
如何避免迭代器失效问题？
- 每次插入/删除/变更结构后不要继续使用原迭代器
- 特别是
vector的push_back、insert、erase等操作
- 若算法中要边遍历边修改结构，请用：
it = container.erase(it); // 使用返回值 - 若需要保持迭代器稳定，可考虑用：
std::list（插入安全）std::map/std::set（插入安全）
七、迭代器适配器（Iterator Adapter）
C++ STL 提供了三种非常实用的迭代器适配器（iterator adapters），用于将 STL 算法的输出“适配”到容器的不同插入方式。
迭代器适配器总览
| 名称 | 插入方式 | 适用容器 | 原理 |
|---|---|---|---|
std::back_inserter |
调用 push_back |
vector, deque, list |
末尾插入 |
std::front_inserter |
调用 push_front |
deque, list |
头部插入 |
std::inserter |
调用 insert(pos, val) |
set, map, list, vector |
在指定位置插入或根据规则 |
它们都定义在头文件：
#include <iterator> 1. std::back_inserter
std::back_inserter(container) 适用于支持 push_back() 的容器，如 vector, deque, list。
示例：
std::vector<int> src = {1, 2, 3}; std::vector<int> dst; std::copy(src.begin(), src.end(), std::back_inserter(dst)); // dst = {1, 2, 3} 2. std::front_inserter
std::front_inserter(container) 适用于支持 push_front() 的容器，如 list, deque（⚠️ vector 不支持）。
示例：
std::vector<int> src = {1, 2, 3}; std::vector<int> dst; std::copy(src.begin(), src.end(), std::front_inserter(dst)); // dst = {3, 2, 1}，相当于反序插入 3. std::inserter
std::inserter(container, pos) 适用于支持 insert(pos, val) 或 insert(val) 的容器，比如：
- 顺序容器：
list,vector,deque - 关联容器：
set,map,unordered_set,unordered_map
它的工作方式是：每次调用 *it = val，会变成 container.insert(pos, val) 或 container.insert(val)，根据容器类型自动处理。
示例（vector）：
std::vector<int> v = {1, 4, 5}; std::vector<int> to_insert = {2, 3}; std::copy(to_insert.begin(), to_insert.end(), std::inserter(v, v.begin() + 1)); // v = {1, 2, 3, 4, 5} 示例（set）：
std::set<int> s; std::vector<int> v = {3, 1, 4}; std::copy(v.begin(), v.end(), std::inserter(s, s.begin())); // s = {1, 3, 4}（自动去重 + 排序） 示例对比
#include <vector> #include <list> #include <set> #include <iterator> #include <algorithm> #include <iostream> int main() { std::vector<int> src = {1, 2, 3}; // back_inserter std::vector<int> v; std::copy(src.begin(), src.end(), std::back_inserter(v)); // v = 1 2 3 // front_inserter std::list<int> l; std::copy(src.begin(), src.end(), std::front_inserter(l)); // l = 3 2 1 // inserter (middle insert into vector) std::vector<int> a = {0, 4}; std::copy(src.begin(), src.end(), std::inserter(a, a.begin() + 1)); // a = 0 1 2 3 4 // inserter (into set) std::set<int> s; std::copy(src.begin(), src.end(), std::inserter(s, s.begin())); // s = 1 2 3 } 八、迭代器的现代替代品
C++11 范围 for 循环（range-based for loop）
在 C++11 中，引入了“范围 for 循环（range-based for loop）”语法，它是对传统迭代器遍历的一种简化封装。它本质上仍然依赖于迭代器接口，只是把编写迭代器的模板代码藏在了语法糖后面。
1、语法示例
| 写法 | 说明 |
|---|---|
for (int x : v) |
拷贝元素（无法修改原始容器） |
for (int& x : v) |
引用访问元素（可修改） |
for (const int& x : v) |
常量引用（节省拷贝成本，无法修改） |
#include <iostream> #include <vector> int main() { std::vector<int> vec = {1, 2, 3, 4}; // 使用范围 for 循环 for (int x : vec) { std::cout << x << " "; } std::cout<< std::endl; // 等价于 for (auto it = vec.begin(); it != vec.end(); ++it) { int x = *it; std::cout << x << " "; } } #include <iostream> #include <vector> int main() { std::vector<int> vec1 = {1, 2, 3, 4}; std::vector<int> vec2 = {1, 2, 3, 4}; // 如果使用引用或引用修改 for (int& x : vec1) { x *= 2; // 修改元素值 } for (int x : vec1) { std::cout << x << " "; } std::cout<< std::endl; // 等价于 for (auto it = vec2.begin(); it != vec2.end(); ++it) { *it *= 2; } for (int x : vec2) { std::cout << x << " "; } } 2、工作原理：使用 begin() 和 end()
编译器在处理 for (auto x : container) 时会：
{ auto __begin = std::begin(container); auto __end = std::end(container); for (; __begin != __end; ++__begin) { auto x = *__begin; // 循环体 } } 即：
- 使用容器的
begin()和end()函数获取迭代器范围 - 使用迭代器
*访问元素，++进行遍历
支持 range-based for 的关键：容器必须有 begin() 和 end() 方法（成员或非成员）返回迭代器。
C++20 Ranges
C++20 引入 ranges，简化迭代器和算法结合的写法：
C++20 引入的 Ranges 是对传统 STL 算法与迭代器体系的重大升级，它让容器操作更加直观、可组合、函数式、懒惰（lazy），是 C++ 泛型编程的一大进步。
1、什么是 Ranges？
更 简洁，更 可读 ，懒惰求值（只有遍历时才计算），更 易组合
对一个vector取奇数，乘2，前3个的操作：
#include <algorithm> #include <iostream> #include <ranges> #include <vector> int main() { std::vector<int> v = {1, 2, 3, 4, 5}; // 取奇数，排序，只保留前两个元素 // 第一步：filter - 筛选奇数 std::vector<int> filtered; std::copy_if(v.begin(), v.end(), std::back_inserter(filtered), [](int x) { return x % 2 == 1; }); // 第二步：transform - 乘2 std::vector<int> transformed; std::transform(filtered.begin(), filtered.end(), std::back_inserter(transformed), [](int x) { return x * 10; }); // 第三步：take 3 - 取前3个 std::vector<int> result; std::copy_n(transformed.begin(), std::min<size_t>(3, transformed.size()), std::back_inserter(result)); // 输出结果 for (int x : result) { std::cout << x << " "; } // c++20 管道式组合：取奇数，乘2，前3个 auto view = v | std::views::filter([](int x){ return x % 2 == 1; }) | std::views::transform([](int x){ return x * 10; }) | std::views::take(3); for (int x : view) { std::cout << x << " "; } } 2、核心组成
Ranges 头文件
#include <ranges> // 所有 ranges 组件 Views（视图） - 核心特性
| 名称 | 说明 | 示例 |
|---|---|---|
views::filter |
过滤元素 | x % 2 == 0 |
views::transform |
元素变换 | x * 2 |
views::take(n) |
取前 n 个元素 | take(5) |
views::drop(n) |
跳过前 n 个元素 | drop(3) |
views::reverse |
反转视图 | |
views::iota(start, end) |
生成数列 | iota(1, 10) |
views::enumerate |
带索引 | C++23 引入 |
3、Range 与容器的区别
| 项目 | 容器（如 vector） | Ranges View |
|---|---|---|
| 是否持有数据 | 是（拥有所有权） | 否（引用或包装） |
| 是否懒惰求值 | 否（立即计算） | 是（按需计算） |
| 是否可组合 | 需要临时变量 | 可以链式组合 |
| 开销 | 复制内存 | 几乎为零开销（按需生成） |
4、与算法结合（ranges::）
C++20 引入 std::ranges:: 下的算法，替代传统 <algorithm> 版本，支持range 作为输入。
#include <ranges> #include <algorithm> std::vector<int> v = {3, 1, 4, 1, 5}; // 更简洁的写法： std::ranges::sort(v); // 不需要手动传 begin/end - 许多算法接受 range 或 iterator：
ranges::find(range, value)ranges::count(range, pred)ranges::for_each(range, fn)ranges::all_of(range, pred)
STL 常用算法
C++ STL（标准模板库）提供了大量泛型算法，位于头文件 <algorithm> 和 <numeric> 中。它们基于迭代器设计，支持几乎所有 STL 容器（如 vector, list, set, map 等）。
以下是对 STL 常用算法分类及用法的系统总结，并附上示例。
一、头文件说明
#include <algorithm> // 绝大多数 STL 算法 #include <numeric> // accumulate, inner_product 等 二、STL 算法分类总览
| 类别 | 常用算法 | 功能描述 |
|---|---|---|
| 遍历类 | for_each, transform |
对每个元素执行操作 |
| 查找类 | find, find_if, count, binary_search |
查找元素 |
| 修改类 | copy, replace, fill, remove |
修改或生成新数据 |
| 排序类 | sort, stable_sort, reverse, partial_sort |
排序与重排 |
| 比较类 | equal, mismatch, lexicographical_compare |
比较区间内容 |
| 数值类 | accumulate, inner_product, iota |
数值计算 |
| 集合类 | set_union, set_intersection, set_difference |
需要排序 |
| 分区类 | partition, stable_partition, is_partitioned |
分组元素 |
| 辅助类 | min, max, swap, iter_swap |
辅助操作 |
三、常用算法详解与示例
1. 遍历类
std::for_each 和 std::transform 是 C++ STL 中两个非常常用的算法函数，它们都用于遍历容器元素并对其应用某种操作，但用途略有不同。
std::for_each
对指定范围内的每个元素执行某个操作，不返回新容器。原型：
template<class InputIterator, class Function> Function for_each(InputIterator first, InputIterator last, Function f); - 对容器中元素应用
f(x) - 常用于打印、累加等副作用操作
- 不会改变容器内容（除非
f修改引用）
📦 示例：
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> v = {1, 2, 3, 4}; std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; }); std::cout << std::endl; // 💡 如果你用引用参数，可以修改容器元素： std::for_each(v.begin(), v.end(), [](int &x) { x *= 2; }); std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; }); } //输出 1 2 3 4 2 4 6 8 Process finished with exit code 0 std::transform
对一个（或两个）区间中的元素应用函数，并将结果写入另一个区间，返回的是结果迭代器。
原型（单输入）：
template<class InputIterator, class OutputIterator, class UnaryOperation> OutputIterator transform(InputIterator first1, InputIterator last1, OutputIterator result, UnaryOperation op); 特点：
- 输入一个或两个区间，输出一个新结果区间
- 不修改原始容器
- 常用于“映射”（map）操作
示例（单输入）：
std::vector<int> v = {1, 2, 3}; std::vector<int> result; std::transform(v.begin(), v.end(), std::back_inserter(result), [](int x){ return x * 2; }); // result = {2, 4, 6} 示例（双输入）：
std::vector<int> a = {1, 2, 3}; std::vector<int> b = {4, 5, 6}; std::vector<int> result; std::transform(a.begin(), a.end(), b.begin(), std::back_inserter(result), [](int x, int y){ return x + y; }); // result = {5, 7, 9} 总结对比
| 项目 | std::for_each |
std::transform |
|---|---|---|
| 是否有输出容器 | 否 | 是，结果写入新容器 |
| 用途 | 遍历打印/修改/统计 | 映射生成新数据 |
| 是否能修改原容器 | 是（通过引用） | 否（默认写入新容器） |
| 是否懒惰求值 | 否 | 否 |
| 等价于 | Python 的 for x in |
Python 的 map() |
选择建议：
- 需要对元素进行处理或收集 → 使用
std::transform - 只想对每个元素做操作（如打印、修改） → 使用
std::for_each
2. 查找类
当然，下面是对 C++ STL 中 查找类算法 的系统整理和详细讲解，包括功能、使用方式、适用场景和示例代码。你将了解如何用标准库高效地在各种容器中查找、定位和判断元素。
查找类算法总览
| 算法名 | 功能 | 特点 |
|---|---|---|
std::find |
查找等于某值的元素 | 线性查找 |
std::find_if / find_if_not |
查找满足（或不满足）某条件的元素 | 可自定义谓词 |
std::count / count_if |
统计等于某值（或满足条件）的元素个数 | 线性统计 |
std::any_of / all_of / none_of |
判断是否存在、全部、全部不满足某条件 | 快速判断 |
std::search / search_n |
查找子序列或重复值 | 区间查找 |
std::adjacent_find |
查找相邻重复元素 | 连续判断 |
std::binary_search |
二分查找 | 有序区间 |
std::lower_bound / upper_bound |
查找第一个不小于 / 大于指定值的位置 | 有序区间 |
std::equal_range |
同时返回 lower_bound 和 upper_bound |
范围查找 |
1. std::find
在线性序列中查找“等于某值”的第一个元素。
template<class InputIt, class T> InputIt find(InputIt first, InputIt last, const T& value); 示例：
std::vector<int> v = {1, 2, 3, 4}; auto it = std::find(v.begin(), v.end(), 3); if (it != v.end()) std::cout << "Found: " << *it; 2. std::find_if / find_if_not
查找满足（或不满足）谓词条件的第一个元素。
template<class InputIt, class UnaryPredicate> InputIt find_if(InputIt first, InputIt last, UnaryPredicate p); 示例：
auto it = std::find_if(v.begin(), v.end(), [](int x){ return x % 2 == 0; }); // 第一个偶数 3. std::count / count_if
统计等于某值，或满足某条件的元素个数。
示例：
int n1 = std::count(v.begin(), v.end(), 5); // 有几个 5 int n2 = std::count_if(v.begin(), v.end(), [](int x){ return x > 3; }); // 有几个大于3 4. std::any_of / all_of / none_of
| 函数 | 功能 |
|---|---|
any_of |
有任意一个满足 |
all_of |
所有都满足 |
none_of |
全部都不满足 |
示例：
bool any_even = std::any_of(v.begin(), v.end(), [](int x){ return x % 2 == 0; }); bool all_positive = std::all_of(v.begin(), v.end(), [](int x){ return x > 0; }); bool none_negative = std::none_of(v.begin(), v.end(), [](int x){ return x < 0; }); 5. std::adjacent_find
查找相邻的两个相等元素或满足某自定义条件的一对相邻元素。
示例：
std::vector<int> v = {1, 2, 2, 3, 4}; auto it = std::adjacent_find(v.begin(), v.end()); // 找到第一个 2,2 6. std::search / search_n
在序列中查找某个子序列 或 连续 n 个值 出现的位置。
示例：
std::search – 查找子序列
std::vector<int> v = {1,2,3,4,5}; std::vector<int> pattern = {3,4}; auto it = std::search(v.begin(), v.end(), pattern.begin(), pattern.end()); std::search_n – 查找 n 连续值
auto it = std::search_n(v.begin(), v.end(), 3, 7); // 连续3个7 7. 二分查找类（⚠ 需要已排序）
常用于：vector, array, 或 set 中，元素按升序排列
std::binary_search（只返回是否存在）
std::sort(v.begin(), v.end()); // 必须排序 bool found = std::binary_search(v.begin(), v.end(), 5); std::lower_bound / upper_bound
| 函数 | 返回 |
|---|---|
lower_bound |
第一个 ≥ val 的位置 |
upper_bound |
第一个 > val 的位置 |
auto lb = std::lower_bound(v.begin(), v.end(), 5); auto ub = std::upper_bound(v.begin(), v.end(), 5); std::equal_range
auto [low, up] = std::equal_range(v.begin(), v.end(), 5); // 一次查两个 示例：计数有几个等于 5 的元素（已排序容器）
int count = std::upper_bound(v.begin(), v.end(), 5) - std::lower_bound(v.begin(), v.end(), 5); 查找类算法使用建议
| 场景 | 推荐算法 |
|---|---|
| 精确查找 | std::find |
| 条件查找 | std::find_if |
| 计数值出现次数 | std::count |
| 判断是否有某种元素 | std::any_of |
| 相邻重复查找 | std::adjacent_find |
| 查找子序列 | std::search |
| 二分查找（有序） | std::binary_search, lower_bound |
性能
| 算法 | 时间复杂度 | 要求 |
|---|---|---|
find, count 等线性查找 |
O(n) | 无需排序 |
binary_search, lower_bound |
O(log n) | 必须排序，支持随机访问迭代器 |
3. 修改类
修改类算法总览
| 类别 | 算法名 | 功能 |
|---|---|---|
| 拷贝类 | std::copy, copy_n, copy_if, move |
拷贝元素或移动元素 |
| 替换类 | std::replace, replace_if, replace_copy |
替换满足条件的元素 |
| 填充类 | std::fill, fill_n, generate, generate_n, iota |
填充或生成元素 |
| 删除类 | std::remove, remove_if, unique |
移除或压缩元素（惰性） |
| 交换类 | std::swap, iter_swap, swap_ranges |
交换元素或范围 |
| 反转类 | std::reverse, reverse_copy, rotate, shuffle |
调整元素顺序 |
1. 拷贝类
std::copy – 复制整个区间
std::copy(src.begin(), src.end(), dest.begin()); - 注意
dest必须有足够空间，或用back_inserter增长容器。
std::copy_if – 条件复制
std::copy_if(v.begin(), v.end(), std::back_inserter(result), [](int x){ return x % 2 == 0; }); std::copy_n – 复制固定数量元素
std::copy_n(src.begin(), 5, std::back_inserter(result)); 2. 替换类
std::replace – 替换值
std::replace(v.begin(), v.end(), 3, 99); // 把 3 替换成 99 std::replace_if – 满足条件的元素被替换
std::replace_if(v.begin(), v.end(), [](int x){ return x < 0; }, 0); std::replace_copy – 替换并写入另一个容器
std::replace_copy(v.begin(), v.end(), std::back_inserter(result), 3, 100); 3. 填充类
std::fill – 将区间填充为某个值
std::fill(v.begin(), v.end(), 0); std::fill_n – 从起点填充 n 个值
std::fill_n(v.begin(), 5, 1); std::generate – 用函数填充区间
int n = 0; std::generate(v.begin(), v.end(), [&](){ return ++n; }); // v = {1,2,3,...} std::generate_n
std::generate_n(std::back_inserter(v), 5, [](){ return rand(); }); std::iota（在 <numeric> 中）– 递增填充
std::iota(v.begin(), v.end(), 1); // v = {1, 2, 3, ...} 4. 删除类（惰性删除，需要配合 erase）
std::remove – 移除某个值（不改变容器大小）
auto it = std::remove(v.begin(), v.end(), 3); v.erase(it, v.end()); // 物理删除 std::remove_if – 按条件移除元素
auto it = std::remove_if(v.begin(), v.end(), [](int x){ return x < 0; }); v.erase(it, v.end()); std::unique – 移除相邻重复元素
std::sort(v.begin(), v.end()); auto it = std::unique(v.begin(), v.end()); v.erase(it, v.end()); // 只保留唯一值 5. 交换类
std::swap – 交换两个变量
std::swap(a, b); std::iter_swap – 交换两个迭代器指向的元素
std::iter_swap(it1, it2); std::swap_ranges – 交换两个区间元素
std::swap_ranges(a.begin(), a.end(), b.begin()); 6. 反转类 / 重排类
std::reverse – 原地反转区间
std::reverse(v.begin(), v.end()); std::reverse_copy
std::reverse_copy(v.begin(), v.end(), std::back_inserter(result)); std::rotate – 左旋或右旋
std::rotate(v.begin(), v.begin() + 2, v.end()); // 左旋 2 位 std::shuffle（C++11 起）
std::random_device rd; std::mt19937 g(rd()); std::shuffle(v.begin(), v.end(), g); 示例：从容器中删去所有负数，并将剩下的数全部翻倍
std::vector<int> v = {-1, 2, -3, 4, 5}; // 1. 删除负数 v.erase(std::remove_if(v.begin(), v.end(), [](int x){ return x < 0; }), v.end()); // 2. 翻倍（用 transform 修改原容器） std::transform(v.begin(), v.end(), v.begin(), [](int x){ return x * 2; }); 总结对比表
| 算法 | 功能 | 注意事项 |
|---|---|---|
copy, copy_if, copy_n |
拷贝区间元素 | 输出容器要预留空间 |
replace, replace_if |
替换元素 | 改变原容器内容 |
fill, generate, iota |
批量填充 | 常用于初始化容器 |
remove, remove_if |
移除元素（惰性） | 需 erase 才真正删除 |
reverse, rotate, shuffle |
调整顺序 | 可用于打乱、移动、翻转 |
swap, iter_swap |
元素互换 | 常用于排序内部实现 |
4. 排序类
当然，下面是对 C++ STL 中 排序类算法（Sorting Algorithms） 的详细介绍，包括常用函数、功能差异、适用场景、性能，以及使用示例。
排序类算法总览
| 算法名称 | 功能 | 特点 |
|---|---|---|
std::sort |
快速排序，默认升序 | 最快，不稳定排序 |
std::stable_sort |
稳定排序（归并） | 保留相等元素相对顺序 |
std::partial_sort |
只排序前 k 个元素 |
部分排序 |
std::nth_element |
将第 n 小元素放到第 n 位 | 非完全排序，适合找中位数 |
std::is_sorted |
判断是否有序 | 布尔返回值 |
std::is_sorted_until |
找到未排序的位置 | 返回迭代器 |
std::reverse |
反转序列 | 非排序，但常结合使用 |
1. std::sort – 快速排序（默认）
将容器内的元素按升序或自定义规则排序，原型：
template <class RandomIt> void sort(RandomIt first, RandomIt last); template <class RandomIt, class Compare> void sort(RandomIt first, RandomIt last, Compare comp); 注意：
- 仅适用于随机访问迭代器：如
vector,array,deque - 平均时间复杂度 O(n log n)，最坏 O(n²)（但实现做了优化）
- 不稳定排序（相等元素相对位置可能变化）
示例：
std::vector<int> v = {5, 3, 1, 4}; std::sort(v.begin(), v.end()); // 升序 std::sort(v.begin(), v.end(), std::greater<>()); // 降序 2. std::stable_sort – 稳定排序
排序后保留相等元素的原始顺序，原型
template <class RandomIt> void stable_sort(RandomIt first, RandomIt last); template <class RandomIt, class Compare> void stable_sort(RandomIt first, RandomIt last, Compare comp); 特点：
- 归并排序实现，时间复杂度 O(n log² n) 或 O(n log n)（部分实现优化）
- 对于排序后仍需依赖原始顺序的情况非常有用
示例：
struct Person { std::string name; int age; }; std::vector<Person> people = {{"Alice", 30}, {"Bob", 25}, {"Amy", 30}}; std::stable_sort(people.begin(), people.end(), [](const Person& a, const Person& b){ return a.age < b.age; }); 3. std::partial_sort – 部分排序
只对前 k 个元素排序
template <class RandomIt> void partial_sort(RandomIt first, RandomIt middle, RandomIt last); template <class RandomIt, class Compare> void partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp); 原理：
- 对
first到last区间排序 - 排好序的前
middle - first个元素放在[first, middle)
示例：找前 3 小：
std::vector<int> v = {9, 2, 7, 4, 1, 5}; std::partial_sort(v.begin(), v.begin() + 3, v.end()); // v[0..2] 是最小的 3 个元素 4. std::nth_element – 找第 n 小的元素
将第 n 小的元素放到正确位置，左边比它小，右边比它大，但左右不保证排序
template <class RandomIt> void nth_element(RandomIt first, RandomIt nth, RandomIt last); template <class RandomIt, class Compare> void nth_element(RandomIt first, RandomIt nth, RandomIt last, Compare comp); - 平均时间复杂度为 O(n)（适合大数据场景）
示例：
std::vector<int> v = {7, 2, 4, 8, 1, 5}; std::nth_element(v.begin(), v.begin() + 2, v.end()); // 第 3 小的数放在 v[2] 5. std::is_sorted / is_sorted_until
std::is_sorted：
判断区间是否已经排序
bool ok = std::is_sorted(v.begin(), v.end()); std::is_sorted_until：
返回第一个不满足排序规则的迭代器
auto it = std::is_sorted_until(v.begin(), v.end()); 6. std::reverse – 反转
将容器内数据反转
std::reverse(v.begin(), v.end()); #include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> v = {9, 2, 7, 4, 1, 5}; std::reverse(v.begin(), v.end()); for (int v1: v) { std::cout << v1 << " "; } //输出 5 1 4 7 2 9 } 应用实例对比
✔ 找出前 5 个最大值（降序）
std::partial_sort(v.begin(), v.begin() + 5, v.end(), std::greater<>()); ✔ 排序自定义对象（按多个字段）
struct Student { std::string name; int score; int age; }; std::sort(v.begin(), v.end(), [](const Student& a, const Student& b){ return std::tie(a.score, a.age) > std::tie(b.score, b.age); // score优先降序，age降序 }); 选择建议
| 需求 | 推荐算法 |
|---|---|
| 完整排序，速度优先 | std::sort |
| 完整排序，顺序稳定 | std::stable_sort |
| 找第 n 小（或前 k 小） | std::nth_element |
| 排前几项即可 | std::partial_sort |
| 判断是否已排序 | std::is_sorted |
5. 比较类
std::equal
判断两个序列的所有对应元素是否相等。
// 第一种：两个范围 [first1, last1) 和 从 first2 开始的序列 template<class InputIt1, class InputIt2> bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2); // 第二种：自定义比较函数 template<class InputIt1, class InputIt2, class BinaryPredicate> bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2, BinaryPredicate p); 自定义比较器：
#include <string> #include <algorithm> #include <cctype> bool char_equal_ignore_case(char a, char b) { return std::tolower(a) == std::tolower(b); } int main() { std::string s1 = "Hello"; std::string s2 = "hELLo"; if (std::equal(s1.begin(), s1.end(), s2.begin(), char_equal_ignore_case)) { std::cout << "Equal ignoring casen"; } } std::lexicographical_compare
std::lexicographical_compare 是一个 STL 算法，用于判断两个序列的字典序（lexicographical order）大小关系。
bool smaller = std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()); 6. 数值类（需 <numeric>）
数值类算法是 <numeric> 头文件中定义的 STL 算法，主要用于对容器中的数值数据进行数学计算。这些算法是对“数值序列”的常见处理模式的抽象，例如求和、求积、生成数列等。
| 算法 | 作用 | 常见用途 |
|---|---|---|
std::accumulate |
求区间元素的累加或其他二元操作的结果 | 求和、拼接字符串、自定义累积 |
std::inner_product |
求两个区间的内积（点积） | 向量相乘、相似度计算等 |
std::iota |
用顺序值填充容器 | 初始化、编号等 |
std::accumulate：累加 / 累积值
- 对区间
[first, last)中的元素进行累计处理 - 默认是执行
init + x1 + x2 + ...
template<class InputIt, class T> T accumulate(InputIt first, InputIt last, T init); // 可自定义操作 template<class InputIt, class T, class BinaryOperation> T accumulate(InputIt first, InputIt last, T init, BinaryOperation op); 示例：
std::vector<int> v = {1, 2, 3, 4}; int sum = std::accumulate(v.begin(), v.end(), 0); // 10 std::string s = std::accumulate(v.begin(), v.end(), std::string(), [](std::string acc, int x) { return acc + std::to_string(x); }); // s = "1234" std::inner_product：内积 / 点积
- 对两个序列执行：
init + a1*b1 + a2*b2 + ... - 可自定义加法和乘法操作
template<class InputIt1, class InputIt2, class T> T inner_product(InputIt1 first1, InputIt1 last1, InputIt2 first2, T init); // 自定义操作 template<class InputIt1, class InputIt2, class T, class BinaryOperation1, class BinaryOperation2> T inner_product(InputIt1 first1, InputIt1 last1, InputIt2 first2, T init, BinaryOperation1 add_op, BinaryOperation2 mul_op); 示例：
std::vector<int> a = {1, 2, 3}; std::vector<int> b = {4, 5, 6}; int dot = std::inner_product(a.begin(), a.end(), b.begin(), 0); // 1×4 + 2×5 + 3×6 = 32 std::iota：填充顺序值
- 将容器中的元素从起始值开始，逐个递增填充（默认+1）
template<class ForwardIt, class T> void iota(ForwardIt first, ForwardIt last, T value); 示例：
std::vector<int> v(5); std::iota(v.begin(), v.end(), 100); // v = {100, 101, 102, 103, 104} 7. 集合类（容器必须有序）
std::set_union, set_intersection, set_difference
集合类算法是 STL <algorithm> 中用于处理两个有序容器之间集合关系的一组算法。它们模拟了集合的并集、交集、差集等操作。
| 算法名 | 作用 | 返回范围 |
|---|---|---|
std::set_union |
并集：A ∪ B | 所有在 A 或 B 中的元素 |
std::set_intersection |
交集：A ∩ B | 只出现在 A 和 B 中的元素 |
std::set_difference |
差集：A - B | 只出现在 A 中、不在 B 中的元素 |
std::set_symmetric_difference |
对称差集：A △ B | A 或 B 中出现但不都出现的元素 |
- 容器必须有序（如
std::set,std::vector排好序） - 通常输出结果放到另一个容器，用
std::back_inserter
示例代码
- 并集
std::set_union
std::vector<int> a = {1, 2, 4}; std::vector<int> b = {2, 3, 5}; std::vector<int> result; std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(result)); // result = {1, 2, 3, 4, 5} - 交集
std::set_intersection
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(result)); // result = {2} - 差集
std::set_difference（A - B）
std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(result)); // result = {1, 4} - 对称差集
std::set_symmetric_difference
std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(result)); // result = {1, 3, 4, 5} 8. 分区类
std::partition, stable_partition
std::partition 和 std::stable_partition 是 STL 中的分区类算法，用于根据某个条件（谓词）将一个序列划分成两部分：
按照指定条件，把容器中的元素分成两组：一组满足条件，另一组不满足。
std::partition：不保证相对顺序std::stable_partition：保持相对顺序稳定
// 不稳定分区 template<class BidirIt, class UnaryPredicate> BidirIt partition(BidirIt first, BidirIt last, UnaryPredicate p); // 稳定分区 template<class BidirIt, class UnaryPredicate> BidirIt stable_partition(BidirIt first, BidirIt last, UnaryPredicate p); 返回值都是 新的“中间”迭代器：
[first, new_iter)是满足条件的部分[new_iter, last)是不满足的部分
示例代码（分区奇偶）
#include <iostream> #include <vector> #include <algorithm> bool is_odd(int x) { return x % 2 != 0; } int main() { std::vector<int> v = {1, 2, 3, 4, 5, 6}; // std::partition（不稳定） auto it = std::partition(v.begin(), v.end(), is_odd); std::cout << "Partition result: "; for (int n : v) std::cout << n << " "; std::cout << "nFirst even: " << *it << "n"; } 可能输出：（顺序不保证）
Partition result: 5 3 1 4 2 6 First even: 4 稳定版本：std::stable_partition
std::vector<int> v = {1, 2, 3, 4, 5, 6}; auto it = std::stable_partition(v.begin(), v.end(), is_odd); // 输出：1 3 5 2 4 6 稳定分区保留了原始顺序，即奇数仍然是原来的顺序 1, 3, 5，偶数仍然是 2, 4, 6。
四、常见组合示例
取奇数 → 乘2 → 排序 → 取前 3 个
std::vector<int> v = {1,2,3,4,5,6,7,8}; std::vector<int> filtered, mapped, result; std::copy_if(v.begin(), v.end(), std::back_inserter(filtered), [](int x){ return x % 2 == 1; }); std::transform(filtered.begin(), filtered.end(), std::back_inserter(mapped), [](int x){ return x * 2; }); std::sort(mapped.begin(), mapped.end()); std::copy_n(mapped.begin(), std::min<size_t>(3, mapped.size()), std::back_inserter(result)); 
![洛谷 P11345 [KTSC 2023 R2] 基地简化 题解](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/themes/kemi/img/random/3.jpg&w=218&h=124&zc=1)
