50 C++ STL模板库-算法库 algorithm

STL模板库——算法库 algorithm

这下算法都包含在标准库中的 <algorithm>头文件中
合理使用算法库可大幅提升代码效率和可读性，避免重复造轮子。

一、非修改序列操作（Non-modifying）

检查元素但不修改容器。

1. all_of

检查所有元素是否满足条件。

std::vector<int> v = {2, 4, 6, 8};
bool allEven = std::all_of(v.begin(), v.end(), [](int i){ return i % 2 == 0; }); // true 

2. any_of

检查至少一个元素满足条件。

bool hasFive = std::any_of(v.begin(), v.end(), [](int i){ return i == 5; }); // false 

3. none_of

检查无元素满足条件。

bool noNegative = std::none_of(v.begin(), v.end(), [](int i){ return i < 0; }); // true 

4. for_each

对每个元素执行操作。

std::for_each(v.begin(), v.end(), [](int& i){ i *= 2; }); // v变为 {4, 8, 12, 16}

5. count

统计匹配值的元素数量。

int cnt = std::count(v.begin(), v.end(), 8); // cnt = 1 

6. count_if

按条件统计元素数量。

int cntEven = std::count_if(v.begin(), v.end(), [](int i){ return i % 4 == 0; }); // 2 

7. mismatch

返回两序列首个不同元素的位置。

std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = {1, 4, 3};
auto p = std::mismatch(v1.begin(), v1.end(), v2.begin()); // p.first → 2, p.second → 4 

8. find

查找首个匹配值的元素。

auto it = std::find(v.begin(), v.end(), 12); // 指向12的迭代器 

9. find_if

查找首个满足条件的元素。

auto it = std::find_if(v.begin(), v.end(), [](int i){ return i > 10; }); // 指向12

10. find_if_not

查找首个不满足条件的元素。

auto it = std::find_if_not(v.begin(), v.end(), [](int i){ return i < 10; }); // 指向12

11. find_end

在序列中查找子序列的最后一次出现。

std::vector<int> main = {1,2,3,4,1,2,3};
std::vector<int> sub = {1,2,3};
auto it = std::find_end(main.begin(), main.end(), sub.begin(), sub.end()); // 指向第2个{1,2,3}

12. find_first_of

在序列中查找子序列中任意元素的首次出现。

std::vector<int> main = {4,3,2,1};
std::vector<int> targets = {5,1,7};
auto it = std::find_first_of(main.begin(), main.end(), targets.begin(), targets.end()); // 指向1

13. adjacent_find

查找首对相邻重复元素。

std::vector<int> v = {1,3,3,5,7};
auto it = std::adjacent_find(v.begin(), v.end()); // 指向第一个3

14. search

在序列中查找子序列的首次出现。

auto it = std::search(main.begin(), main.end(), sub.begin(), sub.end()); // 指向第一个{1,2,3}

15. search_n

查找连续n个相同值的元素。

std::vector<int> v = {1,2,2,2,3};
auto it = std::search_n(v.begin(), v.end(), 3, 2); // 指向连续3个2的起点 

二、修改序列操作（Modifying）

直接修改容器内容。

1. copy

复制序列到新位置。

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

2. copy_n

精确复制n个元素。

std::copy_n(src.begin(), 2, dest.begin()); // dest前2位 = {1,2}

3. copy_if

按条件复制元素。

std::copy_if(src.begin(), src.end(), dest.begin(), [](int i){ return i%2==1; }); // {1,3}

4. copy_backward

从后向前复制（避免重叠覆盖）。

std::vector<int> v = {1,2,3,4,5};
std::copy_backward(v.begin(), v.begin()+3, v.end()); // v变为 {1,2,1,2,3}

5. move (C++11)

移动元素（转移所有权）。

std::vector<std::string> a = {"apple", "banana"}, b(2);
std::move(a.begin(), a.end(), b.begin()); // a为空，b = {"apple", "banana"}

6. move_backward

从后向前移动。

std::vector<int> v = {1,2,3,4};
std::move_backward(v.begin(), v.begin()+2, v.end()); // v = {1,2,1,2}

7. swap_ranges

