算法库

算法库提供大量用途的函数（例如查找、排序、计数、操作），它们在元素范围上操作。注意，范围定义为 [first, last)，其中 last 指代要查询或修改的最后元素的后一个 元素。

受约束算法 (C++20 起)

C++20 在命名空间 std::ranges 中提供大多数算法的受约束版本，在这些算法中，范围既可以由迭代器-哨位对，也可以由单个 range 实参指定，还支持投影和成员指针可调用对象。另外，还更改了大多数算法的返回类型，以返回算法执行过程中计算的所有潜在有用信息。

std::vector<int> v{7, 1, 4, 0, -1};
std::ranges::sort(v); // 受约束算法

执行策略 (C++17 起)

大多数算法拥有接受执行策略的重载。标准库的算法支持几种执行策略，库中提供了相应的执行策略类型和对象。用户可以通过以对应类型的执行策略对象为参数调用并行算法，静态地选择执行策略。

标准库实现（但不是用户）可以定义额外的执行策略作为扩展。以实现定义类型的执行策略对象调用并行算法的语义是由实现定义的。

允许算法的并行版本（除了 std::for_each 与 std::for_each_n）从范围进行任意的元素复制，只要 std::is_trivially_copy_constructible_v<T> 与 std::is_trivially_destructible_v<T> 都是 true，其中 T 是元素的类型。

在标头 `<execution>` 定义
在命名空间 `std::execution` 定义
sequenced_policyparallel_policyparallel_unsequenced_policyunsequenced_policy (C++17)(C++17)(C++17)(C++20)	执行策略类型 (类)
seqparpar_unsequnseq (C++17)(C++17)(C++17)(C++20)	全局执行策略对象 (常量)
在命名空间 `std` 定义
is_execution_policy (C++17)	测试类是否表示某种执行策略 (类模板)

功能特性测试宏	值	标准	功能特性
`__cpp_lib_parallel_algorithm`	`201603L`	(C++17)	并行算法
`__cpp_lib_execution`	`201603L`	(C++17)	执行策略
`__cpp_lib_execution`	`201902L`	(C++20)	std::execution::unsequenced_policy

不修改序列的操作

批量操作

在标头 `<algorithm>` 定义
for_each	应用一元函数对象到范围中元素 (函数模板)
ranges::for_each (C++20)	应用一元函数对象到范围中元素 (算法函数对象)
for_each_n (C++17)	应用函数对象到序列的前 N 个元素 (函数模板)
ranges::for_each_n (C++20)	应用函数对象到序列的前 N 个元素 (算法函数对象)

搜索操作

在标头 `<algorithm>` 定义
all_ofany_ofnone_of (C++11)(C++11)(C++11)	检查谓词是否对范围中所有、任一或无元素为 true (函数模板)
ranges::all_ofranges::any_ofranges::none_of (C++20)(C++20)(C++20)	检查谓词是否对范围中所有、任一或无元素为 true (算法函数对象)
ranges::containsranges::contains_subrange (C++23)(C++23)	检查范围是否包含给定元素或子范围 (算法函数对象)
findfind_iffind_if_not (C++11)	查找首个满足特定条件的元素 (函数模板)
ranges::findranges::find_ifranges::find_if_not (C++20)(C++20)(C++20)	查找首个满足特定条件的元素 (算法函数对象)
ranges::find_lastranges::find_last_ifranges::find_last_if_not (C++23)(C++23)(C++23)	查找最后一个满足特定条件的元素 (算法函数对象)
find_end	查找元素序列在特定范围中最后一次出现 (函数模板)
ranges::find_end (C++20)	查找元素序列在特定范围中最后一次出现 (算法函数对象)
find_first_of	搜索一组元素中任一元素 (函数模板)
ranges::find_first_of (C++20)	搜索一组元素中任一元素 (算法函数对象)
adjacent_find	查找首对相同（或满足给定谓词）的相邻元素 (函数模板)
ranges::adjacent_find (C++20)	查找首对相同（或满足给定谓词）的相邻元素 (算法函数对象)
countcount_if	返回满足特定条件的元素数目 (函数模板)
ranges::countranges::count_if (C++20)(C++20)	返回满足特定条件的元素数目 (算法函数对象)
mismatch	查找两个范围的首个不同之处 (函数模板)
ranges::mismatch (C++20)	查找两个范围的首个不同之处 (算法函数对象)
equal	判断两组元素是否相同 (函数模板)
ranges::equal (C++20)	判断两组元素是否相同 (算法函数对象)
search	搜索元素范围的首次出现 (函数模板)
ranges::search (C++20)	搜索元素范围的首次出现 (算法函数对象)
search_n	搜索元素在范围中首次连续若干次出现 (函数模板)
ranges::search_n (C++20)	搜索元素在范围中首次连续若干次出现 (算法函数对象)
ranges::starts_with (C++23)	检查一个范围是否始于另一范围 (算法函数对象)
ranges::ends_with (C++23)	检查一个范围是否终于另一范围 (算法函数对象)

