算法库

来自cppreference.com
< cpp


 
C++
 
算法库
受约束算法及范围上的算法 (C++20)
包含算法例如 ranges::copy, ranges::sort, ...
执行策略 (C++17)
排序和相关操作
划分操作
排序操作
二分搜索操作（在已划分范围上）
集合操作（在有序范围上）
归并操作（在有序范围上）
堆操作
最小/最大操作
(C++11)
(C++17)
字典序比较操作
(C++20)
排列操作
C 库

数值运算
(C++11)                       
在未初始化内存上的操作
 

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

受约束算法

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

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


执行策略

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

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

允许算法的并行版本（除了 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 定义
(C++17)(C++17)(C++17)(C++20)
 执行策略类型
(类)
(C++17)(C++17)(C++17)(C++20)
 全局执行策略对象
(常量)
在命名空间 std 定义
(C++17)
 测试一个类是否表示某种执行策略
(类模板)
功能特性测试宏 值 标准 功能特性
__cpp_lib_parallel_algorithm 201603L (C++17) 并行算法
__cpp_lib_execution 201603L (C++17) 执行策略
201902L (C++20) std::execution::unsequenced_policy
(C++17 起)

不修改序列的操作

批量操作

在标头 <algorithm> 定义
应用函数到范围中的元素
(函数模板)
(C++20)
 应用函数到范围中的元素
(niebloid)
(C++17)
 应用一个函数对象到序列的前 n 个元素
(函数模板)
(C++20)
 应用函数对象到序列的前 n 个元素
(niebloid)

搜索操作

在标头 <algorithm> 定义
(C++11)(C++11)(C++11)
 检查谓词是否对范围中所有、任一或无元素为 true
(函数模板)
(C++20)(C++20)(C++20)
 检查谓词是否对范围中所有、任一或无元素为 true
(niebloid)
(C++23)(C++23)
 检查范围是否包含给定的元素或子范围
(niebloid)
(C++11)
 寻找首个满足特定判别标准的元素
(函数模板)
(C++20)(C++20)(C++20)
 查找满足特定条件的的第一个元素
(niebloid)
(C++23)(C++23)(C++23)
 查找满足特定条件的最后一个元素
(niebloid)
在特定范围中寻找最后出现的元素序列
(函数模板)
(C++20)
 查找特定范围中最后出现的元素序列
(niebloid)
搜索元素集合中的任意元素
(函数模板)
(C++20)
 查找范围中的任一元素
(niebloid)
查找首对相邻的相同（或满足给定谓词的）元素
(函数模板)
(C++20)
 查找首对相邻的相同（或满足给定谓词的）元素
(niebloid)
返回满足指定判别标准的元素数
(函数模板)
(C++20)(C++20)
 返回满足指定判别标准的元素数
(niebloid)
寻找两个范围出现不同的首个位置
(函数模板)
(C++20)
 寻找两个范围出现不同的首个位置
(niebloid)
确定两个元素集合是否是相同的
(函数模板)
(C++20)
 确定两个元素范围是否是相同的
(niebloid)
搜索一个元素范围的首次出现
(函数模板)
(C++20)
 搜索一个元素范围的首次出现
(niebloid)
在范围中搜索首次出现的某元素一定量连续副本
(函数模板)
(C++20)
 在范围中搜索首次出现某个元素的一定量连续副本
(niebloid)
(C++23)
 检查一个范围是否始于另一范围
(niebloid)
(C++23)
 检查一个范围是否终于另一范围
(niebloid)

折叠操作

在标头 <algorithm> 定义
(C++23)
 左折叠范围内的元素
(niebloid)
(C++23)
 用第一个元素作为初始值左折叠范围内的元素
(niebloid)
(C++23)
 右折叠范围内的元素
(niebloid)
(C++23)
 使用最后一个元素的值为初始值右折叠范围内的元素
(niebloid)
(C++23)
 左折叠范围内的元素，并且返回 一对（迭代器，值）
(niebloid)
(C++23)
 用第一个元素作为初始值左折叠范围内的元素并返回一对（迭代器，可选值）
(niebloid)

修改序列的操作

复制操作

在标头 <algorithm> 定义
(C++11)
 将某一范围的元素复制到一个新的位置
(函数模板)
(C++20)(C++20)
 将某一范围的元素复制到一个新的位置
(niebloid)
(C++11)
 将一定数目的元素复制到一个新的位置
(函数模板)
(C++20)
 将一定数目的元素复制到一个新的位置
(niebloid)
按从后往前的顺序复制一个范围内的元素
(函数模板)
(C++20)
 按从后往前的顺序复制一个范围内的元素
(niebloid)
(C++11)
 将某一范围的元素移动到一个新的位置
(函数模板)
(C++20)
 将某一范围的元素移动到一个新的位置
