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

划分与排序算法

对于序列中的元素进行排序，排序和划分算法提供了多种策略。
每个排序和划分算法都提供稳定和不稳定版本。稳定算法保证保持相等元素的相对顺序。由于稳定算法会做更多的工作，可能比不稳定版本慢得多，并消耗更多内存。

划分算法

一个划分算法将输入范围中的元素分为两组。第一组包含满足给定谓词的元素，第二组包含不满足谓词的元素。这些算法都要求双向迭代器。

//若所有满足unaryPred的元素都在不满足unaryPred的元素之前，则返回true，若序列为空也返回true。
is_partitioned(beg, end, unaryPred)
//将满足unaryPred的元素拷贝到dest1，不满足的拷贝到dest2。
//返回一个迭代器pair，其first表示拷贝到dest1的元素的末尾，second表拷贝到dest2的元素的末尾。
//输入序列与两个目的序列都不能重叠。
partition_copy(beg, end, dest1, dest2, unaryPred)
//输入序列是已经用unaryPred划分过的。返回满足unaryPred的范围的尾后迭代器。
//若返回的迭代器不是end，则其之后的元素都不满足unaryPred。
partition_point(beg, end,  unaryPred)
//stable为稳定版本，使用unaryPred划分输入序列。满足unaryPred的元素放置在序列开始，不满足的元素放在序列尾部。
//返回一个迭代器，指向最后满足unaryPred的元素之后的位置，若都不满足unaryPred，则返回beg。
stable_partition(beg, end, unaryPred)
partition(beg, end, unaryPred)

排序算法

这些算法要求随机访问迭代器。每个都提供两个重载的版本。一个用”<”来比较，另一个版本接受一个额外参数来指定排序关系。
partial_sort和nth_element算法都只进行部分重排工作，其效率比重排整个序列要高。

//重排整个范围。
sort(beg, end)
stable_sort(beg, end)
sort(beg, end, comp)
stable_sort(beg, end, comp)
//返回一个bool，指出序列是否有序。
is_sorted(beg, end)
is_sorted(beg, end, comp)
//在输入序列中查找最长初始有序子序列，并返回子序列的尾后迭代器。
is_sorted_until(beg, end)
is_sorted_until(beg, end, comp)
//排序mid-beg个元素，已排序范围中的元素都不会比mid后的元素更大。未排序区域中的元素的顺序未指定。
partial_sort(beg, mid, end)
partial_sort(beg, mid, end, comp)
//排序输入范围中的元素，并将足够多的已排序元素放到destBeg和destEnd所指示的序列中。
//如果目的范围的大小大于等于输入范围，则排序好的元素存入destBeg开始的范围。
//若小于输入范围，则只拷贝目的范围一样多的元素。
//返回一个迭代器，指向目的范围中已排序部分的尾后迭代器，如果目的序列小于输入序列，则返回destEnd。
partial_sort_copy(beg, end, destBeg, destEnd)
partial_sort_copy(beg, end, destBeg, destEnd, comp)
//nth必须是一个迭代器，指向输入序列中的一个元素。
//序列中的元素会围绕nth进行划分，之前的元素都小于它，之后的元素都大于它
nth_element(beg, nth, end)
nth_element(beg, nth, end, comp)

通用重排操作

这些算法重排输入序列中元素的顺序。remove与unique会重排序列，使得排在序列第一部分的元素满足某种标准，它们返回一个迭代器，标记子序列的末尾。
而其他的一些算法会重排整个输入序列。

使用正向迭代器的重排算法

这些重排算法要求其迭代器是正向迭代器。

//从序列中删除元素，采用的方式是用保留的元素覆盖要删除的元素，删除"=="val或满足unaryPred的元素。
//返回一个迭代器，指向最后一个删除元素的尾后迭代器。
remove(beg, end, val)
remove_if(beg, end, unaryPred)
remove_copy(beg, end, dest, val)
remove(beg, end, dest, unaryPred)
//重排序列，对相邻的重复元素，通过覆盖它们进行删除。返回一个迭代器，指向不重复元素的尾后位置。
//第一个版本使用"=="来确定两元素是否相同，第二个使用谓词。
unique(beg, end)
unique(beg, end, binaryPred)
unique_copy(beg, end, dest)
unique_copy_if(beg, end, dest, binaryPred)
//围绕mid指向的元素进行转动。mid成为首元素，之后是mid+1直到end之前的元素，再从beg到mid之前的元素。
//返回一个迭代器，指向原来beg的位置。
rotate(beg, mid, end)
rotate_copy(beg, mid, end, dest)

使用双向迭代器的重排算法

这些算法要反向处理数据，因此需要双向迭代器。

1
2
3

//翻转序列中的元素。revese返回void，revese_copy返回一个迭代器，指向拷贝到目的序列的尾后位置。
reverse(beg, end)
reverse(beg, end, dest)

使用随机访问迭代器的重排算法

以下算法使用随机重排元素，所以要求随机迭代器。

//混洗输入序列中的元素。
//第二个版本接受一个可调用对象参数，该对象接受一个正整数，
//并生成0到此值的包含区间内的一个服从均匀分布的随机整数。
//shuddle第三个参数须满足均匀分布随机数的要求。所有版本都返回void。
random_shuffle(beg, end)
random_shuffle(beg, end, rand)
shuffle(beg, end, Unifom_rand)