折叠操作 (C++23 起)

在标头 `<algorithm>` 定义
ranges::fold_left (C++23)	左折叠范围中元素 (算法函数对象)
ranges::fold_left_first (C++23)	以首元素为初值左折叠范围中元素 (算法函数对象)
ranges::fold_right (C++23)	右折叠范围中元素 (算法函数对象)
ranges::fold_right_last (C++23)	以末元素为初值右折叠范围中元素 (算法函数对象)
ranges::fold_left_with_iter (C++23)	左折叠范围中元素，并返回 pair（迭代器，值） (算法函数对象)
ranges::fold_left_first_with_iter (C++23)	以首元素为初值左折叠范围中元素，并返回 pair（迭代器，optional） (算法函数对象)

修改序列的操作

复制操作

在标头 `<algorithm>` 定义
copycopy_if (C++11)	复制范围中元素到新位置 (函数模板)
ranges::copyranges::copy_if (C++20)(C++20)	复制范围中元素到新位置 (算法函数对象)
copy_n (C++11)	复制若干元素到新位置 (函数模板)
ranges::copy_n (C++20)	复制若干元素到新位置 (算法函数对象)
copy_backward	从后往前复制范围中元素 (函数模板)
ranges::copy_backward (C++20)	从后往前复制范围中元素 (算法函数对象)
move (C++11)	将范围中元素移到新位置 (函数模板)
ranges::move (C++20)	将范围中元素移到新位置 (算法函数对象)
move_backward (C++11)	从后往前将范围中元素移到新位置 (函数模板)
ranges::move_backward (C++20)	从后往前将范围中元素移到新位置 (算法函数对象)

交换操作

在标头 `<algorithm>` 定义 (C++11 前)
在标头 `<utility>` 定义 (C++11 起)
在标头 `<string_view>` 定义
swap	交换两个对象的值 (函数模板)
在标头 `<algorithm>` 定义
swap_ranges	交换两个范围的元素 (函数模板)
ranges::swap_ranges (C++20)	交换两个范围的元素 (算法函数对象)
iter_swap	交换两个迭代器所指向的元素 (函数模板)

变换操作

在标头 `<algorithm>` 定义
transform	应用函数到元素范围，并在目标范围存储结果 (函数模板)
ranges::transform (C++20)	应用函数到元素范围 (算法函数对象)
replacereplace_if	替换所有满足特定条件的值为另一个值 (函数模板)
ranges::replaceranges::replace_if (C++20)(C++20)	替换所有满足特定条件的值为另一个值 (算法函数对象)
replace_copyreplace_copy_if	复制范围，并将满足特定条件的元素替换为另一个值 (函数模板)
ranges::replace_copyranges::replace_copy_if (C++20)(C++20)	复制范围，并将满足特定条件的元素替换为另一个值 (算法函数对象)

生成操作

在标头 `<algorithm>` 定义
fill	以复制的方式赋给定值到范围中所有元素 (函数模板)
ranges::fill (C++20)	赋给定值到范围中元素 (算法函数对象)
fill_n	以复制的方式赋给定值到范围中 N 个元素 (函数模板)
ranges::fill_n (C++20)	赋给定值到若干元素 (算法函数对象)
generate	赋连续函数调用结果到范围中所有元素 (函数模板)
ranges::generate (C++20)	将函数结果保存到范围中 (算法函数对象)
generate_n	赋连续函数调用结果到范围中 N 个元素 (函数模板)
ranges::generate_n (C++20)	保存 N 次函数应用的结果 (算法函数对象)

