C++ 标准库算法实用手册

for_each

对范围内每个元素执行一个操作。注意传入的函数可能会修改元素，比如下面这个把每个数翻倍。

vector<int> vec = {1, 2, 3, 4, 5};
for_each(vec.begin(), vec.end(), [](int& x) { x *= 2; });
// vec 变成 {2, 4, 6, 8, 10}

equal 与 mismatch

equal 比较两个区间是否完全相同；mismatch 返回第一处不匹配的位置对。

vector<int> a = {1, 2, 3};
vector<int> b = {1, 2, 4};
vector<int> c = {1, 2, 3, 4};

bool is_equal = equal(a.begin(), a.end(), b.begin());
cout << "a == b? " << boolalpha << is_equal << endl; // false

auto mis = mismatch(a.begin(), a.end(), c.begin());
if (mis.first != a.end())
    cout << "mismatch: " << *mis.first << " vs " << *mis.second << endl; // 这里不会输出，因为 a 和 c 前三个元素相等

all_of, any_of, none_of

这三个函数用来快速判断区间内元素是否全部、存在、或没有满足某个条件。

vector<int> vec = {2, 4, 6, 8};
bool all_even = all_of(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; }); // true
bool any_odd = any_of(vec.begin(), vec.end(), [](int x) { return x % 2 != 0; }); // false
bool none_negative = none_of(vec.begin(), vec.end(), [](int x) { return x < 0; }); // true

修改序列算法

这些算法会直接改动容器内容。

copy 与 copy_if

copy 把整个区间拷贝到目标位置，copy_if 只拷贝满足条件的元素。如果目标没有足够空间，用 back_inserter 更方便——它会自动调用 push_back，不用提前分配。

vector<int> src = {1, 2, 3, 4, 5};
vector<int> dest(5);
copy(src.begin(), src.end(), dest.begin()); // dest: [1,2,3,4,5]

vector<int> evens;
copy_if(src.begin(), src.end(), back_inserter(evens), [](int x) { return x % 2 == 0; }); // evens: [2,4]

transform

对区间内每个元素应用一个函数，结果存到另一个区间。可以一元或二元操作。

vector<int> nums = {1, 2, 3};
vector<int> squares(3);
transform(nums.begin(), nums.end(), squares.begin(), [](int x) { return x * x; }); // squares: [1,4,9]

vector<int> a = {1, 2, 3};
vector<int> b = {4, 5, 6};
vector<int> sum(3);
transform(a.begin(), a.end(), b.begin(), sum.begin(), [](int x, int y) { return x + y; }); // sum: [5,7,9]

replace 系列

replace 把旧值换成新值，replace_if 按条件替换，replace_copy 则在拷贝的同时进行替换，原容器不变。

vector<int> nums = {1, 2, 3, 2, 5};
replace(nums.begin(), nums.end(), 2, 20); // nums: [1,20,3,20,5]

replace_if(nums.begin(), nums.end(), [](int x) { return x > 10; }, 0); // nums: [1,0,3,0,5]

vector<int> res;
replace_copy(nums.begin(), nums.end(), back_inserter(res), 3, 300); // res: [1,0,300,0,5]

remove 与 erase 的经典组合

remove 并不真正删除元素，只是把要删的元素挪到末尾，返回新的逻辑结尾迭代器；必须配合 erase 才能物理删除。很多人第一次都会忘记。

vector<int> nums = {1, 2, 3, 2, 4};
auto new_end = remove(nums.begin(), nums.end(), 2); // nums: [1,3,4,2,2]
nums.erase(new_end, nums.end()); // nums: [1,3,4]

nums = {1, 2, 3, 4, 5};
nums.erase(remove_if(nums.begin(), nums.end(), [](int x) { return x % 2 == 0; }), nums.end()); // nums: [1,3,5]

unique

移除相邻的重复元素，同样返回新的逻辑尾迭代器，一般也要接 erase。

vector<int> vec = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto last = unique(vec.begin(), vec.end());
vec.erase(last, vec.end()); // vec: {1, 2, 3, 4, 5}

reverse 与 rotate

reverse 直接反转区间；rotate 把区间旋转，让中间元素成为新的起点。

vector<int> vec = {1, 2, 3, 4, 5};
reverse(vec.begin(), vec.end()); // {5, 4, 3, 2, 1}

vec = {1, 2, 3, 4, 5};
rotate(vec.begin(), vec.begin() + 2, vec.end()); // {3, 4, 5, 1, 2}

shuffle

随机打乱，需要提供一个随机数生成器。C++11 之后推荐用 random_device 和 mt19937。

#include <random>
#include <algorithm>
vector<int> vec = {1, 2, 3, 4, 5};
random_device rd;
mt19937 g(rd());
shuffle(vec.begin(), vec.end(), g); // 随机打乱

排序相关算法

sort、stable_sort 与 partial_sort

sort 默认升序，底层通常是 introsort，不稳定；stable_sort 保证相等元素相对顺序不变，空间开销稍大；partial_sort 只把最小的几个元素排到前面。

vector<int> vec = {5, 3, 1, 4, 2};
sort(vec.begin(), vec.end()); // {1, 2, 3, 4, 5}
sort(vec.begin(), vec.end(), greater<int>()); // {5, 4, 3, 2, 1}

vector<pair<int, int>> vec2 = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
stable_sort(vec2.begin(), vec2.end(), [](const auto& a, const auto& b) { return a.first < b.first; });

