c++标准库泛型算法(一)

介绍

标准库并未给每个容器定义成员函数来实现各种操作，而定义了一些泛型算法，其实现了一些算法的公共接口。
大部分泛型算法被定义在头文件algorithm中。还在头文件numeric中定义了一些数值相关的泛型算法。
下文简单介绍了标准库中的算法，在下面的描述中：

beg和end表示元素范围的迭代器。
beg2是表示第二个输入序列开始位置的迭代器。end2表示第二个输入序列的末尾位置。若没有end2则假定beg2表示的序列与beg和end表示的序列一样大。beg与beg2的数据类型不必相同，但必须保证对两个序列中的元素都可以执行相同的操作。
dest表示目的序列的迭代器。算法生成多少数据其大小必须保证保存相同的元素。
unaryPred和binaryPred表示一元和二元谓词，分别接受一个和两个参数，都是来自输入序列中的元素，两个谓词都返回可用作条件的类型。
comp是一个二元谓词，满足关联容器中对关键字序的要求。详情可观看谓词。
unaryOp和binaryOp是可调用对象（lambda表达式或bind），可分别使用来自输入序列的一个两个实参来调用。

查找对象的算法

这些算法在一个输入序列中搜索一个指定值或一个值的序列。
每个算法都提供两个重载版本，第一个版本使用底层运算符(==)来比较元素；第二个版本使用用户给定的unaryPred和binaryPred(一元谓词与二元谓词)比较元素。

简单查找

这些算法查找指定值，要求输入迭代器。

//返回一个迭代器，指向输入序列中第一个等于val的元素，在未找到时返回end。
find(beg, end, val)
//返回一个迭代器，指向输入序列中第一个满足unaryPred的元素，在未找到时返回end。
find_if(beg, end, unaryPred)
//返回一个迭代器，指向输入序列中第一个令unaryPred为false的元素，在未找到时返回end。
find_if_not(beg, end, unaryPred)
//返回一个计数器，指出val出现多少次。
count(beg, end, val)
//返回一个计数器，统计多少元素满足unaryPred。
count_if(beg, end, unaryPred)
//返回一个bool值，指出unaryPred是否对所有元素都成功，若序列为空返回true。
all_of(beg, end, unaryPred)
//返回一个bool值，指出unaryPred是否对任意元素成功，若序列为空返回false。
any_of(beg, end, unaryPred)
//返回一个bool值，指出unaryPred是否对所有元素都不成功，若序列为空返回true。
none_of(beg, end, unaryPred)

查找重复值

以下算法要求正向迭代器，在输入序列中查找重复元素。

//返回指向第一对相邻重复元素的迭代器。若序列中不存在，则返回end。
adjacent_find(beg, end)
adjacent_find(beg, end, binaryPred)
//返回一个迭代器，从此位置开始有count个相等元素，若不存在这样的子序列反回end。
search_n(beg, end, count, val)
search_n(beg, end, count, val, binaryPred)

查找子序列算法

以下算法中除了find_fist_of用输入迭代器表第一序列，正向迭代器表第二个序列之外都要求两个正向迭代器。

//返回第二个子序列在第一个序列中出现的位置。若不存在返回end1。
search(beg1, end1, beg2, end2)
search(beg1, end1, beg2, end2, binaryPred)
//返回一个迭代器，指向第二个输入范围中任意元素在第一个序列中首次出现的位置。若未找到匹配元素返回end1。
find_fist_of(beg1, end1, beg2, end2)
find_fist_of(beg1, end1, beg2, end2, binaryPred)
//类似search，但返回最后一个出现的位置。若序列2为空或未找到返回end1。
find_end(beg1, end1, beg2, end2)
find_end(beg1, end1, beg2, end2, binaryPred)

其他只读算法

以下算法要求输入迭代器

//对序列中每个元素应用unaryPred，unaryPred返回值被忽略。若迭代器允许通过解引用向序列中写入，则可能修改元素。
for_each(beg, end, unaryPred)
//比较两个序列中的元素，返回一个迭代器的pair，表示两个序列中第一个不匹配的元素
//若都匹配，则返回的oair中第一个迭代器为end1，第二个指向beg2中偏移量等于第一个序列长度的位置
mismatch(beg1, end1, beg2)
mismatch(beg1, end1, beg2, binaryPred)
//确定两个序列是否相等。若序列1中每个元素都与序列2顺序的元素相等，返回true。
equal(beg1, end1, beg2)
equal(beg1, end1, beg2, binaryPred)

二分搜索算法

这些算法都要求正向迭代器，但也可以提供随机访问迭代器会使其性能更好。
这些算法要求序列元素是有序的。默认使用”<”来检测或comp(x, y)成功。