(niebloid)
(C++11)
 按从后往前的顺序移动某一范围的元素到新的位置
(函数模板)
(C++20)
 按从后往前的顺序移动某一范围的元素到新的位置
(niebloid)

交换操作

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

变换操作

在标头 <algorithm> 定义
将一个函数应用于某一范围的各个元素，并在目标范围存储结果
(函数模板)
(C++20)
 将一个函数应用于某一范围的各个元素
(niebloid)
将所有满足特定判别标准的值替换为另一个值
(函数模板)
(C++20)(C++20)
 将所有满足特定判别标准的值替换为另一个值
(niebloid)
复制一个范围，并将满足特定判别标准的元素替换为另一个值
(函数模板)
(C++20)(C++20)
 复制一个范围内的元素，并将满足特定判别标准的元素替换为另一个值
(niebloid)

生成操作

在标头 <algorithm> 定义
将一个给定值复制赋值给一个范围内的每个元素
(函数模板)
(C++20)
 以特定值向范围的各元素赋值
(niebloid)
将一个给定值复制赋值给一个范围内的 N 个元素
(函数模板)
(C++20)
 将一个值复制赋值给一定量的元素
(niebloid)
将相继的函数调用结果赋值给一个范围中的每个元素
(函数模板)
(C++20)
 保存函数结果到一个范围中
(niebloid)
将相继的函数调用结果赋值给一个范围中的 N 个元素
(函数模板)
(C++20)
 保存 N 次函数应用的结果
(niebloid)

移除操作

在标头 <algorithm> 定义
移除满足特定判别标准的元素
(函数模板)
(C++20)(C++20)
 移除满足特定判别标准的元素
(niebloid)
复制一个范围的元素，忽略满足特定判别标准的元素
(函数模板)
(C++20)(C++20)
 复制一个范围的元素，忽略满足特定判别标准的元素
(niebloid)
移除范围内的连续重复元素
(函数模板)
(C++20)
 移除范围中的连续重复元素
(niebloid)
创建某范围的不含连续重复元素的副本
(函数模板)
(C++20)
 创建某范围的不含连续重复元素的副本
(niebloid)

顺序变更操作

在标头 <algorithm> 定义
逆转范围中的元素顺序
(函数模板)
(C++20)
 逆转范围中的元素顺序
(niebloid)
创建一个范围的逆向副本
(函数模板)
(C++20)
 创建一个范围的逆向副本
(niebloid)
旋转范围中的元素顺序
(函数模板)
(C++20)
 旋转范围中的元素顺序
(niebloid)
复制并旋转元素范围
(函数模板)
(C++20)
 复制并旋转元素范围
(niebloid)
(C++20)
 迁移范围中的元素
(函数模板)
(C++17 前)(C++11)
 随机重排范围中的元素
(函数模板)
(C++20)
 随机重排范围中的元素
(niebloid)
(C++23)
 迁移范围中的元素
(niebloid)

采样操作

在标头 <algorithm> 定义
(C++17)
 从一个序列中随机选择 N 个元素
(函数模板)
(C++20)
 从序列中随机选择 n 个元素
(niebloid)

排序和相关操作

要求

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

序列在满足以下条件时已按比较器 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. ↑ 1.0 1.1 1.2 1.3 1.4 在这里 iter + n 只表示 “iter 自增 n 次后的结果”，而 iter 本身不需要是随机访问迭代器。

划分操作

在标头 <algorithm> 定义
(C++11)
 判断范围是否已按给定的谓词划分
(函数模板)
(C++20)
 判断范围是否已按给定的谓词划分
(niebloid)
将范围中的元素分为两组
(函数模板)
(C++20)
 将范围中的元素分为二组
(niebloid)
(C++11)
 复制一个范围，将各元素分为两组
(函数模板)
(C++20)
 复制一个范围，将各元素分为二组
(niebloid)
将元素分为两组，同时保留其相对顺序
(函数模板)
(C++20)
 将元素分成二组，同时保持其相对顺序
(niebloid)
(C++11)
 定位已划分范围的划分点
(函数模板)
(C++20)
 定位已划分范围的划分点
(niebloid)

排序操作

在标头 <algorithm> 定义
将范围按升序排序
(函数模板)
(C++20)
 将范围按升序排序
(niebloid)
将范围内的元素排序，同时保持相等的元素之间的顺序
(函数模板)
(C++20)
 将范围内的元素排序，同时保持相等的元素之间的顺序
(niebloid)
排序一个范围的前 N 个元素
(函数模板)
(C++20)
 排序一个范围的前 N 个元素
(niebloid)
对范围内的元素进行复制并部分排序
(函数模板)
(C++20)
 对范围内的元素进行复制并部分排序
(niebloid)
(C++11)
 检查范围是否已按升序排列
(函数模板)
(C++20)
 检查范围是否以升序排序