交换两序列内容。

std::vector<int> a = {1,2}, b = {3,4};
std::swap_ranges(a.begin(), a.end(), b.begin()); // a={3,4}, b={1,2}

8. transform

对元素应用函数并存储结果。

std::vector<int> v = {1,2,3}, result(3);
std::transform(v.begin(), v.end(), result.begin(), [](int i){ return i*2; }); // result = {2,4,6}

9. replace

替换指定值。

std::vector<int> v = {1,2,3,2};
std::replace(v.begin(), v.end(), 2, 99); // v = {1,99,3,99}

10. replace_if

按条件替换值。

std::replace_if(v.begin(), v.end(), [](int i){ return i<3; }, 0); // v = {0,0,3,0}

11. replace_copy

复制并替换值。

std::vector<int> src = {1,2,3}, dest(3);
std::replace_copy(src.begin(), src.end(), dest.begin(), 2, 99); // dest = {1,99,3}

12. replace_copy_if

复制并按条件替换。

std::replace_copy_if(src.begin(), src.end(), dest.begin(), [](int i){return i%2==1;}, 0); // dest={0,2,0}

13. fill

用指定值填充序列。

std::vector<int> v(5);
std::fill(v.begin(), v.end(), 10); // v = {10,10,10,10,10}

14. fill_n

填充前n个元素。

std::fill_n(v.begin(), 3, 5); // v = {5,5,5,10,10}

15. generate

用函数生成值填充序列。

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

16. generate_n

生成前n个元素。

std::generate_n(v.begin(), 3, []{ return 10; }); // v = {10,10,10,3,4}

17. remove

删除指定值（逻辑删除）。

std::vector<int> v = {1,2,3,2};
auto end = std::remove(v.begin(), v.end(), 2); // v变为{1,3,?,?}, end指向3后一位 
v.erase(end, v.end()); // 物理删除 → {1,3}

18. remove_if

按条件删除元素。

end = std::remove_if(v.begin(), v.end(), [](int i){ return i%2==0; });

19. remove_copy

复制时跳过指定值。

std::vector<int> src = {1,2,3}, dest;
std::remove_copy(src.begin(), src.end(), std::back_inserter(dest), 2); // dest = {1,3}

20. remove_copy_if

复制时跳过满足条件的元素。

std::remove_copy_if(src.begin(), src.end(), std::back_inserter(dest), [](int i){ return i<3; });

21. unique

删除连续重复元素。

std::vector<int> v = {1,1,2,3,3};
auto end = std::unique(v.begin(), v.end()); // v = {1,2,3,?,?}
v.erase(end, v.end()); // {1,2,3}

22. unique_copy

复制时跳过连续重复。

std::unique_copy(v.begin(), v.end(), std::back_inserter(dest)); // dest = {1,2,3}

23. reverse

反转序列顺序。

std::vector<int> v = {1,2,3};
std::reverse(v.begin(), v.end()); // v = {3,2,1}

24. reverse_copy

复制并反转序列。

std::reverse_copy(v.begin(), v.end(), std::back_inserter(dest)); // dest = {1,2,3}

25. rotate

循环左移序列。

std::vector<int> v = {1,2,3,4};
std::rotate(v.begin(), v.begin()+2, v.end()); // v = {3,4,1,2} (以3为起点)

26. rotate_copy

复制并循环移动。

std::rotate_copy(v.begin(), v.begin()+1, v.end(), std::back_inserter(dest)); 

27. sample (C++17)

从序列中随机抽样。

std::vector<int> in = {1,2,3,4}, out;
std::sample(in.begin(), in.end(), std::back_inserter(out), 2, std::mt19937{std::random_device{}()});

28. shift_left / shift_right (C++20)

序列左右移位。

std::vector<int> v = {1,2,3,4};
std::shift_left(v.begin(), v.end(), 1); // v = {2,3,4,0} (左移1位)

三、排序与划分（Sorting/Partitioning）

1. sort

升序排序。

std::vector<int> v = {4,2,5,1};
std::sort(v.begin(), v.end()); // v = {1,2,4,5}

2. stable_sort

稳定排序（保持相等元素顺序）。

