【C/C++】algorithm清单以及适用场景

algorithm清单以及适用场景

C++ 标准库 <algorithm> 中 STL 算法函数主要作用于迭代器区间 [first, last)，并对容器元素进行操作。

---

1 算法介绍

1.1 分类

• 非修改序列算法
• 修改序列算法
• 排序与堆算法
• 集合操作算法
• 查找算法
• 二分查找算法
• 去重与分区算法
• 数值算法 <numeric>

---

1.2 非修改序列算法

函数	说明
for_each	对每个元素应用函数
count / count_if	统计等于/满足条件的元素个数
find / find_if / find_if_not	查找元素
mismatch	找出第一个不匹配的元素对
equal	判断两个区间是否相等
all_of / any_of / none_of	判断所有/任一/无元素满足条件

---

1.3 修改序列算法

函数	说明
copy / copy_if	拷贝元素
move	移动元素
fill / fill_n	用指定值填充区间
transform	应用函数于每个元素
replace / replace_if / replace_copy	替换元素
remove / remove_if / remove_copy	删除元素（惰性）
unique / unique_copy	删除连续重复元素
reverse / reverse_copy	反转区间
rotate / rotate_copy	旋转元素
shuffle	随机打乱
swap_ranges	交换两个区间元素
partition / stable_partition	分区（按条件拆分）

---

1.4 排序与堆算法

函数	说明
sort / stable_sort	快速排序 / 稳定排序
partial_sort / partial_sort_copy	局部排序
nth_element	找第 n 小的元素，部分排序
is_sorted / is_sorted_until	判断是否已排序
make_heap / push_heap / pop_heap / sort_heap	堆算法
is_heap / is_heap_until	是否为堆

---

1.5 集合操作算法（要求有序）

函数	说明
merge	合并两个有序区间
includes	是否包含另一区间
set_union	并集
set_intersection	交集
set_difference	差集
set_symmetric_difference	对称差集

---

1.5 查找算法

函数	说明
find / find_if / find_if_not	基础查找
search / search_n	区间搜索（子序列）
adjacent_find	找相邻相等元素
max_element / min_element	找最大/最小值
lexicographical_compare	字典序比较
clamp	限制值在范围内

---

1.6 二分查找算法（有序区间）

函数	说明
binary_search	判断是否存在元素
lower_bound	第一个 ≥ value 的位置
upper_bound	第一个 > value 的位置
equal_range	返回 [lower_bound, upper_bound) 对

---

1.7 去重与分区算法

函数	说明
unique	删除连续重复值
partition	按条件划分元素
stable_partition	稳定版本分区

---

1.8 数值算法 <numeric>

虽然不在 <algorithm> 中，但常配套使用：

函数	说明
accumulate	求和（或自定义函数）
inner_product	内积
partial_sum	前缀和
adjacent_difference	相邻差值

---

2 适用场景

<algorithm> 中的 STL 算法涵盖了绝大多数常见的数据处理操作 —— 排序、查找、修改、合并、去重等。

---

2.1 遍历与条件检查

• 遍历元素并做处理
• 检查是否满足某个条件
• 查找满足某条件的元素

函数	典型用途
for_each	批量操作，例如打印元素
all_of / any_of / none_of	验证所有/部分元素是否满足条件
find, find_if	查找指定元素或满足条件的第一个元素
count, count_if	统计元素个数（或满足条件）

---

2.2 修改容器内容（非排序）

• 替换、删除、移动或复制元素
• 批量处理内容生成新容器

函数	典型用途
copy, copy_if	拷贝部分元素到另一个容器
replace, replace_if	替换满足条件的元素
remove, remove_if	删除元素（注意配合 erase 使用）
transform	元素映射（如 map + lambda）
fill, generate	用指定值或函数填充容器

---

2.3 排序、分区与堆处理

• 排序列表或结构体
• 快速找中位数或前 K 大元素
• 使用堆进行优先队列处理

函数	典型用途
sort, stable_sort	排序，结构体时配合 lambda
nth_element	找第 K 大（或小）元素（O(n)）
is_sorted	判断是否已排序
partition, stable_partition	分离满足条件的元素
make_heap, pop_heap	优先队列模拟，堆结构处理

---

2.4 二分查找（有序容器）

• 有序数组查找元素或插入位置
• 实现 lower_bound 行为

函数	典型用途
lower_bound	第一个 ≥ value 的位置
upper_bound	第一个 > value 的位置
equal_range	返回一对边界迭代器
binary_search	判断元素是否存在

特别适合：std::vector、std::array 上使用，要求 已排序

---

2.5 集合操作（有序容器）

• 处理交集、并集、差集等集合操作（如考试合格名单、权限集合等）

函数	典型用途
set_union, set_intersection	合并或找交集
set_difference	A 中不在 B 中的元素
includes	判断是否完全包含

📌 这些都要求参与操作的容器是有序的

---

2.6 去重、分组与映射

• 去除重复数据
• 将数据按条件拆分分组

函数	典型用途
unique	移除连续重复元素
adjacent_find	查找相邻重复元素
group_by（C++23）	分组逻辑（新特性）

---

2.7 数值运算 <numeric>

• 前缀和、内积、差分等数学处理

函数	典型用途
accumulate	累加求和
partial_sum	构建前缀和数组
inner_product	点积计算
adjacent_difference	构建差分数组

---

总结：使用 STL 算法的优势

优点	说明
✅ 简洁	大多数操作 1 行搞定
✅ 高效	内部优化 + 编译器识别
✅ 安全	避免手写循环时的越界、逻辑错误
✅ 可读性好	和业务逻辑贴近，便于维护