vec = {5, 3, 1, 4, 2, 6};
partial_sort(vec.begin(), vec.begin() + 3, vec.end()); // 前三个是 1,2,3，后面无序

nth_element

把第 n 小的元素放在正确位置，左边都不大于它，右边都不小于。复杂度 O(n)。

vector<int> vec = {5, 3, 1, 4, 2, 6};
nth_element(vec.begin(), vec.begin() + 2, vec.end()); // vec[2] 是 3

二分查找系列（必须已排序）

binary_search 只返回 bool，lower_bound 返回第一个不小于目标的迭代器，upper_bound 返回第一个大于目标的迭代器。

vector<int> sorted = {1, 3, 3, 5, 7};
bool exists = binary_search(sorted.begin(), sorted.end(), 3); // true
auto lb = lower_bound(sorted.begin(), sorted.end(), 3); // 指向第一个 3 (索引 1)
auto ub = upper_bound(sorted.begin(), sorted.end(), 3); // 指向第一个大于 3 的元素 (索引 3)

merge

合并两个已经排好序的区间。

vector<int> a = {1, 3, 5};
vector<int> b = {2, 4, 6};
vector<int> merged(a.size() + b.size());
merge(a.begin(), a.end(), b.begin(), b.end(), merged.begin()); // {1,2,3,4,5,6}

堆算法

把 vector 当作堆来用，默认是大顶堆。

vector<int> vec = {4, 1, 3, 2, 5};
make_heap(vec.begin(), vec.end()); // 大顶堆，vec: {5,4,3,2,1}
vec.push_back(6);
push_heap(vec.begin(), vec.end()); // 新元素入堆
pop_heap(vec.begin(), vec.end()); // 堆顶移到末尾
int max_val = vec.back(); vec.pop_back(); // 取出最大元素
sort_heap(vec.begin(), vec.end()); // 递增排序，vec: {1,2,3,4,5}

最小/最大值算法

min 和 max

可直接比较两个值或一个初始化列表。

int a = 5, b = 3;
int m = min(a, b); // 3
int M = max(a, b); // 5
auto min_list = min({4, 2, 8, 5, 1}); // 1
auto max_list = max({4, 2, 8, 5, 1}); // 8

min_element 与 max_element

返回区间内最小/最大元素的迭代器。

vector<int> vec = {3, 1, 4, 2, 5};
auto min_it = min_element(vec.begin(), vec.end()); // 指向 1
auto max_it = max_element(vec.begin(), vec.end()); // 指向 5

minmax_element (C++11)

一次返回最小和最大两个迭代器。

vector<int> vec = {3, 1, 4, 2, 5};
auto minmax = minmax_element(vec.begin(), vec.end());
// minmax.first 指向 1, minmax.second 指向 5

数值算法（）

accumulate

默认累加，也可以指定自定义二元运算，比如乘。

#include <numeric>
vector<int> vec = {1, 2, 3, 4, 5};
int sum = accumulate(vec.begin(), vec.end(), 0); // 15
int product = accumulate(vec.begin(), vec.end(), 1, multiplies<int>()); // 120

inner_product

计算两个区间的内积。

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

iota

用连续递增的值填充。

vector<int> vec(5);
iota(vec.begin(), vec.end(), 10); // {10,11,12,13,14}

partial_sum

计算部分和。

vector<int> src = {1, 2, 3, 4, 5};
vector<int> dst(src.size());
partial_sum(src.begin(), src.end(), dst.begin()); // {1,3,6,10,15}

adjacent_difference

相邻元素差值。

vector<int> src = {1, 2, 3, 4, 5};
vector<int> dst(src.size());
adjacent_difference(src.begin(), src.end(), dst.begin()); // {1,1,1,1,1}

其他常用算法

generate 与 generate_n

用生成器填充。

vector<int> vec(5);
int n = 0;
generate(vec.begin(), vec.end(), [&n]() { return n++; }); // {0,1,2,3,4}

vector<int> vec2(5);
n = 10;
generate_n(vec2.begin(), 3, [&n]() { return n++; }); // 前三个 {10,11,12}，后面不变

includes

检查一个排序区间是否包含另一个排序区间的所有元素。

vector<int> v1 = {1,2,3,4,5};
vector<int> v2 = {2,4};
bool inc = includes(v1.begin(), v1.end(), v2.begin(), v2.end()); // true

集合操作

并集、交集、差集、对称差集，要求区间已排序。

vector<int> v1 = {1,2,3,4,5};
vector<int> v2 = {3,4,5,6,7};
vector<int> res;

set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(res)); // {1,2,3,4,5,6,7}

res.clear();
set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(res)); // {3,4,5}

res.clear();
set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(res)); // {1,2}

res.clear();
set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(res)); // {1,2,6,7}

几个容易踩的坑

sort vs stable_sort：sort 是 introsort，不稳定；stable_sort 基于归并排序，稳定但内存占用稍高。如果你依赖相等元素的相对顺序，就得用 stable_sort。

remove 要配合 erase：remove 只是把要删除的元素挪到末尾并返回新终点，容器大小不变。单独用 remove 会留下垃圾元素，典型写法是 vec.erase(remove(vec.begin(), vec.end(), val), vec.end())。

要求已排序的算法：二分查找系列、集合算法、merge 等都要求输入区间有序，否则结果未定义。使用前务必 sort 一下。