C++ 算法概览
- beg和end表示元素范围的迭代器
- beg2表示第二个序列开始位置迭代器，end2表示第二个序列末尾迭代器（如果有的话）。如没有end2则假定系列2至少与beg和end表示的范围一样大。beg和beg2类型不必匹配，但必须保证两个序列中的元素可以执行特性操作或调用给定的可调用对象。
- des表示目的序列的迭代器。对于给定输入序列，算法需要生成多少元素，目的序列保证有足够的空间存放算法生成的元素。
- unaryPred和binaryPred是一元和二元谓词，分别接受来自输入序列的元素，两个谓词都返回可用作条件的类型。
- comp是一个二元谓词，满足关联容器中对关键字序的要求
- unaryOp和binaryOp是可调用对象，分别使用来自输入序列的一个和两个实参来调用。
查找对象的算法
这些算法在一个输入序列中搜索一个指定值或者一个值的序列。每个算法都有两个重载的版本，一个使用底层类型的==来比较；另一个使用用户给定的unaryPred和binaryPred比较。
1. 简单查找算法
find(beg, end, val); // 返回迭代器，指向第一个等于val的元素。未找到，返回end
find_if(beg, end, unaryPred); // 返回迭代器，指向第一个满足unaryPred的元素。未找到，end
find_if_not(beg, end, unaryPred); // 指向第一个不满足unaryPred的元素, 未找到，返回end
count(beg, end, val); // 返回一个计数器，指出val出现了多少次
count_if(beg, end, unaryPred); // 统计有多少个元素满足unaryPred
all_of(beg, end, unaryPred);
any_of(beg, end, unaryPred);
none_of(beg, end, unaryPred);
// 上面几个都返回bool值，分别判断是否所有元素满足unaryPred、任一元素满足unaryPred、所有元素都不满足unaryPred。
// 如序列为空，any_of返回false，all_of和none_of返回true
2. 查找重复值算法
下面算法要求前向迭代器，因为有binaryPred了，需要前后两个元素比较，要多遍扫描。
// 返回指向第一对相邻重复元素的迭代器。如不存在，返回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)
3. 查找子序列算法
除了find_first_of之外，都要求两个前向迭代器；find_first_of第一个只需要输入迭代器，第二个序列需要前向迭代器，因为需要支持多次扫描。
// 返回第二个序列在第一个序列中第一次出现的位置。如未找到，返回end1
search(beg1, end1, beg2, end2)
search(beg1, end1, beg2, end2, binaryPred)
// 返回第一个序列中迭代器，指向序列二中任意一个元素在序列一中首次出现的位置。如未找到，则返回end1
find_first_of(beg1, end1, beg2, end2)
find_first_of(beg1, end1, beg2, end2, binaryPred)
// 类似search，返回最后一次出现的位置。如未找到则返回end1
find_end(beg1, end1, beg2, end2)
find_end(beg1, end1, beg2, end2, binaryPred)
其他只读算法
要求前两个实参都是输入迭代器，同样提供两个版本，一个用底层类型的==，一个用用户指定的unaryPred或binaryPred比较元素。
// 对输入序列中的每个元素应用可调用对象unaryOp，忽略返回值。迭代器支持的话则可以修改元素。
for_each(beg, end, unaryOp):
// 比较两个序列中的元素，返回一个pair，表示两个序列中第一个不匹配的元素，若均匹配，则pair的first成员为end1，second成员是指向beg2中偏移量等于第一个序列长度的位置。
mismatch(beg1, end1, beg2)
mismatch(beg1, end1, beg2, binaryPred)
// 确定两个序列是否相等。相等返回true，不相等返回false。
equal(beg1, end1, beg2)
equal(beg1, end1, beg2, binaryPred)
二分搜索算法
- 这些算法要求至少前向迭代器，如果提供随机访问迭代器，性能会好很多。无论什么迭代器都执行对数次比较操作，但是前向迭代器必须花费线性次数的迭代器操作来移动到序列中要比较的元素位置。
- 另外这些算法要求序列已经是有序的，它们的行为类似关联容器中的同名成员。equal_range、lower_bound和upper_bound算法返回迭代器，指向给定序列中的正确插入位置——插入后还能保持有序。如果给定元素比序列中所有元素都大，则返回尾后迭代器。
- 每个算法提供两个版本，一个用元素类型的<来检测，令一个使用给定的比较操作（比如
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返回的迭代器，second成员为upper_bound返回的迭代器
equal_bound(beg, end, val)
equal_bound(beg, end, val, comp)
// 返回一个bool值，指出序列中是否含有指定值val。对于两个值x和y, 当x不小于y且y也不小于x时认为它们相等。
binary_search(beg, end, val)
binary_search(beg, end, val, comp)
写容器元素的算法
1. 只写不读元素的算法
这些算法要求一个输出迭代器，表示目的位置。_n结尾的版本表示第二个参数是写入的元素个数。
// 给输入序列的每个元素赋予一个新值。fill将值赋予元素(对于不可拷贝的类型不能用fill)，generate执行生成器对象Gen()生成新值。
// fill和generate都返回void, _n结尾的版本返回一个迭代器, 指向写入到输出序列的最后一个元素之后的位置
fill(beg, end, val)
fill_n(dest, cnt, val)
generate(beg, end, Gen)
generate_n(dest, cnt, Gen)
2. 使用输入迭代器的写算法
这些算法读取一个输入序列，将值写入到一个输出序列中。它们要求一个名为dest的输出迭代器，而表示输入范围的迭代器必须是输入迭代器。
// 从输入范围将元素拷贝到dest指定的目的序列。copy拷贝所有元素, copy_if拷贝满足unaryPred的元素，_n拷贝前n个，输入序列至少有n个。
copy(beg, end, dest)
copy_if(beg, end, dest, unaryPred)
copy_n(beg, n, dest)
// 对输入序列中的每个元素调用std::move,将其移动到迭代器dest开始的序列，没有if和n的版本
move(beg, end, dest)
// 调用给定操作，将结果写入dest。第一个版本对输入范围中的每个元素应用一元操作，第二个版本对两个输入序列中元素应用二元操作。
transform(beg, end, dest, unaryOp)
transform(beg, end, beg2, dest, binaryOp)
// 将每个元素拷贝到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(beg1, end1, beg2, end2, dest)
merge(beg1, end1, beg2, end2, dest, comp):
3. 使用前向迭代器的写算法
这些算法要求前向迭代器，由于它们是向输入序列写入元素，迭代器必须具有写入元素的权限。
// 交换iter1和iter2所表示的元素，或者将输入范围中所有元素与beg2开始的第二个序列中所有元素进行交换。两个范围不能有重叠。iter_swap返回void，swap_ranges返回递增后的beg2，指向最后一个交换元素之后的位置。
iter_swap(iter1, iter2)
swap_ranges(beg1, end1, beg2):
// 用new_val替换每个匹配元素。第一个版本使用==，第二个版本使用一元谓语unaryPred。
replace(beg, end, old_val, new_val)
replace(beg, end, unaryPred, new_val)
4. 使用双向迭代器的写算法
这些算法需要在序列中有反向移动的能力，因此它们要求双向迭代器。
// 从输入范围中拷贝或移动元素到指定目的位置。与其他算法不同，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)
划分与排序算法
每个排序和划分算法都提供了稳定和不稳定版本。稳定版本保证保持相等元素的相对顺序。由于稳定算法会做更多的工作，可能比不稳定版本慢得多并消耗更多内存。
1. 划分算法
一个划分算法将输入范围中的元素划分为两组。第一组包含那些满足给定谓词的元素，第二组则包含不满足给定谓词的与元素。
// 如果所有满足谓词unaryPred的元素都在不满足unaryPred的元素之前则返回true(序列为空也返回true)，否则返回flase
is_partitioned(beg, end, unaryPred)
// 将满足unaryPred的元素拷贝到dest1，将不满足unaryPred的元素拷贝到dest2。返回一个迭代器pair，其first成员表示拷贝到dest1的元素的末尾，其second表示拷贝到dest2的元素的末尾。输入序列与两个目的序列都不能重叠
partition_copy(beg, end, dest1, dest2, unaryPred)
// 输入序列必须是用unaryPred划分过的。返回满足unaryPred的范围的尾后迭代器。如果返回的迭代器不是end，则它指向的元素及其后的元素必须都不满足unaryPred。
partition_point(beg, end, unaryPred)
// 使用unaryPred划分输入序列，满足unaryPred的元素放在序列开始，不满足unaryPred的元素放在序列尾部,返回一个迭代器，指向最后一个满足unaryPred的元素之后的元素，若所有元素均不满足unaryPred则返回beg。
stable_partition(beg, end, unaryPred)
partition(beg, end, unaryPred)
2. 排序算法
这些算法要求随机访问迭代器。每个排序算法都提供两个重载的版本。一个版本用元素的<运算符来比较元素，另一个版本接受一个额外参数来指定排序关系。partial_sort_copy返回一个指向目的位置的迭代器，其他排序算法都返回void。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-beg=42，则此函数将值最小的42个元素有序放在序列前42个位置。当partial_sort完成后，从beg到mid之间的范围中的元素已经排好序。已排序返回中的元素都不会比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_element后，此迭代器指向的元素恰好是整个序列排好序后此位置上的值。序列中的元素会围绕nth进行划分: nth之前的元素都小于等于它，而之后的元素都大于等于它。
nth_element(beg, nth, end)
nth_element(beg, nth, end, comp)
6 通用重排操作
这些算法重排输入序列中元素的顺序。前两个算法remove和unique会重排序列，使得排在序列第一部分的元素满足某种标准 。它们返回一个迭代器，标记子序列的末尾。其他算法，比如reverse、rotate和random_shuffle都重排整个序列。
这些算法的基本版本都进行“原址”操作，即在输入序列自身内部重排与元素。三个重排算法提供“拷贝”版本，这些_copy版本完成相同的重排工作，但将重排后的元素写入到一个指定目的序列中，而不是改变输入序列。这些算法要求输出迭代器来表示目的序列。
6.1 使用前向迭代器的重排序列
// 从序列中删除元素，采用的办法是用保留的元素覆盖要删除的元素。被删除的是那些==val或者满足unaryPred的元素。算法返回一个迭代器，指向最后一个保留元素的尾后位置。
remove(beg, end, val)
remove_if(beg, end, unaryPred)
remove_copy(beg, end, dest, val)
remove_copy_if(beg, end, dest, unaryPred)
// 重排序列，对于相邻的重复元素，通过覆盖来进行删除，返回一个迭代器，指向不重复元素的尾后位置。
unique(beg, end)
unique(beg, end, binaryPred)
unique_copy(beg, end, dest)
unique_copy(beg, end, dest, binaryPred)
// 围绕mid指向的元素进行元素转动。元素mid成为首元素，随后是mid+1到end之前的元素，再接着是beg到mid之前的元素。返回一个迭代器，指向原来beg位置的元素
rotate(beg, mid, end)
rotate_copy(beg, mid, end, dest)
6.2 使用双向迭代器的重排算法
// 翻转序列中的元素。reverse返回void，reverse_copy返回一个迭代器，指向拷贝到目的序列的元素的尾后位置。
reverse(beg, end)
reverse_copy(beg, end, dest)
6.3 使用随机访问迭代器的重排算法
由于这些算法要随机重排元素，它们要求随机访问迭代器。
// 混洗输入序列中的元素。第二个版本接受一个可调用对象参数，该对象必须接受一个正整数数值，并生成0到此值的包含区间内的一个服从均匀分布的随机整数。shuffle的第三个参数必须满足均匀分布随机数生成器的要求。所有版本都返回void。
random_shuffle(beg, end)
random_shuffle(beg, end, rand)
shuffle(beg, end, Uniform_rand)
7 排列算法
排序算法生成序列的字典序排列。对于一个给定序列，这些算法通过重排它的一个排列来生成字典序中下一个或前一个排列。算法返回一个bool值，指出是否还有下一个或者前一个排列。
这些算法假定序列中的元素都是唯一的，即没有两个元素的值是一样的。另外为了生成排列，必须既向前又向后处理序列，因此算法要求双向迭代器。
// 如果第二个序列的某个排列和第一个序列具有相同数目的元素，且元素都相等，则返回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。否则将序列转为字典序的上一个排序，返回true。
prev_permutation(beg, end)
prev_permutation(beg, end, comp)
8 有序序列的集合算法
集合算法实现了有序序列上的一般集合操作。这些算法与标准库set容器不同，不要与set上的操作相混淆。这些算法提供了普通顺序容器比如vector和list等的类集合行为。
每种算法都有重载版本，第一个使用元素类型的<运算符，第二个使用给定的比较曹组偶。
// 如果第二个序列中的每个元素都包含在输入序列中则返回true(这里使用的是==)，否则返回false。
includes(beg, end, beg2, end2)
includes(beg, end, beg2, end2, comp)
// 对两个序列中的所有元素，创建它们的有序序列，两个序列都包含的元素在输出序列中只出现一次。输出序列保存在dest中。
set_union(beg1, end1, beg2, end2, dest)
set_union(beg1, end1, beg2, end2, dest, comp)
// 对两个输入序列中均包含的元素创建它们的有序序列，输出交集。输出序列保存在dest中。
set_intersection(beg1, end1, beg2, end2, dest)
set_intersection(beg1, end1, beg2, end2, dest, comp)
// 对出现在第一个序列但不出现在第二个序列中的元素创建一个有序序列。
set_difference(beg1, end1, beg2, end2, dest)
set_difference(beg1, end1, beg2, end2, dest, comp)
// 对只出现在一个序列中的元素，创建一个有序序列。
set_symmetric_difference(beg1, end1, beg2, end2, dest)
set_symmetric_difference(beg1, end1, beg2, end2, dest, comp)
9 最大值和最小值
这些算法使用元素的<运算符或者给定的比较操作。第一组算法对值而非序列进行操作，第二组算法接受一个序列，它们要求输入迭代器。
// 返回val1和val2中最小值/最大值，或initializer_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，分别表示最小值和最大值。
minmax(val1, val2)
minmax(val1, val2, comp)
minmax(init_list)
minmax(init_list, comp)
// min_element和max_element返回指向指向输入序列中最小和最大元素的迭代器。minmax_element返回一个pair，其first成员为最小元素，second成员为最大元素。
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)
10 数值算法
数值算法定义在头文件numeric中，这些算法要求输入迭代器，如果算法输出数据，则使用输出迭代器表示目的位置。
// 返回输入序列所有值的和。和的初始值由init指定。返回类型和init的类型相同。第一个版本使用+,第二个版本使用binaryOp。
accumulate(beg, end, init)
accumulate(beg, end, init, binaryOp)
// 返回两个序列的内积（即对应元素的积的和）。和的初始值由init指定，返回类型和init相同。第一个版本使用* +,第二个版本使用binOp1,binOp2。
inner_product(beg1, end1, beg2, init)
inner_product(beg1, end1, beg2, init, binOp1, binOp2)
// 将新序列写入dest，每个新元素的值都等于输入范围中当前位置和之前位置上所有元素之和。第一个版本使用+，第二个版本使用binaryOp。
partial_sum(beg, end, dest)
partial_sum(beg, end, dest, binaryOp)
// 将新序列写入dest，每个新元素(除了首元素)的值都为输入范围中当前位置和前一个位置元素之差。第一个版本使用-，第二个版本使用binaryOp。v
adjacent_difference(beg, end, dest)
adjacent_difference(beg, end, dest, binaryOp)
// 将val赋予首元素，并将递增后的值赋予下一元素，直至结束。val可以是一个字面值常量。
iota(beg, end, val)
网友评论