移除操作

在标头 `<algorithm>` 定义
removeremove_if	移除满足特定条件的元素 (函数模板)
ranges::removeranges::remove_if (C++20)(C++20)	移除满足特定条件的元素 (算法函数对象)
remove_copyremove_copy_if	复制范围并忽略满足特定条件的元素 (函数模板)
ranges::remove_copyranges::remove_copy_if (C++20)(C++20)	复制范围并忽略满足特定条件的元素 (算法函数对象)
unique	移除范围中连续重复元素 (函数模板)
ranges::unique (C++20)	移除范围中连续重复元素 (算法函数对象)
unique_copy	创建某范围的不含连续重复元素的副本 (函数模板)
ranges::unique_copy (C++20)	创建某范围的不含连续重复元素的副本 (算法函数对象)

顺序变更操作

在标头 `<algorithm>` 定义
reverse	逆转范围中的元素顺序 (函数模板)
ranges::reverse (C++20)	逆转范围中的元素顺序 (算法函数对象)
reverse_copy	创建范围的逆向副本 (函数模板)
ranges::reverse_copy (C++20)	创建范围的逆向副本 (算法函数对象)
rotate	旋转范围中的元素顺序 (函数模板)
ranges::rotate (C++20)	旋转范围中的元素顺序 (算法函数对象)
rotate_copy	复制并旋转元素范围 (函数模板)
ranges::rotate_copy (C++20)	复制并旋转元素范围 (算法函数对象)
shift_leftshift_right (C++20)	迁移范围中元素 (函数模板)
ranges::shift_leftranges::shift_right (C++23)	迁移范围中元素 (算法函数对象)
random_shuffleshuffle (C++17 前)(C++11)	随机重排范围中元素 (函数模板)
ranges::shuffle (C++20)	随机重排范围中元素 (算法函数对象)

采样操作

在标头 `<algorithm>` 定义
sample (C++17)	从序列中随机选择 N 个元素 (函数模板)
ranges::sample (C++20)	从序列中随机选择 N 个元素 (算法函数对象)

排序和相关操作

要求

部分算法要求由实参表示的序列“已排序”或“已划分”。未满足要求时行为未定义。

序列在满足以下条件时已按比较器 comp 排序：对于指向序列中的每个迭代器 iter 和每个非负整数 n，如果 iter + n^[1] 是一个指向序列中的某个元素的有效迭代器，那么 comp(*(iter + n), *iter) == false^[1]。

(C++20 前)

序列在满足以下条件时已按比较器 comp 和投影 proj 排序：对于指向序列中的每个迭代器 iter 和每个非负整数 n，如果 iter + n^[1] 是一个指向序列中的某个元素的有效迭代器，那么 bool(std::invoke(comp, std::invoke(proj, *(iter + n)),
std::invoke(proj, *iter)))^[1] 是 false。

序列在满足以下条件时已按比较器 comp 排序：该序列已按比较器 comp 和投影 std::identity{}（即投影到自身）排序。

(C++20 起)

序列 [start, finish) 在满足以下条件时已按表达式 f(e) 划分：存在一个整数 n，使得对于 [0, std::distance(start, finish)) 中的所有整数 i，f(*(start + i))^[1] 当且仅当 i < n 时是 true。

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 在这里 iter + n 只表示 “iter 自增 n 次后的结果”，而 iter 本身不需要是随机访问迭代器。

划分操作

在标头 `<algorithm>` 定义
is_partitioned (C++11)	判断范围是否已按给定谓词划分 (函数模板)
ranges::is_partitioned (C++20)	判断范围是否已按给定谓词划分 (算法函数对象)
partition	将范围中元素分为两组 (函数模板)
ranges::partition (C++20)	将范围中元素分为两组 (算法函数对象)
partition_copy (C++11)	复制范围并将元素分为两组 (函数模板)
ranges::partition_copy (C++20)	复制范围并将元素分为两组 (算法函数对象)
stable_partition	将元素分为两组，同时保留其相对顺序 (函数模板)
ranges::stable_partition (C++20)	将元素分为两组，同时保留其相对顺序 (算法函数对象)
partition_point (C++11)	定位已划分范围的划分点 (函数模板)
ranges::partition_point (C++20)	定位已划分范围的划分点 (算法函数对象)