(niebloid)
(C++11)
 找出最大的有序子范围
(函数模板)
(C++20)
 寻找最大的有序子范围
(niebloid)
将给定的范围部分排序，确保其按给定元素划分
(函数模板)
(C++20)
 将给定的范围部分排序，确保其按给定元素划分
(niebloid)

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

在标头 <algorithm> 定义
返回指向第一个不小于 给定值的元素的迭代器
(函数模板)
(C++20)
 返回指向首个不小于给定值的元素的迭代器
(niebloid)
返回指向第一个大于 给定值的元素的迭代器
(函数模板)
(C++20)
 返回指向首个大于某值的元素的迭代器
(niebloid)
返回匹配特定键值的元素范围
(函数模板)
(C++20)
 返回匹配特定键的元素范围
(niebloid)
确定元素是否存在于某部分有序的范围中
(函数模板)
(C++20)
 确定元素是否存在于某范围中
(niebloid)

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

在标头 <algorithm> 定义
若一个序列是另一个的子序列则返回 true
(函数模板)
(C++20)
 若一个序列是另一个的子列则返回 true
(niebloid)
计算两个集合的并集
(函数模板)
(C++20)
 计算两个集合的并集
(niebloid)
计算两个集合的交集
(函数模板)
(C++20)
 计算两个集合的交集
(niebloid)
计算两个集合的差集
(函数模板)
(C++20)
 计算两个集合的差集
(niebloid)
计算两个集合的对称差
(函数模板)
(C++20)
 计算两个集合的对称差
(niebloid)

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

在标头 <algorithm> 定义
合并两个有序范围
(函数模板)
(C++20)
 归并两个有序范围
(niebloid)
就地合并两个有序范围
(函数模板)
(C++20)
 在原位归并两个有序范围
(niebloid)

堆操作

