C++ STL 算法分类速查与常见坑

count 和 count_if

直接统计个数。

#include <vector>
#include <algorithm>
using namespace std;

int main() {
    std::vector<int> vec = {1, 2, 3, 2, 4, 2};
    int cnt = std::count(vec.begin(), vec.end(), 2); // 结果是 3
    int even_cnt = std::count_if(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; }); // 4
    return 0;
}

for_each

对每个元素执行操作。用来就地修改很方便，但注意别把它当万能循环用——有时候 range-for 更直观。

#include <vector>
#include <algorithm>
using namespace std;

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

equal 与 mismatch

• equal(b1, e1, b2) 判断两个范围是否完全相等。
• mismatch(b1, e1, b2) 返回一个 pair，指向第一个不匹配的位置，两端都走完才匹配。

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    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; // 不输出，前三个元素相等
    }
    return 0;
}

all_of, any_of, none_of

这三个用来做条件检查，比写循环简洁。

#include <vector>
#include <algorithm>
using namespace std;

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

修改序列算法

这些算法会改动元素内容或顺序。

copy 和 copy_if

copy 和 copy_if 复制元素到目标位置。注意目标要有足够空间，或者用 back_inserter 自动扩容。

#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    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]
    return 0;
}

transform

做映射转换，单序列、双序列都支持。

#include <vector>
#include <algorithm>
using namespace std;

int main() {
    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]
    return 0;
}

replace、replace_if 与 replace_copy

替换操作很直白，replace_copy 不影响原容器，适合需要保留原始数据的时候。

#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    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]
    return 0;
}

remove、remove_if 与 erase

这一组最容易用错。remove 并不会真正删除元素，只是把要保留的挪到前面，返回一个新逻辑终点，之后必须手动 erase。现在通常直接写 erase(remove_if(...), end())。

#include <vector>
#include <algorithm>
using namespace std;

int main() {
    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]
    return 0;
}

unique

移除连续的重复元素，同样要配合 erase 才能真正去重。如果容器不是排序的，unique 只能去掉相邻重复，不一定能全局去重。

#include <vector>
#include <algorithm>
using namespace std;

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

reverse

反转顺序。

#include <vector>
#include <algorithm>
using namespace std;

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::reverse(vec.begin(), vec.end()); // vec 变成 {5, 4, 3, 2, 1}
    return 0;
}

rotate

让某个中间位置变成新的开头。

#include <vector>
#include <algorithm>
using namespace std;

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::rotate(vec.begin(), vec.begin() + 2, vec.end()); // 以 3 为起点旋转，变成 {3, 4, 5, 1, 2}
    return 0;
}

shuffle

需要随机引擎（C++11 后推荐用 std::mt19937 之类的）。std::random_device 生成种子。

#include <vector>
#include <algorithm>
#include <random>
using namespace std;

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(vec.begin(), vec.end(), g); // 随机打乱
    return 0;
}

排序和相关算法

sort、stable_sort 与 partial_sort

• sort 内部通常用 introsort，不是纯粹快排，无稳定性，但大多数场景够用。
• stable_sort 保证相等元素的相对顺序，性能稍差一点。
• partial_sort 只让前几个元素有序，比如取 Top-K 时很有用。

#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    std::vector<int> vec = {5, 3, 1, 4, 2};
    std::sort(vec.begin(), vec.end()); // 升序 {1, 2, 3, 4, 5}
    std::sort(vec.begin(), vec.end(), std::greater<int>()); // 降序
    std::sort(vec.begin(), vec.end(), [](int a, int b) { return a < b; }); // 自定义

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

    std::vector<int> vec2 = {5, 3, 1, 4, 2, 6};
    std::partial_sort(vec2.begin(), vec2.begin() + 3, vec2.end()); // 前三个排好: 1,2,3, 后面随意
    return 0;
}

nth_element

只保证第 n 个位置放的是完全排序后该位置的值，两边元素只是分别不大于 / 不小于它，但内部不排序。用来找中位数之类的很方便。

#include <vector>
#include <algorithm>
using namespace std;

int main() {
    std::vector<int> vec = {5, 3, 1, 4, 2, 6};
    std::nth_element(vec.begin(), vec.begin() + 2, vec.end()); // vec[2] = 3, 左边 ≤3, 右边 ≥3
    return 0;
}

binary_search、lower_bound、upper_bound

必须在已排序的序列上用，否则行为未定义。lower_bound 是第一个不小于目标的位置，upper_bound 是第一个大于目标的位置。

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    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);
    cout << "lower_bound index: " << lb - sorted.begin() << endl; // 1
    auto ub = upper_bound(sorted.begin(), sorted.end(), 3);
    cout << "upper_bound index: " << ub - sorted.begin() << endl; // 3
    return 0;
}