//返回一个迭代器，表第一个小于等于val的元素，若不存在返回end。
lower_bound(beg, end, val)
lower_bound(beg, end, val, comp)
//返回一个迭代器，表第一个大于等于val的元素，若不存在返回end。
upper_bound(beg, end, val)
upper_bound(beg, end, val, comp)
//返回一个pair，其first表lower_bound返回的迭代器，sencond表upper_bound返回的迭代器
equal_range(beg, end, val)
equal_range(beg, end, val, comp)
//返回一个bool，指出序列中是否包含等于val的元素。不大于也不小于认为其相等。
binary_search(beg, end, val)
binary_search(beg, end, val, comp)

写容器算法

许多算法向给定序列中的元素写入新值。这些算法可以通过表示输入序列的迭代器类型来区分；或通过写入输入序列中的元素还是写入给定的位置来区分。

只写不读

这些算法要求一个输入迭代器，表目的位置。_n结尾的版本接受第二个实参表写入的元素数目，并将给定数目的元素写入到目的位置中。

//给输入序列中每个元素赋一个新值。fill将val赋予元素；generate执行生成器对象Gen()生成新值。生成器是一个可调用对象。
//fill和generate都返回void。_n版本返回一个迭代器，指向写入到序列的最后一个元素之后的位置。
fill(beg, end, val)
fill(dest, cnt, val)
generate(beg, end, Gen)
generate(dest, cnt, Gen)

使用输入迭代器的写算法

这些算法读取一个输入序列，将值写入到一个输出序列中。其要求一个名为dest的输出迭代器，表输入范围的迭代器必须是输入迭代器。

//从输入范围将元素拷贝到dest指定的序列中。
//copy拷贝所有元素，copy_if拷贝满足unaryPred的元素，copy_n拷贝前n个元素。输入序列至少有n个元素。
copy(deg, end, dest)
copy(deg, end, dest, unaryPred)
copy(deg, n, dest)
//对输入序列中每个元素调用std::move，将其移动到迭代器dest开始的序列中。
move(deg, end, dest)
//调用给定操作，并将结果写入dest中。
//第一个版本对每个元素应用一元操作，第二个版本对两个输入序列中的元素应用二元操作。
transform(deg, end, dest, unaryOp)
transform(deg, end, deg2, dest, unaryOp)
//将每个元素拷贝到dest，将指定元素替换为new_val。
//第一个版本替换那些==old_val的元素，第二个版本替换满足unaryPred的元素。
replace_copy(beg, end, dest, old_val, new_val)
replace_copy_if(beg, end, dest, unaryPred, new_val)
//两个序列都是有序的。将合并的序列写入dest。
//第一个版本用"<"运算符比较元素，第二个版本使用给定比较操作。
merge(deg1, end1, beg2, end2, dest)
merge(deg1, end1, beg2, end2, dest, comp)

使用正向迭代器的写算法

这些算法要求正向迭代器，由于它们要向序列中写入元素，迭代器必须有写入元素的权限。

//交换iter1和iter2所表达的元素，或将输入范围中所有元素与beg2开始的第二个序列中所有元素进行交换。两个范围不能重叠。
//iter_swap返回void。swap_ranger返回递增后的beg2，指向最后一个交换元素的位置
iter_swap(iter1, iter2)
swap_ranges(beg1, end1, beg2)
//用new_val替换每个匹配元素。第一个版本使用"=="比较元素与old_val，第二个版本替换满足unaryPred的元素。
replace(beg, end, old_val, new_val)
replace_if(beg, end, unaryPred, new_val)

使用双向迭代器的写算法

这些算法需要在序列中有反向移动的能力，以此其要求双向迭代器。

//从输入范围中拷贝或移动元素到指定位置。与其他算法不同，dest是输入序列的尾后迭代器。
//输入范围中的尾元素被拷贝或移动到目的序列的尾元素，然后是倒数第二个，以此类推。
//元素在目的序列中的顺序与输入序列相同。若范围为空。则返回dest，否返回值表示从*beg中拷贝或移动的元素。
copy_backward(beg, end, dest)
move_backward(beg, end, dest)
//将同一个序列中的两个有序子序列合并为单一的有序序列。beg到mid间的子序列和mid到end间的子序列被合并。
//将合并后的结果写入到原序列中。第一个版本使用"<"比较元素，第二个版本使用给定的操作，返回void
inplace_merge(beg, mid, end)
inplace_merge(beg, mid, end, comp)

参考资料

C++primer中文版(第五版) 电子工业出版社。