随机访问范围 [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{}（即投影到自身）的堆。

(C++20 起)

可以通过 std::make_heap 和 ranges::make_heap (C++20 起) 创建堆。

关于堆的更多性质，可以参考最大堆。


在标头 <algorithm> 定义
将一个元素加入到一个最大堆
(函数模板)
(C++20)
 将一个元素加入到一个最大堆
(niebloid)
从最大堆中移除最大元素
(函数模板)
(C++20)
 从最大堆中移除最大元素
(niebloid)
从一个元素范围创建出一个最大堆
(函数模板)
(C++20)
 从一个元素范围创建出一个最大堆
(niebloid)
将一个最大堆变成一个按升序排序的元素范围
(函数模板)
(C++20)
 将一个最大堆变成一个按升序排序的元素范围
(niebloid)
检查给定范围是否为一个最大堆
(函数模板)
(C++20)
 检查给定范围是否为最大堆
(niebloid)
(C++11)
 查找能成为最大堆的最大子范围
(函数模板)
(C++20)
 寻找能成为最大堆的最大子范围
(niebloid)

最小/最大操作

在标头 <algorithm> 定义
返回各给定值中的较大者
(函数模板)
(C++20)
 返回给定值的较大者
(niebloid)
返回范围内的最大元素
(函数模板)
(C++20)
 返回范围中的最大元素
(niebloid)
返回各给定值中的较小者
(函数模板)
(C++20)
 返回给定值的较小者
(niebloid)
返回范围内的最小元素
(函数模板)
(C++20)
 返回范围中的最小元素
(niebloid)
(C++11)
 返回两个元素的较小和较大者
(函数模板)
(C++20)
 返回两个元素的较小和较大者
(niebloid)
(C++11)
 返回范围内的最小元素和最大元素
(函数模板)
(C++20)
 返回范围中的最小和最大元素
(niebloid)
(C++17)
 在一对边界值间夹逼一个值
(函数模板)
(C++20)
 在一对边界值间夹一个值
(niebloid)

字典序比较操作

在标头 <algorithm> 定义
当一个范围按字典顺序小于另一个范围时，返回 true
(函数模板)
(C++20)
 当一个范围按字典顺序小于另一个范围时，返回 true
(niebloid)
(C++20)
 用三路比较比较两个范围
(函数模板)

排列操作

在标头 <algorithm> 定义
产生某个元素范围的按字典顺序的下一个较大的排列
(函数模板)
(C++20)
 产生某个元素范围的按字典序下一个较大的排列
(niebloid)
产生某个元素范围的按字典顺序的下一个较小的排列
(函数模板)
(C++20)
 产生某个元素范围的按字典序下一个较小的排列
(niebloid)
(C++11)
 判断一个序列是否为另一个序列的排列
(函数模板)
(C++20)
 确定一个序列是否为另一序列的排列
(niebloid)

数值运算

在标头 <numeric> 定义
(C++11)
 用从起始值开始连续递增的值填充一个范围
(函数模板)
(C++23)
 用从起始值开始连续递增的值填充一个范围
(niebloid)
对一个范围内的元素求和或折叠
(函数模板)
计算两个范围的元素的内积
(函数模板)
计算范围内各相邻元素之间的差
(函数模板)
计算范围内元素的部分和
(函数模板)
(C++17)
 类似 std::accumulate，但不依序执行
(函数模板)
(C++17)
 类似 std::partial_sum，第 i 个和中排除第 i 个输入
(函数模板)
(C++17)
 类似 std::partial_sum，第 i 个和中包含第 i 个输入
(函数模板)
(C++17)
 应用一个可调用物，然后以乱序规约
(函数模板)
(C++17)
 应用一个可调用物，然后进行排除扫描
(函数模板)
(C++17)
 应用一个可调用物，然后进行包含扫描
(函数模板)

在未初始化内存上的操作

在标头 <memory> 定义
将范围内的对象复制到未初始化的内存区域
(函数模板)
(C++20)
 复制元素范围到未初始化的内存区域
(niebloid)
(C++11)
 将指定数量的对象复制到未初始化的内存区域
(函数模板)
(C++20)
 复制一定量元素到未初始化的内存区域
(niebloid)
复制一个对象到以范围定义的未初始化内存区域
(函数模板)
(C++20)
 复制一个对象到范围所定义的未初始化的内存区域
(niebloid)
复制一个对象到以起点和计数定义的未初始化内存区域
(函数模板)
(C++20)
 复制一个对象到起始与计数所定义的未初始化的内存区域
(niebloid)
(C++17)
 移动一个范围的对象到未初始化的内存区域
(函数模板)
(C++20)
 移动对象范围到未初始化的内存区域
(niebloid)
(C++17)
 移动一定数量对象到未初始化内存区域
(函数模板)
(C++20)
 移动一定量对象到未初始化的内存区域
(niebloid)
(C++17)
 在范围所定义的未初始化的内存区域以默认初始化构造对象
(函数模板)
(C++20)
 在范围所定义的未初始化的内存区域以默认初始化构造对象
(niebloid)
(C++17)
 在起始和计数所定义的未初始化内存区域用默认初始化构造对象
(函数模板)
(C++20)
 在起始与计数所定义的未初始化的内存区域以默认初始化构造对象
(niebloid)
(C++17)
 在范围所定义的未初始化内存中用值初始化构造对象
(函数模板)
(C++20)
 在范围所定义的未初始化的内存区域以值初始化构造对象
(niebloid)
(C++17)
 在起始和计数所定义的未初始化内存区域以值初始化构造对象
(函数模板)
(C++20)
 在起始与计数所定义的未初始化的内存区域以值初始化构造对象
(niebloid)
(C++17)
 销毁一个范围中的对象
(函数模板)
(C++20)
 销毁范围中的元素
(niebloid)
(C++17)
 销毁范围中一定数量的对象
(函数模板)
(C++20)
 销毁范围中一定量的元素
(niebloid)
(C++17)
 销毁在给定地址的对象
(函数模板)
(C++20)
 销毁位于给定地址的元素
(niebloid)
(C++20)
 在给定地址创建对象
(函数模板)
(C++20)
 在给定地址创建对象
(niebloid)

随机数生成

在标头 <random> 定义
(C++26)
 用来自均匀随机位发生器的随机数填充范围
(niebloid)

注解

功能特性测试宏 值 标准 功能特性
__cpp_lib_algorithm_iterator_requirements 202207L (C++23) 对非范围算法使用范围迭代器
__cpp_lib_clamp 201603L (C++17) std::clamp
__cpp_lib_constexpr_algorithms 201806L (C++20) constexpr 算法
202306L (C++26) constexpr 稳定排序
__cpp_lib_algorithm_default_value_type 202403L (C++26) 算法的列表初始化
__cpp_lib_freestanding_algorithm 202311L (C++26) <algorithm> 中的独立设施
__cpp_lib_robust_nonmodifying_seq_ops 201304L (C++14) 使不修改序列的操作更健壮（std::mismatch、std::equal 和 std::is_permutation 的两个范围重载）
__cpp_lib_sample 201603L (C++17) std::sample
__cpp_lib_shift 201806L (C++20) std::shift_left 与 std::shift_right

C 库

在标头 <cstdlib> 定义
对未指定类型的元素的一个范围进行排序
(函数)
在未指定类型的数组中搜索元素
(函数)

缺陷报告

下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。

缺陷报告 应用于 出版时的行为 正确行为
LWG 193 C++98 堆要求 *first 是最大的元素 可以有等于 *first 的元素
LWG 2150 C++98 已排序序列的定义不正确 已改正
LWG 2166 C++98 对堆的要求与最大堆的定义不够接近 改进要求

参阅

来自“https://zh.cppreference.com/mwiki/index.php?title=cpp/algorithm&oldid=91265”