merge

归并两个有序序列，结果仍然有序。

#include <vector>
#include <algorithm>
using namespace std;

int main() {
    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]
    return 0;
}

堆算法

用 make_heap 建堆（默认最大堆），push_heap 和 pop_heap 维护堆性质，sort_heap 可以输出有序序列。

#include <vector>
#include <algorithm>
using namespace std;

int main() {
    std::vector<int> vec = {4, 1, 3, 2, 5};
    std::make_heap(vec.begin(), vec.end()); // 最大堆 {5,4,3,2,1}
    vec.push_back(6);
    std::push_heap(vec.begin(), vec.end()); // {6,4,5,2,1,3}
    std::pop_heap(vec.begin(), vec.end()); // 最大值移到末尾 {5,4,3,2,1,6}
    int max_val = vec.back(); // 6
    vec.pop_back();
    std::sort_heap(vec.begin(), vec.end()); // 升序 {1,2,3,4,5}
    return 0;
}

最小/最大值算法

min 和 max

可以比较两个值，也支持初始化列表。

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    int a = 5, b = 3;
    int min_val = std::min(a, b); // 3
    int max_val = std::max(a, b); // 5
    auto min_of_list = std::min({4, 2, 8, 5, 1}); // 1
    auto max_of_list = std::max({4, 2, 8, 5, 1}); // 8
    return 0;
}

min_element 和 max_element

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

#include <vector>
#include <algorithm>
using namespace std;

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

minmax_element (C++11)

同时获得最小和最大，返回一对迭代器。

#include <vector>
#include <algorithm>
using namespace std;

int main() {
    std::vector<int> vec = {3, 1, 4, 2, 5};
    auto minmax = std::minmax_element(vec.begin(), vec.end()); // first->1, second->5
    return 0;
}

数值算法（）

accumulate

求和或自定义累积运算。初始值类型决定了返回类型，比如用 0 返回 int，0.0 返回 double。

#include <vector>
#include <numeric>
using namespace std;

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

inner_product

计算点积，也可以传自定义二元操作。

#include <vector>
#include <numeric>
using namespace std;

int main() {
    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); // 32
    return 0;
}

iota

生成递增序列，比手写循环简洁。

#include <vector>
#include <numeric>
using namespace std;

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

partial_sum

计算前缀和。

#include <vector>
#include <numeric>
using namespace std;

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

adjacent_difference

计算相邻元素差，第一个元素直接复制。

#include <vector>
#include <numeric>
using namespace std;

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

其他实用算法

generate 和 generate_n

用生成器填充区间，lambda 捕获引用可以实现状态。

#include <vector>
#include <algorithm>
using namespace std;

int main() {
    std::vector<int> vec(5);
    int n = 0;
    std::generate(vec.begin(), vec.end(), [&n]() { return n++; }); // {0,1,2,3,4}
    n = 10;
    std::generate_n(vec.begin(), 3, [&n]() { return n++; }); // 前三个变成 10,11,12
    return 0;
}

includes

判断一个有序序列是否包含另一个有序序列的所有元素。

#include <vector>
#include <algorithm>
using namespace std;

int main() {
    std::vector<int> vec1 = {1, 2, 3, 4, 5};
    std::vector<int> vec2 = {2, 4};
    bool contains = std::includes(vec1.begin(), vec1.end(), vec2.begin(), vec2.end()); // true
    return 0;
}

集合操作

set_union、set_intersection、set_difference、set_symmetric_difference 都要求输入已排序。

#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {3, 4, 5, 6, 7};
    std::vector<int> result;
    std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result)); // {1,2,3,4,5,6,7}
    result.clear();
    std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result)); // {3,4,5}
    result.clear();
    std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result)); // {1,2}
    result.clear();
    std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result)); // {1,2,6,7}
    return 0;
}

常见问题

sort 与 stable_sort 的区别？

sort 通常用 introsort，效率高但不稳定；stable_sort 一般是归排，保证相等元素相对次序，但内存开销稍大。如果排序后还需要依赖原始顺序的关键字，就得用 stable_sort。

为什么 remove 后必须跟 erase？

STL 算法只操作迭代器，不改变容器大小。remove 把不要的元素挪到末尾，返回新尾迭代器，实际元素还在容器里。只有 erase 才真正删除。惯用法是 v.erase(remove_if(v.begin(), v.end(), pred), v.end())，写熟了很自然，但第一次见到容易掉坑。

哪些算法需要容器已排序？

二分查找类（binary_search、lower_bound、upper_bound）和集合操作（set_union 等）以及 merge 都要求有序，不然结果未定义。另外 equal_range 等也属于此类。使用的容器不一定非要是 set，只要确保提前 sort 过就行。