algorithm — 算法库

<algorithm> 是 STL 的灵魂，提供 100+ 个泛型算法。配合 C++20 Ranges，让数据处理代码既高效又优雅。

查找算法

#include <algorithm>
#include <vector>

std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5};

// 线性查找
auto it = std::find(v.begin(), v.end(), 5);          // 找值
auto it2 = std::find_if(v.begin(), v.end(),
    [](int x) { return x > 4; });                    // 找满足条件的
auto it3 = std::find_if_not(v.begin(), v.end(),
    [](int x) { return x < 5; });                    // 找不满足条件的

// 二分查找（需要有序）
std::vector<int> sorted = {1, 2, 3, 4, 5, 6, 7};
bool found = std::binary_search(sorted.begin(), sorted.end(), 4);
auto lo = std::lower_bound(sorted.begin(), sorted.end(), 4);  // 第一个 >= 4
auto hi = std::upper_bound(sorted.begin(), sorted.end(), 4);  // 第一个 > 4
auto [lo2, hi2] = std::equal_range(sorted.begin(), sorted.end(), 4);

// 统计
int cnt = std::count(v.begin(), v.end(), 5);          // 值为 5 的个数
int cnt2 = std::count_if(v.begin(), v.end(),
    [](int x) { return x % 2 == 0; });               // 偶数个数

// 检查
bool all_pos = std::all_of(v.begin(), v.end(), [](int x){ return x > 0; });
bool any_big = std::any_of(v.begin(), v.end(), [](int x){ return x > 8; });
bool none_neg = std::none_of(v.begin(), v.end(), [](int x){ return x < 0; });

排序算法

std::vector<int> v = {5, 3, 1, 4, 2};

// 完全排序
std::sort(v.begin(), v.end());                          // 升序
std::sort(v.begin(), v.end(), std::greater<int>{});     // 降序
std::sort(v.begin(), v.end(), [](int a, int b){ return a > b; });

// 稳定排序（保持相等元素的相对顺序）
std::stable_sort(v.begin(), v.end());

// 部分排序（只排前 k 个）
std::partial_sort(v.begin(), v.begin() + 3, v.end());  // 前3个有序

// 第 k 小元素（O(n) 均摊）
std::nth_element(v.begin(), v.begin() + 2, v.end());
// v[2] 是第3小的元素，左边都 ≤ v[2]，右边都 ≥ v[2]

// 检查是否有序
bool sorted = std::is_sorted(v.begin(), v.end());
auto it = std::is_sorted_until(v.begin(), v.end());  // 第一个乱序位置

// 自定义比较器（结构体排序）
struct Person { std::string name; int age; };
std::vector<Person> people = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};
std::sort(people.begin(), people.end(),
    [](const Person& a, const Person& b) { return a.age < b.age; });

变换算法

std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst(src.size());

// transform：对每个元素应用函数
std::transform(src.begin(), src.end(), dst.begin(),
    [](int x) { return x * x; });  // dst = {1, 4, 9, 16, 25}

// 二元 transform
std::vector<int> a = {1, 2, 3}, b = {4, 5, 6};
std::vector<int> c(3);
std::transform(a.begin(), a.end(), b.begin(), c.begin(),
    std::plus<int>{});  // c = {5, 7, 9}

// fill / generate
std::fill(dst.begin(), dst.end(), 0);
std::fill_n(dst.begin(), 3, 42);  // 前3个填42

int n = 0;
std::generate(dst.begin(), dst.end(), [&n]{ return n++; });  // 0,1,2,3,4
std::generate_n(dst.begin(), 3, []{ return rand(); });

// replace
std::replace(v.begin(), v.end(), 1, 99);  // 把所有 1 替换为 99
std::replace_if(v.begin(), v.end(), [](int x){ return x < 3; }, 0);

复制与移动

std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst;

// copy
std::copy(src.begin(), src.end(), std::back_inserter(dst));
std::copy_if(src.begin(), src.end(), std::back_inserter(dst),
    [](int x){ return x % 2 == 0; });  // 只复制偶数
std::copy_n(src.begin(), 3, std::back_inserter(dst));  // 复制前3个

// move（转移所有权）
std::move(src.begin(), src.end(), std::back_inserter(dst));

// remove（不真正删除，返回新的逻辑末尾）
auto new_end = std::remove(v.begin(), v.end(), 3);
v.erase(new_end, v.end());  // erase-remove 惯用法

// C++20 简化
std::erase(v, 3);
std::erase_if(v, [](int x){ return x % 2 == 0; });

// unique（去除相邻重复，需先排序）
std::sort(v.begin(), v.end());
auto it = std::unique(v.begin(), v.end());
v.erase(it, v.end());

数值算法

#include <numeric>

std::vector<int> v = {1, 2, 3, 4, 5};

// 求和
int sum = std::accumulate(v.begin(), v.end(), 0);  // 15
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>{});

// C++17 reduce（可并行）
int sum2 = std::reduce(v.begin(), v.end());  // 默认加法
int sum3 = std::reduce(v.begin(), v.end(), 0, std::plus<int>{});

// 前缀和
std::vector<int> prefix(v.size());
std::partial_sum(v.begin(), v.end(), prefix.begin());  // {1,3,6,10,15}

// 相邻差
std::vector<int> diff(v.size());
std::adjacent_difference(v.begin(), v.end(), diff.begin());  // {1,1,1,1,1}

// 内积
std::vector<int> a = {1,2,3}, b = {4,5,6};
int dot = std::inner_product(a.begin(), a.end(), b.begin(), 0);  // 32

// iota：填充递增序列
std::vector<int> idx(10);
std::iota(idx.begin(), idx.end(), 0);  // {0,1,2,3,4,5,6,7,8,9}

C++20 Ranges 算法

#include <algorithm>
#include <ranges>

std::vector<int> v = {5, 3, 1, 4, 2};

// ranges 算法：不需要 begin/end，更简洁
std::ranges::sort(v);
std::ranges::reverse(v);
auto it = std::ranges::find(v, 3);
bool found = std::ranges::binary_search(v, 3);

// 投影（projection）：对比较键进行变换
struct Person { std::string name; int age; };
std::vector<Person> people = {{"Alice", 30}, {"Bob", 25}};
std::ranges::sort(people, {}, &Person::age);  // 按 age 排序，无需 lambda

// 管道组合
auto result = v
    | std::views::filter([](int x){ return x > 2; })
    | std::views::transform([](int x){ return x * 10; });

for (int x : result) std::cout << x << " ";  // 惰性求值

关键认知

STL 算法是经过高度优化的，比手写循环更快且更安全。erase-remove 是删除元素的标准惯用法（C++20 用 std::erase/std::erase_if 更简洁）。C++20 Ranges 让算法组合变得优雅，优先使用。