C++ STL算法库

概述

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

排序

参考:排序算法

排序算法 平均时间复杂度 最差时间复杂度 空间复杂度 数据对象稳定性
冒泡排序 O(n2) O(n2) O(1) 稳定
选择排序 O(n2) O(n2) O(1) 数组不稳定、链表稳定
插入排序 O(n2) O(n2) O(1) 稳定
快速排序 O(n*log2n) O(n2) O(log2n) 不稳定
堆排序 O(n*log2n) O(n*log2n) O(1) 不稳定
归并排序 O(n*log2n) O(n*log2n) O(n) 稳定
希尔排序 O(n*log2n) O(n2) O(1) 不稳定
计数排序 O(n+m) O(n+m) O(n+m) 稳定
桶排序 O(n) O(n) O(m) 稳定
基数排序 O(k*n) O(n2) 稳定
  • k:代表数值中的 “数位” 个数
  • n:代表数据规模
  • m:代表数据的最大值减最小值

查找

查找算法 平均时间复杂度 空间复杂度 查找条件
顺序查找 O(n) O(1) 无序或有序
二分查找(折半查找) O(log2n) O(1) 有序
插值查找 O(log2(log2n)) O(1) 有序
斐波那契查找 O(log2n) O(1) 有序
哈希查找 O(1) O(n) 无序或有序
二叉查找树(二叉搜索树查找) O(log2n)
红黑树 O(log2n)
2-3树 O(log2n - log3n)
B树/B+树 O(log2n)

图搜索算法

图搜索算法 数据结构 遍历时间复杂度 空间复杂度
BFS广度优先搜索 邻接矩阵
邻接链表
O(|v|2)
O(|v|+|E|)
O(|v|2)
O(|v|+|E|)
DFS深度优先搜索 邻接矩阵
邻接链表
O(|v|2)
O(|v|+|E|)
O(|v|2)
O(|v|+|E|)

其他算法

算法 思想 应用
分治法 把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并 循环赛日程安排问题、排序算法(快速排序、归并排序)
动态规划 通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法,适用于有重叠子问题和最优子结构性质的问题 背包问题、斐波那契数列
贪心法 一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法 旅行推销员问题(最短路径问题)、最小生成树、哈夫曼编码

不修改序列的操作

不修改序列的操作 说明
all_of(C++11)
any_of(C++11)
none_of(C++11)
检查一定范围之内,是否全部、存在或不存在元素使得谓词为true (函数模板)
for_each 将一个函数应用于某一范围的元素 (函数模板)
for_each_n(C++17) 应用函数对象到序列的首 n 个元素 (函数模板)
count
count_if
返回满足指定判别的元素数 (函数模板)
mismatch 查找两个范围第一个不同元素的位置 (函数模板)
find
find_if
find_if_not(C++11)
查找满足特定条件的第一个元素 (函数模板)
find_end 查找一定范围内最后出现的元素序列 (函数模板)
find_first_of 查找元素集合中的任意元素 (函数模板)
adjacent_find 查找彼此相邻的两个相同(或其它的关系)的元素 (函数模板)
search 查找一个元素区间 (函数模板)
search_n 在区间中搜索连续一定数目次出现的元素 (函数模板)

修改序列的操作

修改序列的操作 说明
copycopy_if(C++11) 将某一范围的元素复制到一个新的位置 (函数模板)
copy_n(C++11) 复制一定数目的元素到新的位置 (函数模板)
copy_backward 按从后往前的顺序复制一个范围内的元素 (函数模板)
move(C++11) 将某一范围的元素移动到一个新的位置 (函数模板)
move_backward(C++11) 按从后往前的顺序移动某一范围的元素到新的位置 (函数模板)
fill 将一个值赋给一个范围内的元素 (函数模板)
fill_n 将一个值赋给一定数目的元素 (函数模板)
transform 将一个函数应用于某一范围的元素 (函数模板)
generate 赋值相继的函数调用结果给范围中的每个元素 (函数模板)
generate_n 赋值相继的函数调用结果给范围中的 N 个元素 (函数模板)
removeremove_if 移除满足特定标准的元素 (函数模板)
remove_copy
remove_copy_if
复制一个范围内不满足特定条件的元素 (函数模板)
replace
replace_if
将所有满足特定条件的元素替换为另一个值 (函数模板)
replace_copy
replace_copy_if
复制一个范围内的元素,并将满足特定条件的元素替换为另一个值 (函数模板)
swap 交换两个对象的值 (函数模板)
swap_ranges 交换两个范围的元素 (函数模板)
iter_swap 交换两个迭代器所指向的元素 (函数模板)
reverse 将区间内的元素颠倒顺序 (函数模板)
reverse_copy 将区间内的元素颠倒顺序并复制 (函数模板)
shift_left
shift_right(C++20)
迁移范围中的元素 (函数模板)
rotate 将区间内的元素旋转 (函数模板)
rotate_copy 将区间内的元素旋转并复制 (函数模板)
random_shuffle 将范围内的元素随机重新排序 (函数模板)
sample(C++17) 从一个序列中随机选择 n 个元素 (函数模板)
unique 删除区间内连续重复的元素 (函数模板)
unique_copy 删除区间内连续重复的元素并复制 (函数模板)

划分操作

划分操作 说明
is_partitioned(C++11) 判断区间是否被给定的谓词划分 (函数模板)
partition 把一个区间的元素分为两组 (函数模板)
partition_copy(C++11) 将区间内的元素分为两组复制到不同位置 (函数模板)
stable_partition 将元素分为两组,同时保留其相对顺序 (函数模板)
partition_point(C++11) 定位已划分的区域的划分点 (函数模板)

排序操作