排列算法

排列算法生成序列的字典排序。这些算法假定序列中的元素是唯一的。
为了生成排列，须使用双向迭代器。

//如果第二个序列的某个排列和第一个序列具有相同数目的元素，且元素都相等，则返回true。
//第一个版本用"=="比较元素，第二个版本使用给定的binaryPred。
is_permutation(beg1, end1, beg2)
is_permutation(beg1, end1, beg2, binaryPred)
//如果序列已经是最后一个排列，则将序列重排为最小的排列，并返回false。
//否则，它将输入序列转换为字典序中的下个排序，并返回true。
//第一个版本使用"<"比较元素，第二个版本使用给定的比较操作。
next_permutation(beg, end)
next_permutation(beg, end, comp)
//与上个方法类似，但将序列转换为一个前一个排列。若已是最小排列，则将其重排为最大排列，并返回false。
prev_permutation(beg, end)
prev_permutation(beg, end, comp)

有序序列的集合算法

这些算法实现了有序序列上的一般集合操作。这些算法与标准库set容器不同。这些算法提供了普通顺序容器(vector,list等)或其他序列(输入流等)上的类集合行为。
这些算法顺序处理元素，因此要求输入迭代器。他们还接受一个表示目的序列的输出迭代器，唯一例外是includes。这些算法返回递增后的dest迭代器，表示写入dest的最后一个元素之后的位置。
每种算法都有重载版本，第一个使用”<”，第二个使用给定的比较操作。

//如果第二个序列中的每个元素都包含在输入序列中，则返回true，否则返回false。
includes(beg, end, beg2, end2)
includes(beg, end, beg2, end2, comp)
//对两个序列中所有元素，创建它们的有序序列。两个序列都包含的元素在输出序列中只出现一次。输出序列保存在dest中。
set_union(beg, end, beg2, end2, dest)
set_union(beg, end, beg2, end2, dest, comp)
//对两个序列都包含的元素创建一个有序序列。结果保存在dest中。
set_intersection(beg, end, beg2, end2, dest)
set_intersection(beg, end, beg2, end2, dest, comp)
//对出现在第一个序列但不在第二个序列中的元素，创建一个有序序列。
set_difference(beg, end, beg2, end2, dest)
set_difference(beg, end, beg2, end2, dest, comp)
//对只出现在一个序列中的元素，创建一个有序序列。
set_symmetric_difference(beg, end, beg2, end2, dest)
set_symmetric_difference(beg, end, beg2, end2, dest, comp)

最小值和最大值

这些算法使用”<”或给定的比较操作。第一组算法对值而非序列进行操作。第二组算法接受一个序列。
要求输入迭代器。

//返回val1、val2中最小/大值，或init_list中的最小/大值。
//两个参数类型须一致。参数返回类型都是const的引用，意味着对象不会被拷贝。
min(val1, val2)
min(val1, val2, comp)
min(init_list)
min(init_list, comp)
max(val1, val2)
max(val1, val2, comp)
max(init_list)
max(init_list, comp)
//返回一个pair，其first成员为提供值中的较小值，second成员为较大值。
//initializer_list版本返回一个pair，其first成员为list中的最小值，second成员为最大值。
minmax(val1, val2)
minmax(val1, val2, comp)
minmax(init_list)
minmax(init_list, comp)
//分别返回序列中的最大值/最小值和表两个最值的pair。
min_element(beg, end)
min_element(beg, end, comp)
max_element(beg, end)
max_element(beg, end, comp)
minmax_element(beg, end)
minmax_element(beg, end, comp)

字典序比较

此算法比较两个序列，根据第一对不相等的元素的相对大小来返回结果。算法使用”<”或给定的比较操作。两个序列都要求输入迭代器。

//若第一个序列·在字典序中小于第二个序列，则返回true，若否返回false。
//若一个序列相较另一序列短，且所有对应元素相等，较短的序列字典序更小。
lexicographical_compare(beg1, end1, beg2, end2)
lexicographical_compare(beg1, end1, beg2, end2, comp)

数值算法

这些算法都定义在头文件numeric中。要求输入迭代器；若算法输出数据，则使用输出迭代器表示目的位置。

//返回输入序列中所有元素之和，和的初值由init指定，init须与序列元素的类型相同。
//默认使用"+",可以使用指定处理方式。
accumulate(beg, end, init)
accumulate(beg, end, init, binaryOp)
//返回两个输入序列的乘积之和，init指出初始和的值。
//默认使用"*"和"+"，可以使用binOp1与binOp2代替
inner_product(beg1, end1, beg2, end2 ,init)
inner_product(beg1, end1, beg2, end2 ,init, binOp1, binOp2)
//将新序列写入到dest中，每个新元素的值都等于输入范围中当前位置和之前位置上所有元素之和。
//默认使用"+",可以使用指定处理方式。
partial_sum(beg, end, dest)
partial_sum(beg, end, dest, binaryOp)
//将新序列写入dest，除了首元素之外，每个新元素的值都等于输入范围中当前位置和前一个位置之差。
//默认使用"-",可以使用指定处理方式。
adjacent_difference(beg, end, dest)
adjacent_difference(beg, end, dest, binaryOp)
//将val赋予首元素，递增val并赋予下个元素，依次递推。
iota(beg, end, val)

参考资料

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