C++ STL算法
STL算法是C++标准库中一组高度优化的通用算法，主要定义在<algorithm>、<numeric>和<functional>头文件中。它们通过迭代器抽象与容器交互，提供丰富的操作功能。
一、STL算法基础架构
1. 设计哲学
泛型编程：通过模板实现类型无关
迭代器抽象：统一访问容器元素的方式
函数对象：支持自定义操作逻辑
2. 核心组件
// 典型算法签名
template <class InputIt, class UnaryPredicate>
InputIt find_if(InputIt first, InputIt last, UnaryPredicate p);InputIt：输入迭代器类型first/last：定义元素范围[first, last)UnaryPredicate：一元谓词（函数对象）
二、算法分类详解
1. 非修改序列算法（只读）
| 算法 | 功能描述 | 复杂度 |
|---|---|---|
all_of | 检查所有元素是否满足条件 | O(n) |
any_of | 检查至少一个元素满足条件 | O(n) |
none_of | 检查没有元素满足条件 | O(n) |
find | 查找特定值 | O(n) |
find_if | 查找满足条件的元素 | O(n) |
count | 统计值出现次数 | O(n) |
mismatch | 找出两个序列第一个不同点 | O(n) |
equal | 比较两个序列是否相等 | O(n) |
示例：
std::vector<int> v{1,2,3,4,5};
bool all_even = std::all_of(v.begin(), v.end(), [](int i){ return i%2==0; });
auto it = std::find(v.begin(), v.end(), 3);
size_t cnt = std::count(v.begin(), v.end(), 2);2. 修改序列算法
| 算法 | 功能描述 | 复杂度 |
|---|---|---|
copy | 复制元素到新位置 | O(n) |
move | 移动元素（C++11） | O(n) |
fill | 填充元素 | O(n) |
replace | 替换特定值 | O(n) |
remove | "删除"特定值（实际是移动） | O(n) |
reverse | 反转元素顺序 | O(n) |
rotate | 旋转元素位置 | O(n) |
unique | 去除相邻重复元素 | O(n) |
示例：
std::vector<int> src{1,2,3}, dest(3);
std::copy(src.begin(), src.end(), dest.begin());std::string s = "Hello";
std::reverse(s.begin(), s.end()); // s = "olleH"std::vector<int> v{1,2,2,3,2,4};
auto last = std::remove(v.begin(), v.end(), 2);
v.erase(last, v.end()); // v = {1,3,4}3. 排序与相关算法
| 算法 | 功能描述 | 复杂度 |
|---|---|---|
sort | 快速排序 | O(n log n) |
stable_sort | 稳定排序（保持相等元素顺序） | O(n log n) |
partial_sort | 部分排序（前N个元素） | O(n log k) |
nth_element | 找出第n小的元素 | O(n) |
is_sorted | 检查是否已排序 | O(n) |
merge | 合并两个有序序列 | O(n+m) |
binary_search | 二分查找 | O(log n) |
示例：
std::vector<int> v{5,3,1,4,2};
std::sort(v.begin(), v.end()); // {1,2,3,4,5}// 只排序前3个元素
std::partial_sort(v.begin(), v.begin()+3, v.end());// 找出中位数
auto mid = v.begin() + v.size()/2;
std::nth_element(v.begin(), mid, v.end());
int median = *mid;4. 数值算法（<numeric>）
| 算法 | 功能描述 |
|---|---|
accumulate | 累加/自定义归约操作 |
inner_product | 计算内积 |
partial_sum | 计算部分和 |
adjacent_difference | 计算相邻差 |
iota | 填充递增序列 |
示例：
std::vector<int> v{1,2,3,4,5};
int sum = std::accumulate(v.begin(), v.end(), 0);
int product = std::accumulate(v.begin(), v.end(), 1, [](int a, int b){ return a*b; });std::vector<int> prefix;
std::partial_sum(v.begin(), v.end(), std::back_inserter(prefix));
// prefix = {1,3,6,10,15}三、高级用法与技巧
1. 迭代器适配器
#include <iterator>// 反向迭代
std::sort(v.rbegin(), v.rend());// 插入迭代器
std::fill_n(std::back_inserter(v), 5, 42);// 流迭代器
std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));2. 谓词组合
#include <functional>auto is_even = [](int x){ return x%2==0; };
auto is_positive = [](int x){ return x>0; };// 组合谓词
auto is_even_positive = [&](int x){return is_even(x) && is_positive(x);
};std::find_if(v.begin(), v.end(), is_even_positive);3. 执行策略（C++17）
#include <execution>// 并行排序
std::sort(std::execution::par, v.begin(), v.end());// 并行变换
std::transform(std::execution::par,v.begin(), v.end(), v.begin(),[](int x){ return x*2; });四、性能优化指南
减少数据拷贝：
// 不好 std::vector<int> copy = original; std::sort(copy.begin(), copy.end());// 好（原地排序） std::sort(original.begin(), original.end());预分配内存：
std::vector<int> result; result.reserve(input.size()); // 避免多次扩容 std::copy_if(input.begin(), input.end(), std::back_inserter(result), predicate);选择合适算法：
小数据量：
std::sort可能优于std::stable_sort部分排序：优先
std::partial_sort或std::nth_element