STL常用算法

#include

算法 std::find() 常用版本 find(_InIt _Fisrt,_InIt _Last, _Ty& _Val); std::find_if() find_if(_InIt _Fisrt,_InIt _Last, _CallBack); 描述 从两个迭代器指定的范围中查找指定值 返回Type 引用被查找的值的iterator或end() 从两个迭代器指定的范围中查找与回调谓词匹配的与谓词匹配的实例的iterator实例 std::find_if_not() find_if_not(_InIt _Fisrt,_InIt _Last,_Func _CallBack); std::count() count(_InIt _First,_InIt _Last, _Ty& _Val); std::count_if() std::generate() std::max() count_if(_InIt _First,_InIt _Last, _CallBack); generate(_FwdIt _First,_FwdIt _Last, _CallBack); max(_Left,_Right /*,Predicate*/); 从迭代器范围中返回第一个不符合谓词的元素 或end() 第一个不符合谓词的元素的iterator或end() 求得一个元素序列中与第三个参数相符的元素的个与第三个参数匹配的元素的int数 求得一个序列中与谓词匹配的元素的个数 通过特定值填充一个迭代器范围 个数 符合条件元素的int个数 void 通过operator<或用户提供的二元谓词比较任意返回较大的一个元素的const引类型的两个元素 用 较小的一个元素的const引用 std::min() min(_Left,_Right /*,Predicate*/); 通过operator<或用户提供的二元谓词比较任意类型的两个元素 std::max_element() max_element(_FwdIt _First,_FwdIt _Last /*,_Pred*/); 从一组任意类型的元素元素序列中查找\"最大\"的一个 std::min_element() min_element(_FwdIt _First,_FwdIt _Last /*,_Pred*/); 从一组任意类型的元素元素序列中查找\"最小\"的一个 adjacent_find() adjacent_find(_FwdIt _First, _FwdIt _Last/*,_Pred*/); 从一组任意类型的元素序列中查找有重复的元素 引用\"最大”的元素的iterator 引用\"最小\"的元素的iterator 引用重复的第一个元素的iterator或者end() 1

STL常用算法

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() std::transform() for_each(_InIt _First,_InIt _Last,_CallBack); transform(_InIt_SrcFirst,_InIt _SrcLast,_OutIt_DestBegin, _CallBack); 对指定范围内的所有元素执行一次_CallBack 对指定范围的元素执行回调后生成新的元素,然后将这些新元素保存在第三个参数指定的目标范围中 _CallBackl类型 引用Dest范围的past-the-end的_OutputIterator - transform(_InIt _First1,_InIt _Last,_InIt _First2,_OutIt _DestBegin,_CallBack); 对两个指定序列的元素调用二元谓词,并将结果存入到第四个参数指定的容器中 引用Dest范围的past-the-end的_OutputIterator std::equal() 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 将Src范围的元素反向复制到Dest范围中,也就_DestEnd); 是从Src范围最后一个元素开始复制,将这个元素引用Dest范围的_Begin()的_OutputIterator 2

STL常用算法