std::stable_sort(v.begin(), v.end());

3. partial_sort

部分排序（前n个最小元素）。

std::partial_sort(v.begin(), v.begin()+2, v.end()); // 前2位是 {1,2}

4. partial_sort_copy

复制并部分排序。

std::vector<int> src = {4,2,5}, dest(2);
std::partial_sort_copy(src.begin(), src.end(), dest.begin(), dest.end()); // dest = {2,4}

5. is_sorted

检查序列是否已排序。

bool sorted = std::is_sorted(v.begin(), v.end()); // false

6. is_sorted_until

查找首个破坏排序的元素。

auto it = std::is_sorted_until(v.begin(), v.end()); // 指向5（若v={1,2,4,3}）

7. partition

按条件划分序列（真值在前）。

std::vector<int> v = {1,2,3,4};
auto p = std::partition(v.begin(), v.end(), [](int i){ return i%2==0; }); // v={4,2,3,1}, p指向3 

8. stable_partition

稳定划分（保持相对顺序）。

auto p = std::stable_partition(v.begin(), v.end(), [](int i){ return i>2; }); // v={3,4,1,2}

9. partition_copy

复制时划分到两个容器。

std::vector<int> even, odd;
std::partition_copy(v.begin(), v.end(), std::back_inserter(even), std::back_inserter(odd),[](int i){ return i%2==0; });

10. is_partitioned

检查序列是否被划分。

bool part = std::is_partitioned(v.begin(), v.end(), [](int i){ return i>2; }); // true

11. partition_point

查找划分点。

auto p = std::partition_point(v.begin(), v.end(), [](int i){ return i>2; }); // 指向1 

四、二分搜索（Binary Search）

要求序列已排序！

1. lower_bound

返回首个 ≥ 指定值的迭代器。

std::vector<int> v = {1,2,4,5};
auto it = std::lower_bound(v.begin(), v.end(), 3); // 指向4 

2. upper_bound

返回首个 > 指定值的迭代器。

it = std::upper_bound(v.begin(), v.end(), 4); // 指向5

3. equal_range

返回匹配值的范围 [lower_bound, upper_bound)。

auto [low, high] = std::equal_range(v.begin(), v.end(), 4); // [指向4, 指向5)

4. binary_search

检查值是否存在。

bool exists = std::binary_search(v.begin(), v.end(), 3); // false 

五、堆操作（Heap）

基于堆的优先队列。

1. make_heap

将序列转化为最大堆。

std::vector<int> v = {3,1,4,2};
std::make_heap(v.begin(), v.end()); // v = {4,2,3,1}

2. push_heap

向堆中插入元素（需先push_back）。

v.push_back(5);
std::push_heap(v.begin(), v.end()); // v = {5,4,3,1,2}

3. pop_heap

移除堆顶元素（移至容器尾）。

std::pop_heap(v.begin(), v.end()); // 堆顶5移至末尾 → v = {4,2,3,1,5}
v.pop_back(); // 移除5 

4. sort_heap

堆排序（升序）。

std::sort_heap(v.begin(), v.end()); // v = {1,2,3,4}

5. is_heap

检查是否为堆。

bool isHeap = std::is_heap(v.begin(), v.end()); // false 

6. is_heap_until

查找首个破坏堆结构的元素。

auto it = std::is_heap_until(v.begin(), v.end()); // 指向末尾（已是堆）

六、合并操作（Merge）

1. merge

合并两个有序序列。

std::vector<int> v1 = {1,3}, v2 = {2,4}, dest(4);
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), dest.begin()); // dest={1,2,3,4}

2. inplace_merge

合并同一容器的两个有序子序列。

std::vector<int> v = {1,3,2,4};
std::inplace_merge(v.begin(), v.begin()+2, v.end()); // v={1,2,3,4}

3. includes

检查一个序列是否包含另一个序列。

bool contains = std::includes(dest.begin(), dest.end(), v1.begin(), v1.end()); // true 

4. set_union

求两个有序序列的并集。

std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), dest.begin());

5. set_intersection

求两个有序序列的交集。

std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), dest.begin());

6. set_difference

