#include <algorithm>
算法 | 常用版本 | 描述 | 返回Type |
std::find() | find(_InIt _Fisrt ,_InIt _Last, | 从两个迭代器指定的范围 中查找指定值 | 引用被查找的值的iterator 或end() |
std:: find_if() | find_if(_InIt _Fisrt ,_InIt _Last , _CallBack); | 从两个迭代器指定的范围 中查找与回调谓词匹配的实例 | 与谓词匹配的实例的 iterator或end() |
std:: find _if _not() | find_if_not(_InIt _Fisrt ,_InIt _Last ,_Func _CallBack); | 从迭代器范围中返回第一 个不符合谓词的元素 | 第一个不符合谓词的 元素的iterator或end() |
std:: count() | count(_InIt _First ,_InIt _Last , _Ty& _Val); | 求得一个元素序列中与 第三个参数相符的元素的个数 | 与第三个参数匹配的 元素的int个数 |
std:: count_if() | count_if(_InIt _First ,_InIt _Last , _CallBack); | 求得一个序列中与谓 词匹配的元素的个数 | 符合条件元素的int个数 |
std:: generate() | generate(_FwdIt _First ,_FwdIt _Last , _CallBack); | 通过特定值填充一个 迭代器范围 | void |
std::max() | max(_Left,_Right /*,Predicate*/); | 通过operator<或用 户提供的二元谓词比 较任意类型的两个元素 | 返回较大的一个元素 的const引用 |
std::min() | min(_Left,_Right /*,Predicate*/); | 通过operator<或用户 提供的二元谓词比较 任意类型的两个元素 | 较小的一个元素的const引用 |
std::max _element() | max_element(_FwdIt _First ,_FwdIt _Last /*,_Pred*/); | 从一组任意类型的元素 元素序列中查找"最大"的一个 | 引用"最大”的元素的iterator |
std::min _element() | min_element(_FwdIt _First ,_FwdIt _Last /*,_Pred*/); | 从一组任意类型的元素 元素序列中查找"最小 "的一个 | 引用"最小"的元素的iterator |
adjacent _find() | adjacent_find(_FwdIt _First , _FwdIt _Last /*,_Pred*/); | 从一组任意类型的元素 序列中查找有重复的元素 | 引用重复的第一个元素 的iterator或者end() |
std:: all_of() | all_of(_InIt _First ,_InIt _Last ,Pr _Pred); | 当一组元素序列全部 与谓词匹配时返回true 否则返回false | bool |
std:: any_of() | any_of(_InIt _First ,_InIt _Last ,_Pr _Pred); | 当一组元素序列中任意 一个元素与谓词匹配时 返回true否则返回false | bool |
std:: none_of() | none_of(_InIt _First ,_InIt _Last ,_Pr _Pred); | 当一组元素序列全部都 不与谓词匹配时返回true 否则返回false | bool |
std:: for_each() | for_each(_InIt _First ,_InIt _Last ,_CallBack); | 对指定范围内的所有元素 执行一次_CallBack | _CallBackl类型 |
transform() | transform(_InIt_SrcFirst ,_InIt _SrcLast ,_OutIt_DestBegin ,_CallBack); | 对指定范围的元素执行 回调后生成新的元素,然后 将这些新元素保存在第三个 参数指定的目标范围中 | 引用Dest范围的past-the-end 的_OutputIterator |
| transform(_InIt _First1 ,_InIt _Last ,_InIt _First2 ,_OutIt _DestBegin ,_CallBack); | 对两个指定序列的元素 调用二元谓词,并将结果 存入到第四个参数指定 的容器中 | 引用Dest范围的past-the-end 的_OutputIterator |
| equal(_InIt _First1 ,_InIt _Last1 ,_InIt _First2 /*,_Pred*/); | 对两个不同类型的容器 比较对应位置的值,当全部 相等或者全部符合谓词时 返回true否则返回false |
bool |
std::copy() |
copy(_InIt _SrcBegin ,_InIt _SrcEnd ,_OutIt _DestBegin); | 将一个序列的元素复制到 另一个序列中,Src范围 与Dest范围不能相同,但 可以重叠,std::copy不会 向目标序列中插入元素,而 会直接修改元素,使用前 必须配合_Dest序列的 resize()函数给Dest序列 重分配足够的空间 |
引用Dest范围past_the_end的 _OutputIterator |
std::copy _backward() | copy_backward(_InIt _SrcBegin ,_InIt _SrcEnd ,_OutIt _DestEnd); | 将Src范围的元素反向复制 到Dest范围中,也就是从 Src范围最后一个元素开始 复制,将这个元素放在Dest 范围的最后一个位置,然后 再每一次复制后反向移动. 第三个参数应该是_DestEnd 而不是_DestBegin | 引用Dest范围的_Begin() 的_OutputIterator |
std::copy_if |
copy_if(_InIt _SrcBegin ,_InIt _SrcEnd ,_OutIt _DestBegin ,_Pr _Pred); | 对一个序列中每个准备复制 的元素执行一次_Callback, 如果返回值为true,那么 执行copy操作,否则不执行; 返回了Dest范围中最后一个 复制的元素的后一个位置, 这是为了配合past_the_end 来删除多余的元素:复制完 成后使用_Dest.erase( _CopyEndIt,past_the_end); 来删除Dest范围多余的元素位置 |
返回引用Dest范围的最后一个 复制的元素的后一个位置的 _OutputIterator |
std::copy_n() | copy_n(_InIt _SrcBegin ,_Ty _Cnt ,_OutIt _DestBegin); | 从Src范围复制_Cnt个元素 到Dest范围,第二个参数是 一个指定要复制的元素个数 的整数 | 返回引用Dest范围的 past_the_end |
std:: partition _copy() |
partition_copy(_InIt _SrcBegin ,_InIt _SrcEnd,_OutIt _Dest1,_OutIt _Dest2,_Pr _Pred); | 对一个序列的元素进行依据 谓词返回的结果进行划分复制,首先对Src序列中的每一个元素执行一次谓词,如果返回true,那么将这个元素复制到_Dest1,如果返回false,复制到_Dest2,复制之前需要使用resize()重置Dest的空间;算法返回一个打包_Dest1和_Dest2的one_past_the_last_copied的std::pair,利用这个pair可以删除多分配的空间 |
打包引用_Dest1和_Dest2 的one_past_the_last_copied 的_OutputIterator的 std::pair |
|
move(_InIt _SrcBegin,_InIt _SrcEnd,_OutIt _DestBegin); | 需要给元素提供移动赋值运算符,将Src序列的元素通过移动赋值运算符移动到Dest序列,在移动操作中,SrcObject被重置了,因为DstObject接管了SrcObject资源的所有权, | 返回Dest范围的引用 past_the_end的 _OutputIterator |
Std::move _backward() | move_backward(_InIt _SrcBegin, | 使用了和std::move()相同的移动机制,但是按照从最后一个元素向第一个元素的顺序进行移动 | 返回Dest范围的引用_Begin() 的_OutputIterator |
std::replace() | replace(_FwdIt _First,_FwdIt _Last,const _Ty& _OldVal,const _Ty& _NewVal); | 这个算法将一个范围中的匹配某个值的元素替换为第三个参数指定的新值 | void |
std:: replace_if() | replace_if(_FwdIt _First,_FwdIt _Last,_Pr _Pred, | 这个算法将一个范围中的匹配某个谓词的元素替换为第三个参数指定的新值 | void |
std::remove() |
remove(_FwdIt _First,_FwdIt _Last,const _Ty& _Val); | 这个算法并不是将序列中与_Val匹配的元素直接删除,而是将它们移动到容器的末端,然后返回引用第一个被移除的元素的iterator,可以利用这个iterator和end()将被移除的元素彻底擦除 |
返回引用第一个被移除的 元素的_FwdIterator |
std:: remove_if() |
remove_if(_FwdIt _First,_FwdIt _Last,_Pr _Pred); | 这个算法并不是将序列中与谓词匹配的元素直接删除,而是将它们移动到容器的末端,然后返回引用第一个被移除的元素的iterator,可以利用这个iterator和end()将被移除的元素彻底擦除 |
返回引用第一个被移除的 元素的_FwdIterator |
std::unique() |
unique(_FwdIt _First,_FwdIt _Last /*,_Pr _Pred)*/; | std::unique算法是特殊的std::remove算法,和后者一样,std::unique并不是直接将重复的元素删除,而是将它们全部移动到容器的尾端,然后返回引用第一个被移除的元素的iterator,可以利用这个iterator和end()将被移除的元素彻底擦除 |
返回引用第一个被移除的元素的_FwdIterator |
std:: unique_copy | unique(_FwdIt _SrcBegin,_FwdIt _SrcEnd,_OutIt _DestBegin /*,_Pr _Pred*/); | std::unique()的基本形式是就地操作数据,std::unique_copy则是将操作的结果复制到Dest范围中 | 返回引用Dest范围的元素的_OutputIterator |
std::reverse() | reverse(_BidIt _First,_BidIt _Last); | 将范围中的第一个元素和最后一个元素交换,第二个元素和倒数第二个元素交换,依此类推 | Void |
_copy() | reverse_copy(_BidIt _SrcBegin,_BidIt _SrcEnd, | std::reverse是就地操作数据,std::reverse_copy将结果复制到Dest范围中 | 返回引用Dest范围的元素的_OutputIterator |
std::sort() | sort(_RanIt _First,_RanIt _Last /*,_Pr _Pred*/); | 将范围中的元素按operator<或_CallBack进行排序 | Void |
std::merge() |
merge(_InIt _SrcBegin1,_InIt _SrcEnd1,_InIt _SrcBegin2,_InIt _SrcEnd2,_OutIt _DestBegin, | 将两个排好序的Src序列合并成一个元素序列,然后将结果复制到Dest序列中,并且依然保持排序的顺序,结果是一个包含两个Src序列的所有元素的有序序列,注意一定要使用两个排好序的序列进行merge操作 |
引用Dest序列的past_the_end 的_OutputIterator |
std:: is_sorted() | sort(_FwdIt _First,_FwdIt _Last /*,_Pr _Pred*/); | 验证一个序列是否是有序序列.如果是,返回true,否则返回false | bool |
std:random _shuffle() |
random_shuffle(_RanIt _First,_RanIt _Last /*,_Fn& _Func*/ | 将一个序列的顺序打乱,这个算法适用于洗牌之类的任务,对一个版本默认使用标准C库的rand()函数,第二个版本需要提供一个随机数生成器, 以适应不同问题领域的随机性 |
void |
| 集合算法 |
std::includes() | includes(_InIt _First1,_InIt _Last1,_InIt _First2,_InIt _Last2 /*,_Pr _Pred*/); |
|
|
std::set_union() |
set_union(_InIt _SrcBegin1, | 计算两个有序序列的并集,然后将并集的结果存入第四个参数指定的Dest序列中,注意在计算前必须给Dest容器分配足够的空间,因为Dest范围最大是_Src1和_Src2的size()和,所以在进行合并后有可能会留下一些空间,set_union算法返回一个引用Dest范围中最后一个被添加进去的元素的后一个位置的iterator,利用它可以将Dest中多余的空间删除 |
返回一个引用Dest范围中最后一个被添加进去的元素的后一个位置的_OutputIterator
|
std::set _intersection() | set_intersection( _InIt _SrcBegin1, | 计算两个有序序列的交集,然后将交集的结果存入第四个参数指定的Dest序列中,注意在计算前必须给Dest容器分配足够的空间,因为Dest范围最大是两个_Src范围的size的最大值,所以在进行取交集后有可能会留下一些空间,set_union算法返回一个引用Dest范围中最后一个被添加进去的元素的后一个位置的iterator,利用它可以将Dest中多余的空间删除 |
返回一个引用Dest范围中最后一个被添加进去的元素的后一个位置的_OutputIterator
|
std ::set _difference() |
set_difference( _InIt _SrcBegin1, | 计算两个有序序列的集合差,(集合差:所有存在于第一个集合,但是不存在与第二个集合中的所有元素),然后将求集合差的结果存入第四个参数指定的Dest序列中,注意在计算前必须给Dest容器分配足够的空间,因为Dest范围最大是两个_Src范围的size的最大值,所以在进行取交集后有可能会留下一些空间,set_union算法返回一个引用Dest范围中最后一个被添加进去的元素的后一个位置的iterator,利用它可以将Dest中多余的空间删除 |
返回一个引用Dest范围中最后一个被添加进去的元素的后一个位置的_OutputIterator
|
std:: set_symmetric _difference() | set_symmetric _difference( _InIt _SrcBegin1, | 计算两个有序序列的对称集合差,(对称集合差:所有存在于某一个集合,但是不存在与第二个集合中的元素),然后将求对称集合差的结果存入第四个参数指定的Dest序列中,注意在计算前必须给Dest容器分配足够的空间,因为Dest范围最大是_Src1和_Src2的size()和,所以在进行取交集后有可能会留下一些空间,set_union算法返回一个引用Dest范围中最后一个被添加进去的元素的后一个位置的iterator,利用它可以将Dest中多余的空间删除 |
返回一个引用Dest范围中最后一个被添加进去的元素的后一个位置的_OutputIterator |
Warning: 务必要确保Dest范围足够大,足以保存操作的结果. 对于set_union()和set_symmetric_difference(), 结果大小的上限是两个输入范围的总和. 对于set_intersection()和set_difference(), 结果大小的上限是两个输入范围大小中的最大值. |
#include <numeric>
算法 | 常用版本 | 描述 | 返回Type |
std::accumulate() | accumulate(_InIt _First ,_InIt _Last ,_Ty& _Val); | 对一个由两个迭代器指定的序列的元素求和 | 返回一个指定的序列的求和的值 |
- | accumulate(_InIt _First ,_InIt _Last ,Ty& _Val, _Func _CallBack); |
对一个由两个迭代器指定的序列进行 调用者指定的操作 | 返回对一个序列执行指定操作的值 |
std::iota() | iota(_FwdIt _First ,_FwdIt _Last,_Ty& _Val); | 生成一个指定范围内的序列值, 由第三个实参指定的值开始使用 operator++递增,调用此算法之前必须要指定容器的size() | void |
算法复杂度大O表示法
算法复杂度 | 大O表示法 | 说明 | 事例算法 |
常数 | O(1) | 运行时间与输入量无关 | 访问数组中的某个元素 |
对数 | O(log n) | 运行时间是输入量以2为底的对数的函数 | 使用二分法查找有序列表中的元素 |
线性 | O(n) | 运行时间与输入量成正比 | 未排序列表中查找元素 |
线性对数 | O(n log n) | 运行时间是输入量的对数函数的线性倍的函数 | 归并排序 |
二次方 | O(n²) | 运行时间是输入量的平方的函数 | 较慢的排序算法,如选择排序算法 |
乐享：知识积累，快乐无限。