放在Dest范围的最后一个位置,然后再每一次复制后反向移动.第三个参数应该是_DestEnd而不是_DestBegin std::copy_if copy_if(_InIt _SrcBegin,_InIt _SrcEnd,_OutIt _DestBegin, _Pr _Pred); 对一个序列中每个准备复制的元素执行一次_Callback,如果返回值为true,那么执行copy制的元素的后一个位置,这是为了配合past_the_end来删除多余的元素:复制完成后使用_Dest.erase(_CopyEndIt,past_the_end);来删除Dest范围多余的元素位置 std::copy_n() copy_n(_InIt _SrcBegin,_Ty _Cnt,_OutIt _DestBegin); 从Src范围复制_Cnt个元素到Dest范围,第二个参数是一个指定要复制的元素个数的整数 _Dest1,_OutIt _Dest2,_Pr _Pred); 对一个序列的元素进行依据谓词返回的结果进行划分复制,首先对Src序列中的每一个元素执行一次谓词,如果返回true,那么将这个元素复制到前需要使用resize()重置Dest的空间;算法返回一个打包_Dest1和_Dest2的one_past_the_last_copied的std::pair,利用这个pair可以删除多分配的空间 std::move() move(_InIt _SrcBegin,_InIt _SrcEnd,_OutIt _DestBegin); 需要给元素提供移动赋值运算符,将Src序列的元素通过移动赋值运算符移动到Dest序列,在移动操作中,SrcObject被重置了,因为DstObject接管了SrcObject资源的所有权, 返回Dest范围的引用past_the_end的_OutputIterator 返回引用Dest范围的past_the_end 打包引用_Dest1和_Dest2的的_OutputIterator的std::pair 复制的元素的后一个位置的_OutputIterator 操作,否则不执行;返回了Dest范围中最后一个复返回引用Dest范围的最后一个std::partition_copy() partition_copy(_InIt _SrcBegin,_InIt _SrcEnd,_OutIt _Dest1,如果返回false,复制到_Dest2,复制之one_past_the_last_copied 3

STL常用算法

这意味着在move操作过后Src序列中的对象不能再使用 Std::move_backward() move_backward(_InIt _SrcBegin, _InIt _SrcEnd,_OutIt _DstEnd) std::replace() replace(_FwdIt _First,_FwdIt _Last,const _Ty& _OldVal,const _Ty& _NewVal); std::replace_if() 使用了和std::move()相同的移动机制,但是按返回Dest范围的引用_Begin()照从最后一个元素向第一个元素的顺序进行移动 这个算法将一个范围中的匹配某个值的元素替换为第三个参数指定的新值 void 的_OutputIterator void replace_if(_FwdIt _First,_FwdIt _Last,_Pr _Pred, 这个算法将一个范围中的匹配某个谓词的元素替换const _Ty& _NewVal); 为第三个参数指定的新值 这个算法并不是将序列中与_Val匹配的元素直接用第一个被移除的元素的iterator,可以利用这个iterator和end()将被移除的元素彻底擦除 std::remove() 返回引用第一个被移除的元素的_FwdIterator remove(_FwdIt _First,_FwdIt _Last,const _Ty& _Val); 删除,而是将它们移动到容器的末端,然后返回引 std::remove_if() remove_if(_FwdIt _First,_FwdIt _Last,_Pr _Pred); 这个算法并不是将序列中与谓词匹配的元素直接删除,而是将它们移动到容器的末端,然后返回引用第一个被移除的元素的iterator,可以利用这个iterator和end()将被移除的元素彻底擦除 返回引用第一个被移除的元素的_FwdIterator std::unique() std::unique算法是特殊的std::remove算法,和后者一样,std::unique并不是直接将重复然后返回引用第一个被移除的元素的iterator,可以利用这个iterator和end()将被移除的元素彻底擦除 返回引用第一个被移除的元素的_FwdIterator unique(_FwdIt _First,_FwdIt _Last /*,_Pr _Pred)*/; 的元素删除,而是将它们全部移动到容器的尾端,std::unique_copy unique(_FwdIt _SrcBegin,_FwdIt _SrcEnd,_OutIt _DestBegin /*,_Pr _Pred*/); std::unique()的基本形式是就地操作数据,std::unique_copy则是将操作的结果复制返回引用Dest范围的元素的_OutputIterator 4

STL常用算法

到Dest范围中 std::reverse() reverse(_BidIt _First,_BidIt _Last); 将范围中的第一个元素和最后一个元素交换,第二个元素和倒数第二个元素交换,依此类推 std::reverse_copy() reverse_copy(_BidIt _SrcBegin,_BidIt _SrcEnd, _OutIt _DestBegin); std::reverse是就地操作数据,std::reverse_copy将结果复制到Dest范围中 std::sort() sort(_RanIt _First,_RanIt _Last /*,_Pr _Pred*/); 将范围中的元素按operator<或_CallBack进行排序 std::merge() merge(_InIt _SrcBegin1,_InIt _SrcEnd1,_InIt _SrcBegin2,_InIt _SrcEnd2,_OutIt _DestBegin, /*,_Pr _Prd*/); 将两个排好序的Src序列合并成一个元素序列,然后将结果复制到Dest序列中,并且依然保持排序的顺序,结果是一个包含两个Src序列的所有元素的有序序列,注意一定要使用两个排好序的序列进行merge操作 std::is_sorted() sort(_FwdIt _First,_FwdIt _Last /*,_Pr _Pred*/); 验证一个序列是否是有序序列.如果是,返回true,否则返回false _Func*/ 将一个序列的顺序打乱,这个算法适用于洗牌之类函数,第二个版本需要提供一个随机数生成器, 以适应不同问题领域的随机性

void bool 引用Dest序列的past_the_end的_OutputIterator Void 返回引用Dest范围的元素的_OutputIterator Void std:random_shuffle() random_shuffle(_RanIt _First,_RanIt _Last /*,_Fn& 的任务,对一个版本默认使用标准C库的rand() 5

STL常用算法

集合算法

std::includes() includes(_InIt _First1,_InIt _Last1,_InIt _First2,_InIt _Last2 /*,_Pr _Pred*/); std::set_union() set_union(_InIt _SrcBegin1, _InIt _SrcEnd1, _InIt _SrcBegin2, _InIt _SrcEnd2, _OutIt _DestBegin /*,_Pr _Pred*/); 验证第二个序列是否是第一个序列的子集,注意不是真子集,而是子集,如果是返回true,否则返回false 计算两个有序序列的并集,然后将并集的结果存入第四个参 数指定的Dest序列中,注意在计算前必须给Dest容器分配返回一个引用Dest范围中足够的空间,因为Dest范围最大是_Src1和_Src2的size()和,所以在进行合并后有可能会留下一些空间,set_union算法返回一个引用Dest范围中最后一个被添加进去的元素的后一个位置的iterator,利用它可以将Dest中多余的空间删除 计算两个有序序列的交集,然后将交集的结果存入第四个参 数指定的Dest序列中,注意在计算前必须给Dest容器分配返回一个引用Dest范围中足够的空间,因为Dest范围最大是两个_Src范围的size最后一个被添加进去的元素的最大值,所以在进行取交集后有可能会留下一些空间,set_union算法返回一个引用Dest范围中最后一个被添加进去的元素的后一个位置的iterator,利用它可以将Dest中多余的空间删除 计算两个有序序列的集合差,(集合差:所有存在于第一个集 合,但是不存在与第二个集合中的所有元素),然后将求集合返回一个引用Dest范围中差的结果存入第四个参数指定的Dest序列中,注意在计算前必须给Dest容器分配足够的空间,因为Dest范围最大是两个_Src范围的size的最大值,所以在进行取交集后有可最后一个被添加进去的元素的后一个位置的_OutputIterator 的后一个位置的_OutputIterator 最后一个被添加进去的元素的后一个位置的_OutputIterator bool std::set_intersection() set_intersection( _InIt _SrcBegin1, _InIt _SrcEnd1, _InIt _SrcBegin2, _InIt _SrcEnd2, _OutIt _DestBegin /*,_Pr _Pred*/); std ::set_difference() set_difference( _InIt _SrcBegin1, _InIt _SrcEnd1, _InIt _SrcBegin2, 6

STL常用算法

_InIt _SrcEnd2, _OutIt _DestBegin /*,_Pr _Pred*/); std::set_symmetric_difference() set_symmetric_difference( _InIt _SrcBegin1, _InIt _SrcEnd1, _InIt _SrcBegin2, _InIt _SrcEnd2, _OutIt _DestBegin /*,_Pr _Pred*/); 能会留下一些空间,set_union算法返回一个引用Dest范围中最后一个被添加进去的元素的后一个位置的iterator,利用它可以将Dest中多余的空间删除 计算两个有序序列的对称集合差,(对称集合差:所有存在于某一个集合,但是不存在与第二个集合中的元素),然后将求对称集合差的结果存入第四个参数指定的Dest序列中,注围最大是_Src1和_Src2的size()和,所以在进行取交集后有可能会留下一些空间,set_union算法返回一个引用Dest范围中最后一个被添加进去的元素的后一个位置的iterator,利用它可以将Dest中多余的空间删除 返回一个引用Dest范围中的后一个位置的_OutputIterator 意在计算前必须给Dest容器分配足够的空间,因为Dest范最后一个被添加进去的元素

Warning: 务必要确保Dest范围足够大,足以保存操作的结果.

对于set_union()和set_symmetric_difference(),结果大小的上限是两个输入范围的总和. 对于set_intersection()和set_difference(),结果大小的上限是两个输入范围大小中的最大值.

7

STL常用算法

#include

算法 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 对一个由两个迭代器指定的序列进行调用者指定的操作 描述 对一个由两个迭代器指定的序列的元素求和 返回Type 返回一个指定的序列的求和的值 返回对一个序列执行指定操作的值

8

STL常用算法

算法复杂度大O表示法 算法复杂度 常数 对数 线性 线性对数 二次方 大O表示法 O(1) O(log n) O(n) O(n log n) O(n²) 说明 运行时间与输入量无关 运行时间是输入量以2为底的对数的函数 运行时间与输入量成正比 运行时间是输入量的对数函数的线性倍的函数 运行时间是输入量的平方的函数 事例算法 访问数组中的某个元素 使用二分法查找有序列表中的元素 未排序列表中查找元素 归并排序 较慢的排序算法,如选择排序算法 9