求差集（在v1中但不在v2中）。

std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), dest.begin());

7. set_symmetric_difference

求对称差集（仅在一个序列中出现的元素）。

std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), dest.begin());

七、排列操作（Permutation）

1. next_permutation

生成下一个字典序排列。

std::vector<int> v = {1,2,3};
while (std::next_permutation(v.begin(), v.end())) {// 遍历所有排列：{1,3,2} → {2,1,3} → ...
}

2. prev_permutation

生成上一个字典序排列。

std::prev_permutation(v.begin(), v.end());

3. is_permutation

检查一个序列是否为另一个的排列。

bool isPerm = std::is_permutation(v1.begin(), v1.end(), v2.begin());

八、数值操作（Numeric）

需包含 <numeric>头文件，但常与算法库协同使用。

1. iota

用递增序列填充容器。

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

2. accumulate

累加元素（可自定义操作）。

int sum = std::accumulate(v.begin(), v.end(), 0); // 10+11+...=60 
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>());

3. inner_product

计算两序列内积（点积）。

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

4. adjacent_difference

计算相邻元素的差。

std::vector<int> src = {2,4,8}, result(3);
std::adjacent_difference(src.begin(), src.end(), result.begin()); // result = {2,2,4}

5. partial_sum

计算部分和（前缀和）。

std::partial_sum(src.begin(), src.end(), result.begin()); // result = {2,6,14}

6. reduce (C++17)

并行累加（无序）。

int sum = std::reduce(v.begin(), v.end());

7. transform_reduce (C++17)

先变换再累加。

int sq_sum = std::transform_reduce(v.begin(), v.end(), 0, std::plus<>(),[](int i){ return i*i; });

8. inclusive_scan (C++17)

并行前缀和（包含当前元素）。

std::inclusive_scan(v.begin(), v.end(), result.begin());

9. exclusive_scan (C++17)

并行前缀和（不包含当前元素）。

std::exclusive_scan(v.begin(), v.end(), result.begin(), 0);

九、比较操作（Comparison）

1. equal

比较两序列是否相等。

bool same = std::equal(v1.begin(), v1.end(), v2.begin());

2. lexicographical_compare

字典序比较。

bool less = std::lexicographical_compare(v1.begin(), v1.end(), v2.begin(), v2.end());

3. lexicographical_compare_three_way (C++20)

三路字典序比较。

auto cmp = std::lexicographical_compare_three_way(v1.begin(), v1.end(), v2.begin(), v2.end());

十、最值操作（Min/Max）

1. min / max / minmax

返回最小/最大/两者。

int m = std::min({5,3,8}); // 3// 同时返回最小值和最大值
auto [minVal, maxVal] = std::minmax({5,3,8}); // minVal=3, maxVal=8

2. min_element / max_element / minmax_element

在序列中查找最值。

// 查找序列中最小值位置 
auto it = std::min_element(vec.begin(),  vec.end()); // 查找序列中最大值位置 
auto it = std::max_element(vec.begin(),  vec.end()); // 同时查找最小值和最大值位置 
auto [min_it, max_it] = std::minmax_element(vec.begin(),  vec.end()); 

3. clamp (C++17)

将值限制在范围内。

int clamped = std::clamp(10, 0, 5); // 返回值5

关键分类：
非修改操作（15个）、修改操作（28个）、排序划分（11个）、二分查找（4个）、堆操作（6个）、合并操作（7个）、排列操作（3个）、数值操作（9个）、比较操作（3个）、最值操作（8个）。

十一、 <numeric> 与 <algorithm> 库的核心区别

库/特性	<numeric>	<algorithm>
核心目标	数值计算与统计分析	通用数据操作与容器管理
典型操作	累加、内积、前缀和、并行归约	排序、查找、复制、变换、逻辑判断
数学关联性	强（直接处理数值运算逻辑）	弱（关注元素操作，不涉及数学推导）
哲学差异	侧重数学语义的封装（如点积、统计计算）	侧重数据操作的抽象（如元素遍历、结构变换）
适用场景	数值密集型任务如科学计算、统计分析）	通用数据处理（如容器操作、业务逻辑）