1、非修改序列算法
这些算法不会改变它们所操作的容器中的元素。
1.1 find 和 find_if
find(begin, end, value)：查找第一个等于value的元素，返回迭代器（未找到返回end）。find_if(begin, end, predicate)：查找第一个满足谓词的元素。find_end(begin, end, sub_begin, sub_end)：查找子序列最后一次出现的位置。
1vector<int> nums = {1, 3, 5, 7, 9}; 2 3// 查找值为5的元素 4auto it = find(nums.begin(), nums.end(), 5); 5if (it != nums.end()) { 6 cout << "found: " << *it << endl; // 输出：5 7} 8 9// 查找第一个大于6的元素 10auto it2 = find_if(nums.begin(), nums.end(), [](int x) { 11 return x > 6; 12}); 13cout << "first >6: " << *it2 << endl; // 输出：7 14 15// 查找子序列 16vector<int> sub = {3, 5}; 17auto it3 = find_end(nums.begin(), nums.end(), sub.begin(), sub.end()); 18if (it3 != nums.end()) { 19 cout << "subsequence starts at index: " << it3 - nums.begin() << endl; // 输出：1 20} 21
1.2 count 和 count_if
count(begin, end, value)：统计等于value的元素个数。count_if(begin, end, predicate)：统计满足谓词（predicate）的元素个数。
1std::vector<int> vec = {1, 2, 3, 2, 4, 2}; 2int cnt = std::count(vec.begin(), vec.end(), 2); // 计数2的个数，结果为3 3int even_cnt = std::count_if(vec.begin(), vec.end(), [](int x) { 4 return x % 2 == 0; 5}); // 偶数个数，结果为4 6
1.3 for_each
对范围内的每个元素应用一个函数
1std::vector<int> vec = {1, 2, 3, 4, 5}; 2std::for_each(vec.begin(), vec.end(), [](int& x) { 3 x *= 2; // 将每个元素乘以2 4}); 5// 现在vec变为{2, 4, 6, 8, 10} 6
1.4 equal 与 mismatch
equal(b1, e1, b2)：判断两个范围[b1,e1)和[b2, b2+(e1-b1))是否相等。mismatch(b1, e1, b2)：返回两个范围中第一个不相等元素的迭代器对（pair）。
1vector<int> a = {1, 2, 3}; 2vector<int> b = {1, 2, 4}; 3vector<int> c = {1, 2, 3, 4}; 4 5// 比较a和b的前3个元素 6bool is_equal = equal(a.begin(), a.end(), b.begin()); 7cout << "a == b? " << boolalpha << is_equal << endl; // 输出：false 8 9// 查找a和c的第一个不匹配元素 10auto mis = mismatch(a.begin(), a.end(), c.begin()); 11if (mis.first != a.end()) { 12 cout << "mismatch: " << *mis.first << " vs " << *mis.second << endl; // 无输出（a和c前3元素相等） 13} 14
1.5 all_of, any_of, none_of
检查范围内元素是否全部、存在或没有满足条件的
1std::vector<int> vec = {2, 4, 6, 8}; 2bool all_even = std::all_of(vec.begin(), vec.end(), [](int x) { 3 return x % 2 == 0; 4}); // true 5bool any_odd = std::any_of(vec.begin(), vec.end(), [](int x) { 6 return x % 2 != 0; 7}); // false 8bool none_negative = std::none_of(vec.begin(), vec.end(), [](int x) { 9 return x < 0; 10}); // true 11
2、修改序列算法
这些算法会修改它们所操作的容器中的元素。
2.1 copy 和 copy_if
copy(begin, end, dest)：将[begin, end)中的元素复制到dest开始的位置。copy_if(begin, end, dest, predicate)：复制满足谓词的元素到dest。
1vector<int> src = {1, 2, 3, 4, 5}; 2vector<int> dest(5); // 需预先分配足够空间 3 4// 复制所有元素 5copy(src.begin(), src.end(), dest.begin()); // dest: [1,2,3,4,5] 6 7// 复制偶数元素到新容器 8vector<int> evens; 9copy_if(src.begin(), src.end(), back_inserter(evens), [](int x) { 10 return x % 2 == 0; 11}); // evens: [2,4] 12
注意：back_inserter(dest) 会自动调用 push_back，无需提前分配空间。
2.2 transform
对范围内的每个元素应用一个函数，并将结果存储在另一个范围内
1vector<int> nums = {1, 2, 3}; 2vector<int> squares(3); 3 4// 计算平方（单参数转换） 5transform(nums.begin(), nums.end(), squares.begin(), [](int x) { 6 return x * x; 7}); // squares: [1,4,9] 8 9// 两容器元素相加（双参数转换） 10vector<int> a = {1, 2, 3}; 11vector<int> b = {4, 5, 6}; 12vector<int> sum(3); 13transform(a.begin(), a.end(), b.begin(), sum.begin(), [](int x, int y) { 14 return x + y; 15}); // sum: [5,7,9] 16
2.3 replace、replace_if与 replace_copy
replace(begin, end, old_val, new_val)：将所有old_val替换为new_val。replace_if(begin, end, predicate, new_val)：替换满足谓词的元素。replace_copy(begin, end, dest, old_val, new_val)：复制时替换元素（不修改原容器）。
1vector<int> nums = {1, 2, 3, 2, 5}; 2 3// 替换所有2为20 4replace(nums.begin(), nums.end(), 2, 20); // nums: [1,20,3,20,5] 5 6// 替换大于10的元素为0 7replace_if(nums.begin(), nums.end(), [](int x) { 8 return x > 10; 9}, 0); // nums: [1,0,3,0,5] 10 11// 复制时替换3为300（原容器不变） 12vector<int> res; 13replace_copy(nums.begin(), nums.end(), back_inserter(res), 3, 300); // res: [1,0,300,0,5] 14
2.4 remove、remove_if 与 erase
remove(begin, end, value)：将等于value的元素 “移动” 到容器末尾，返回新的逻辑尾迭代器（不实际删除元素，需配合erase）。remove_if(begin, end, predicate)：移动满足谓词的元素到末尾。
1vector<int> nums = {1, 2, 3, 2, 4}; 2 3// 逻辑删除所有2（移动到末尾） 4auto new_end = remove(nums.begin(), nums.end(), 2); // nums: [1,3,4,2,2] 5 6// 物理删除（真正移除元素） 7nums.erase(new_end, nums.end()); // nums: [1,3,4] 8 9// 结合lambda删除偶数 10nums = {1, 2, 3, 4, 5}; 11nums.erase(remove_if(nums.begin(), nums.end(), [](int x) { 12 return x % 2 == 0; 13}), nums.end()); // nums: [1,3,5] 14
2.5 unique
移除范围内连续的重复元素，返回新的逻辑结尾迭代器。通常与erase结合使用。
1std::vector<int> vec = {1, 1, 2, 2, 3, 3, 3, 4, 5}; 2auto last = std::unique(vec.begin(), vec.end()); 3vec.erase(last, vec.end()); // vec变为{1, 2, 3, 4, 5} 4
2.6 reverse
反转范围内的元素顺序
1std::vector<int> vec = {1, 2, 3, 4, 5}; 2std::reverse(vec.begin(), vec.end()); // vec变为{5, 4, 3, 2, 1} 3
2.7 rotate
旋转范围内的元素，使中间元素成为新的第一个元素
1std::vector<int> vec = {1, 2, 3, 4, 5}; 2std::rotate(vec.begin(), vec.begin() + 2, vec.end()); // 以3为起点旋转，vec变为{3, 4, 5, 1, 2} 3
2.8 shuffle
随机重排范围内的元素（需要C++11或更高版本）
1#include <random> 2#include <algorithm> 3 4std::vector<int> vec = {1, 2, 3, 4, 5}; 5std::random_device rd; 6std::mt19937 g(rd()); 7std::shuffle(vec.begin(), vec.end(), g); // 随机打乱vec中的元素 8
3、排序和相关算法
3.1 sort、stable_sort 与 partial_sort
sort(begin, end)：对元素进行快速排序（不稳定，平均时间复杂度 O (n log n)）。stable_sort(begin, end)：稳定排序（相等元素相对位置不变）。partial_sort(begin, mid, end)：部分排序，使[begin, mid)为整个范围中最小的元素并排序。
1std::vector<int> vec = {5, 3, 1, 4, 2}; 2std::sort(vec.begin(), vec.end()); // 默认升序，vec变为{1, 2, 3, 4, 5} 3std::sort(vec.begin(), vec.end(), std::greater<int>()); // 降序，vec变为{5, 4, 3, 2, 1} 4std::sort(vec.begin(), vec.end(), [](int a, int b) { 5 return a < b; 6}); // 升序，自定义比较 7 8std::vector<std::pair<int, int>> vec = {{1, 2}, {2, 1}, {1, 1}, {2, 2}}; 9std::stable_sort(vec.begin(), vec.end(), [](const auto& a, const auto& b) { 10 return a.first < b.first; // 按first排序，保持相等元素的相对顺序 11}); 12 13std::vector<int> vec = {5, 3, 1, 4, 2, 6}; 14// 将最小的3个元素放在前面并排序 15std::partial_sort(vec.begin(), vec.begin() + 3, vec.end()); 16// 现在vec前三个元素是1, 2, 3，后面是未排序的4, 5, 6 17
3.2 nth_element
重新排列范围，使得指定位置的元素等于排序后的元素，并且左边的元素都不大于它，右边的元素都不小于它
1std::vector<int> vec = {5, 3, 1, 4, 2, 6}; 2// 找到第三小的元素（索引2） 3std::nth_element(vec.begin(), vec.begin() + 2, vec.end()); 4// 现在vec[2]是3，它左边的元素<=3，右边的>=3 5
3.3 binary_search、lower_bound、upper_bound
需在已排序的容器上使用
binary_search(begin, end, value)：判断value是否存在（返回bool）。lower_bound(begin, end, value)：返回第一个不小于value的元素迭代器。upper_bound(begin, end, value)：返回第一个大于value的元素迭代器。
1vector<int> sorted = {1, 3, 3, 5, 7}; // 必须先排序 2 3// 判断3是否存在 4bool exists = binary_search(sorted.begin(), sorted.end(), 3); // true 5 6// 查找第一个>=3的元素 7auto lb = lower_bound(sorted.begin(), sorted.end(), 3); 8cout << "lower_bound index: " << lb - sorted.begin() << endl; // 输出：1 9 10// 查找第一个>3的元素 11auto ub = upper_bound(sorted.begin(), sorted.end(), 3); 12cout << "upper_bound index: " << ub - sorted.begin() << endl; // 输出：3 13
3.4 merge
合并两个已排序的范围到新容器（保持排序）
1vector<int> a = {1, 3, 5}; 2vector<int> b = {2, 4, 6}; 3vector<int> merged(a.size() + b.size()); 4 5// 合并a和b（均需已排序） 6merge(a.begin(), a.end(), b.begin(), b.end(), merged.begin()); // merged: [1,2,3,4,5,6] 7
4、堆算法
STL提供了将范围作为堆来操作的算法，包括make_heap, push_heap, pop_heap, sort_heap等。
1std::vector<int> vec = {4, 1, 3, 2, 5}; 2std::make_heap(vec.begin(), vec.end()); // 构建最大堆，vec变为{5, 4, 3, 2, 1} 3 4vec.push_back(6); 5std::push_heap(vec.begin(), vec.end()); // 将新元素加入堆，vec变为{6, 4, 5, 2, 1, 3} 6 7std::pop_heap(vec.begin(), vec.end()); // 将最大元素移到末尾，vec变为{5, 4, 3, 2, 1, 6} 8int max_val = vec.back(); // 获取最大元素6 9vec.pop_back(); // 移除最大元素 10 11std::sort_heap(vec.begin(), vec.end()); // 将堆排序为升序序列，vec变为{1, 2, 3, 4, 5} 12
5、最小/最大值算法
5.1 min 和 max
返回两个值或初始化列表中的最小/最大值
1int a = 5, b = 3; 2int min_val = std::min(a, b); // 3 3int max_val = std::max(a, b); // 5 4 5auto min_of_list = std::min({4, 2, 8, 5, 1}); // 1 6auto max_of_list = std::max({4, 2, 8, 5, 1}); // 8 7
5.2 min_element 和 max_element
返回范围内的最小/最大元素的迭代器
1std::vector<int> vec = {3, 1, 4, 2, 5}; 2auto min_it = std::min_element(vec.begin(), vec.end()); // 指向1 3auto max_it = std::max_element(vec.begin(), vec.end()); // 指向5 4
5.3 minmax_element (C++11)
同时返回范围内的最小和最大元素的迭代器
1std::vector<int> vec = {3, 1, 4, 2, 5}; 2auto minmax = std::minmax_element(vec.begin(), vec.end()); 3// minmax.first指向1，minmax.second指向5 4
6、数值算法（在<numeric>中）
6.1 accumulate
计算范围内元素的累加和（或自定义操作）
1#include <numeric> 2 3std::vector<int> vec = {1, 2, 3, 4, 5}; 4int sum = std::accumulate(vec.begin(), vec.end(), 0); // 和，初始值为0，结果为15 5int product = std::accumulate(vec.begin(), vec.end(), 1, std::multiplies<int>()); // 乘积，初始值为1，结果为120 6
6.2 inner_product
计算两个范围的内积（或自定义操作）
1std::vector<int> a = {1, 2, 3}; 2std::vector<int> b = {4, 5, 6}; 3int dot = std::inner_product(a.begin(), a.end(), b.begin(), 0); // 1*4 + 2*5 + 3*6 = 32 4
6.3 iota
用连续递增的值填充范围
1std::vector<int> vec(5); 2std::iota(vec.begin(), vec.end(), 10); // 填充为10, 11, 12, 13, 14 3
6.4 partial_sum
计算部分和，将结果存储在目标范围内
1std::vector<int> src = {1, 2, 3, 4, 5}; 2std::vector<int> dst(src.size()); 3std::partial_sum(src.begin(), src.end(), dst.begin()); // dst变为{1, 3, 6, 10, 15} 4
6.5 adjacent_difference
计算相邻元素的差值，将结果存储在目标范围内
1std::vector<int> src = {1, 2, 3, 4, 5}; 2std::vector<int> dst(src.size()); 3std::adjacent_difference(src.begin(), src.end(), dst.begin()); // dst变为{1, 1, 1, 1, 1} 4
7、其他
7.1 generate
用生成函数填充范围
1std::vector<int> vec(5); 2int n = 0; 3std::generate(vec.begin(), vec.end(), [&n]() { 4 return n++; 5}); // 填充为0, 1, 2, 3, 4 6
7.2 generate_n
用生成函数填充范围的开始n个元素
1std::vector<int> vec(5); 2int n = 10; 3std::generate_n(vec.begin(), 3, [&n]() { 4 return n++; 5}); // 前三个元素为10, 11, 12，后两个保持不变 6
7.3 includes
检查一个排序范围是否包含另一个排序范围的所有元素
1std::vector<int> vec1 = {1, 2, 3, 4, 5}; 2std::vector<int> vec2 = {2, 4}; 3bool includes = std::includes(vec1.begin(), vec1.end(), vec2.begin(), vec2.end()); // true 4
7.3 set_union, set_intersection, set_difference, set_symmetric_difference
执行集合操作：并集、交集、差集和对称差集
1std::vector<int> v1 = {1, 2, 3, 4, 5}; 2std::vector<int> v2 = {3, 4, 5, 6, 7}; 3std::vector<int> result; 4 5// 并集 6std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result)); 7// result为{1, 2, 3, 4, 5, 6, 7} 8 9// 交集 10result.clear(); 11std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result)); 12// result为{3, 4, 5} 13 14// 差集 (v1 - v2) 15result.clear(); 16std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result)); 17// result为{1, 2} 18 19// 对称差集 (v1 ∪ v2 - v1 ∩ v2) 20result.clear(); 21std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result)); 22// result为{1, 2, 6, 7} 23
8、常见问题
sort与stable_sort的区别？sort采用快速排序（实际是 introsort 算法），不稳定（相等元素的相对位置可能改变），平均时间复杂度 O (n log n)。stable_sort采用归并排序，稳定（相等元素相对位置不变），时间复杂度 O (n log n)，但空间开销略大。
- 为什么
remove算法需要配合erase使用？
remove算法的原理是 “覆盖” 要删除的元素，将保留的元素移到前面，返回新的逻辑尾迭代器，但不修改容器的实际大小。erase则通过迭代器范围真正删除元素，修改容器大小。因此需结合使用：container.erase(remove(...), container.end())。 - 哪些算法需要容器是已排序的？
二分查找系列（binary_search、lower_bound、upper_bound）、集合算法（set_intersection、set_union等）、merge等，这些算法依赖有序性实现高效操作（如二分查找 O (log n)）。
《基于C++的游戏引擎开发》 是转载文章，点击查看原文。