排序操作

在标头 `<algorithm>` 定义
sort	将范围按升序排序 (函数模板)
ranges::sort (C++20)	将范围按升序排序 (算法函数对象)
stable_sort	将范围中元素排序，同时保持相等元之间的顺序 (函数模板)
ranges::stable_sort (C++20)	将范围中元素排序，同时保持相等元之间的顺序 (算法函数对象)
partial_sort	将范围中前 N 个元素排序 (函数模板)
ranges::partial_sort (C++20)	将范围中前 N 个元素排序 (算法函数对象)
partial_sort_copy	复制范围中元素并部分排序 (函数模板)
ranges::partial_sort_copy (C++20)	复制范围中元素并部分排序 (算法函数对象)
is_sorted (C++11)	检查范围是否已按升序排列 (函数模板)
ranges::is_sorted (C++20)	检查范围是否已按升序排列 (算法函数对象)
is_sorted_until (C++11)	找出最大的有序子范围 (函数模板)
ranges::is_sorted_until (C++20)	找出最大的有序子范围 (算法函数对象)
nth_element	将给定范围部分排序，确保其按给定元素划分 (函数模板)
ranges::nth_element (C++20)	将给定范围部分排序，确保其按给定元素划分 (算法函数对象)

二分搜索操作（在已划分范围上）

在标头 `<algorithm>` 定义
lower_bound	返回首个不小于给定值的元素的迭代器 (函数模板)
ranges::lower_bound (C++20)	返回首个不小于给定值的元素的迭代器 (算法函数对象)
upper_bound	返回首个大于给定值的元素的迭代器 (函数模板)
ranges::upper_bound (C++20)	返回首个大于给定值的元素的迭代器 (算法函数对象)
equal_range	返回匹配特定键值的元素范围 (函数模板)
ranges::equal_range (C++20)	返回匹配特定键值的元素范围 (算法函数对象)
binary_search	判断元素是否在偏序范围中 (函数模板)
ranges::binary_search (C++20)	判断元素是否在偏序范围中 (算法函数对象)

集合操作（在已排序范围上）

在标头 `<algorithm>` 定义
includes	当一个序列是另一个的子序列时返回 true (函数模板)
ranges::includes (C++20)	当一个序列是另一个的子序列时返回 true (算法函数对象)
set_union	计算两个集合的并集 (函数模板)
ranges::set_union (C++20)	计算两个集合的并集 (算法函数对象)
set_intersection	计算两个集合的交集 (函数模板)
ranges::set_intersection (C++20)	计算两个集合的交集 (算法函数对象)
set_difference	计算两个集合的差集 (函数模板)
ranges::set_difference (C++20)	计算两个集合的差集 (算法函数对象)
set_symmetric_difference	计算两个集合的对称差 (函数模板)
ranges::set_symmetric_difference (C++20)	计算两个集合的对称差 (算法函数对象)

归并操作（在已排序范围上）

在标头 `<algorithm>` 定义
merge	合并两个有序范围 (函数模板)
ranges::merge (C++20)	合并两个有序范围 (算法函数对象)
inplace_merge	就地合并两个有序范围 (函数模板)
ranges::inplace_merge (C++20)	就地合并两个有序范围 (算法函数对象)

堆操作

随机访问范围 [first, last) 在满足以下条件时是一个关于比较器 comp 的堆：对于 (0, last - first) 中的所有整数 i，bool(comp(first[(i - 1) / 2], first[i])) 都是 false。

(C++20 前)

随机访问范围 [first, last) 在满足以下条件时是一个关于比较器 comp 和投影 proj 的堆：对于 (0, last - first) 中的所有整数 i，bool(std::invoke(comp, std::invoke(proj, first[(i - 1) / 2]),
std::invoke(proj, first[i])) 都是 false。

随机访问范围 [first, last) 在满足以下条件时是一个关于比较器 comp 的堆：该范围是一个关于 comp 和 std::identity{}（即投影到自身）的堆。