排序操作 说明
is_sorted(C++11) 检查区间元素是否按升序排列 (函数模板)
is_sorted_until(C++11) 找出最大的已排序子范围 (函数模板)
sort 将区间按升序排序 (函数模板)
partial_sort 将区间内较小的N个元素排序 (函数模板)
partial_sort_copy 对区间内的元素进行复制并部分排序 (函数模板)
stable_sort 将区间内的元素排序,同时保持相等的元素之间的顺序 (函数模板)
nth_element 将给定的区间部分排序,确保区间被给定的元素划分 (函数模板)

二分搜索操作(在已排序范围上)

二分搜索操作(在已排序范围上) 说明
lower_bound 返回指向第一个不小于给定值的元素的迭代器 (函数模板)
upper_bound 返回指向第一个大于给定值的元素的迭代器 (函数模板)
binary_search 判断一个元素是否在区间内 (函数模板)
equal_range 返回匹配特定键值的元素区间 (函数模板)

集合操作(在已排序范围上)

集合操作(在已排序范围上) 说明
merge 合并两个已排序的区间 (函数模板)
inplace_merge 就地合并两个有序的区间 (函数模板)
includes 如果一个集合是另外一个集合的子集则返回true (函数模板)
set_difference 计算两个集合的差集 (函数模板)
set_intersection 计算两个集合的交集 (函数模板)
set_symmetric_difference 计算两个集合的对称差 (函数模板)
set_union 计算两个集合的并集 (函数模板)

堆操作

堆操作 说明
is_heap 检查给定的区间是否为一个堆 (函数模板)
is_heap_until(C++11) 查找区间中为堆的最大子区间 (函数模板)
make_heap 根据区间内的元素创建出一个堆 (函数模板)
push_heap 将元素加入到堆 (函数模板)
pop_heap 将堆中的最大元素删除 (函数模板)
sort_heap 将堆变成一个排好序的区间 (函数模板)

最小/最大操作

最小/最大操作 说明
max 返回两个元素中的较大者 (函数模板)
max_element 返回区间内的最大元素 (函数模板)
min 返回两个元素中的较小者 (函数模板)
min_element 返回区间内的最小元素 (函数模板)
minmax(C++11) 返回两个元素中的的较大者和较小者 (函数模板)
minmax_element(C++11) 返回区间内的最小元素和最大元素 (函数模板)
clamp(C++17) 在一对边界值间夹住一个值 (函数模板)

比较操作

比较操作 说明
equal 确定两个元素集合是否是相同的 (函数模板)
lexicographical_compare 如果按字典顺序一个区间小于另一个区间,返回true (函数模板)
compare_3way(C++20) 用三路比较比较二个值 (函数模板)
lexicographical_compare_3way(C++20) 用三路比较比价二个范围 (函数模板)

排列操作

排列操作 说明
is_permutation(C++11) 判断一个序列是否为另一个序列的排列组合 (函数模板)
next_permutation 按字典顺序产生区间内元素下一个较大的排列组合 (函数模板)
prev_permutation 按字典顺序产生区间内元素下一个较小的排列组合 (函数模板)

数值运算

数值运算 说明
iota(C++11) 用从起始值开始连续递增的值填充区间 (函数模板)
accumulate 计算区间内元素的和 (函数模板)
inner_product 计算两个区间元素的内积 (函数模板)
adjacent_difference 计算区间内相邻元素之间的差 (函数模板)
partial_sum 计算区间内元素的部分和 (函数模板)
reduce(C++17) 类似 std::accumulate ,除了以乱序 (函数模板)
exclusive_scan(C++17) 类似 std::partial_sum ,第 i 个和中排除第 i 个输入 (函数模板)
inclusive_scan(C++17) 类似 std::partial_sum ,第 i 个和中包含第 i 个输入 (函数模板)
transform_reduce(C++17) 应用函数对象,然后以乱序规约 (函数模板)
transform_exclusive_scan(C++17) 应用函数对象,然后进行排除扫描 (函数模板)
transform_inclusive_scan(C++17) 应用函数对象,然后进行包含扫描 (函数模板)

未初始化内存上的操作

未初始化内存上的操作 说明
uninitialized_copy 将范围内的对象复制到未初始化的内存区域 (函数模板)
uninitialized_copy_n(C++11) 将指定数量的对象复制到未初始化的内存区域 (函数模板)
uninitialized_fill 复制一个对象到以范围定义的未初始化内存区域 (函数模板)
uninitialized_fill_n 复制一个对象到以起点和计数定义的未初始化内存区域 (函数模板)
uninitialized_move(C++17) 移动一个范围的对象到未初始化的内存区域 (函数模板)
uninitialized_move_n(C++17) 移动一定数量对象到未初始化内存区域 (函数模板)
uninitialized_default_construct(C++17) 在范围所定义的未初始化的内存区域以默认初始化构造对象 (函数模板)
uninitialized_default_construct_n(C++17) 在起始和计数所定义的未初始化内存区域用默认初始化构造对象 (函数模板)
uninitialized_value_construct(C++17) 在范围所定义的未初始化内存中用值初始化构造对象 (函数模板)
uninitialized_value_construct_n(C++17) 在起始和计数所定义的未初始化内存区域以值初始化构造对象 (函数模板)
destroy_at(C++17) 销毁在给定地址的对象 (函数模板)
destroy(C++17) 销毁一个范围中的对象 (函数模板)
destroy_n(C++17) 销毁范围中一定数量的对象 (函数模板)

C 库

C 库 说明
定义于头文件 说明
qsort 排序类型未指定的元素的范围 (函数)
bsearch 在未指定类型的数组中搜索元素 (函数)
暂无评论

发送评论 编辑评论


				
上一篇
下一篇