|
《Thinking in C++> STL算法总结笔记。
STL算法目录
0.算法总览
fill(),为[first, last)每个元素赋值value。fill_n()，由first开始的n个元素赋值value。generate()，用发生器为[first, last)的每个元素生成一个值。generate_n()为first开始的n个元素生成一个值。count()，范围内等于value的个数。count_if()，范围内是判定函数为真的个数。copy()，从[first, last)复制序列到destination。copy_backward()，反向复制元素。reverse()，倒置源序列reverse_copy()，源序列不变，导致结果复制到destination。swap_ranges()，交换相等大小两个范围的内容rotate()，把[first, middle)范围元素移到序列末尾，[middle, last)移到序列开始。rotate_copy()，不改变原始序列，轮换结果复制到destination。next_permutation(),后继排列prev_permutation()，前驱排列random_shuffle()，重新排列元素（混洗）partition()，将满足判定函数的元素移动到序列开头。stable_partition()，稳定划分，保持相对位置不变find()，查找value第一次出现的位置find_if()，查找使判定函数为真的元素。adjacent_find()查找两个邻近的相等元素。find_first_of()，在第二个范围内查找与第一个范围内的某个元素相等的元素。search()，查找第二个序列第一次出现在第一个序列的位置。find_end()，查找第二个序列最后一次出现在第一个序列的位置。search_n()，在范围内查找一组共count个连续的值。min_element()，最小值首次出现的位置。max_element()，最大值首次出现的位置。replace()，旧值替换为新值。replace_if()，使判定函数为真的值替换为新值。replace_copy()，不修改原始序列，替换旧值放入result。replace_copy_if()，不修改原始序列，替换使判定函数为真的值放入result。equal()，判断两个范围内元素是否完全相同。lexicographical_compare()，第一个范围是否“字典序小于”第二个范围。mismatch()，两个范围不匹配的位置。remove()，删除等于value的元素。remove_if()，删除使判定函数为真的元素。remove_copy()，不改变源序列。remove_copy_if()，不改变源序列。unique()，删除相邻的相等值（副本）。unique_copy()，不改变源序列。sort()，升序排序。stable_sort()，稳定升序排序。partital_sort()，对一定元素进行排序，使其有序放入[first, middle)中。partital_sort_copy()，不改变源序列。nth_element()，使[first, nth]内所有元素都满足二元判定函数。binary_search()，告诉value是否出现在有序序列中。lower_bound()，value第一次出现的位置。upper_bound()，超越value最后出现的位置。equal_range()，value第一次和超越最后一次出现的位置。merge()，升序合并序列。inplace_merge()，升序合并同一序列的两个范围。includes()，判断第二个范围是否是第一个范围子集。set_union()，并集。set_intersection()，交集。set_difference()，差。set_symmetric_difference()，对称差。make_heap()，建堆。push_heap()，向[first, last-1)堆中增加元素*（last-1）并放入合适位置。pop_heap()，将最大元素*first放入位置(last-1)并调整堆。sort_heap()，堆排序，使堆转为有序序列，不稳定排序。for_each()，遍历运算，丢弃调用返回值。transform()，遍历运算，保留调用返回值。accumulate()，合计。inner_product()，广义内积。partial_sum()，广义部分和。adjacent_difference()，相邻元素差。make_pair()，两个对象封装为一个对象。distance()，[first, last)之间的元素个数。back_inserter()，迭代器。front_inserter()，迭代器。inserter()，迭代器。min()，较小值。max()，较大值。swap()，交换a和b。
1.迭代器形式：
- InputIterator。一个只允许单个向序列输入迭代器，前向传递使用operator++和operator*。可以通过operator==和operator！=检测输入迭代器，这是约束的范围。
- OutputIterator。一个只允许单个向序列写入的元素的输出迭代器，前向传递使用operator++和operator*。可以持有无限个对象，不需要结尾检查，可以和ostream（通过ostream_iterator)一起使用，也普遍使用插入迭代器（back_insert()返回的迭代器类型。
- ForwardIterator。仍然仅用operator++前向移动，但是可以同时进行读和写和判断相等。
- BidirectionalIterator。支持ForwardIterator的全部操作，还增加了operator--运算，支持后向移动。
- RandomAccessIterator。支持一个常规指针所做的全部运算：可以通过增加和减少某个整数值，来向前和向后跳跃移动（不是每次只移动一个元素），还可以用operator[]作为下标索引，可以从一个迭代器中减去另一个迭代器，也可以用operator＜，operator＞来比较迭代器大小。
2.填充和生成
这些算法能够自动用一个特定值来填充（容器中的）某个范围的数据，或为（容器中的）某个特定范围生成一组值。
3. 计数
所有容器都含有一个成员函数size()，它可以告诉该容器包含多少个元素。size()的返回类型是迭代器的difference_type（通常是ptrdiff_t）。
-
计数（count）：对满足一定标准的对象计数
IntegraValue count(InputIterator first, InputIterator last, const EqualityComparable& value);
count()这个算法产生[first, last)范围内等于value的元素个数（相当于operator==）
IntegraValue count_if(InputIterator first, InputIterator last, Predicate pred);
count_if()这个算法产生[first, last)范围内能使pred返回true的元素个数。
4. 操作序列
5. 查找和替换
这些算法用来在某个范围内查找一个或多个对象，该范围由两个迭代器参数定义。
-
查找（find）：
InputIterator find(InputIterator first, InputIterator last, const EqualityComparable& value);
find()算法在[first, last)内查找value第一次出现的位置，如果value不在范围内，则返回last。这是线性查找（linear search），不对元素的顺序路径做任何假设。binary_search()是在有序的序列上工作，能更快的查找。
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);
find_if()在指定范围内执行线性查找，寻找一个满足pred的元素（使Predicate pred返回true），找不到则返回last。
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);
adjacent_find()进行线性查找，查找两个邻近的相等元素。第一种形式查找两个相等的元素（通过operator==）。第二种形式查找两个邻近的元素，当找到这两个元素并一起传递给binary_pred时产生true。如果找到这样的一对则返回指向第一个元素的迭代器，否则返回last。
ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);
ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator last2, BinaryPredicate binary_pred);
find_first_of()在指定范围内执行线性查找，在第二个范围内查找与第一个范围内的某个元素相等的元素。第一种形式使用operator==， 第二种形式使用判定函数。
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred);
search()算法检查第二个序列范围是否出现在第一个序列的范围内（顺序完全一致），如果是则返回一个迭代器，指向第一个范围序列中第二个序列出现的开始位置。没有找到则返回last1。第一种形式使用operator==， 第二种形式检测每对元素是否能使binary_pred返回true。
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred);
find_end()与search()类似，查找第二个范围的序列是否使第一个范围序列的子集，search()查找该子集首次出现的位置，find_end()查找最后出现的位置。返回指向该子集的第一个元素的迭代器。
ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value, BinaryPredicate binary_pred);
search_n()在[first, last)内查找一组共count个连续的值，这些值都与value相等（第一种形式），或是将所有这些与value相同的值传递给binary_pred时返回true（第二种形式）。找不到则返回last。
ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
ForwardIterator min_element(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);
min_element()返回一个迭代器，指向范围内“最小值”首次出现的地方。如果范围为空则返回last。第一种形式用operator<执行比较，且返回值为r（对范围[first, r)中的每个元素e，*e<*r都为假）。第二种形式用binary_pred比较，返回值是r（对于范围[first, r)中的每个元素e, binary_pred(*e, *r)都为假。
ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
ForwardIterator max_element(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);
max_element()指向范围内最大值首次出现的地方。第一种形式用operator<执行比较，且返回值为r（对范围[first, r)中的每个元素e，*r<*e都为假）。第二种形式用binary_pred比较，返回值是r（对于范围[first, r)中的每个元素e, binary_pred(*r, *e)都为假。
-
替换（replace）：
void replace(ForwardIterator first, Forwarditerator last, const T& old_value, const T& new_value);
void replace_if(ForwardIterator first, Forwarditerator last, Predicate pred, const T& new_value);
OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value);
OutputIterator replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);
reaplace()和replace_copy()在[first, last)内查找old_value并替换为new_value。replace_if()和replace_copy_if()查找满足判定函数pred的值并替换。- copy形式的函数不修改原始范围，而将作为替换的副本赋值给result，每次赋值后增加result。
6. 比较范围
以下算法提供比较两个范围的方法。
-
比较：
bool equal(InputIterator first1, InputIterator last1, InputIterator first2);
bool equal(InputIterator first1, InputIterator last1, InputIterator first2, BinaryPredicate binary_pred);
equal()算法中，第二个范围始于first2，长度取决于第一个范围。如果两个范围完全相同（有相同元素和顺序），则返回true。第一种形式使用operator==，第二种形式由binary_pred来决定两个元素是否相同。
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, BinartPredicate binary_pred);
lexicographical_compare()决定第一个范围是否“字典序小于（lexicographically less)”第二个范围。如果小于则返回true。如果完全相等，范围1不小于范围2，则返回false。- 如果两个范围长度不同，按字典序，一个范围内缺少的元素起到“领先于（precede）”另一个范围的元素的作用，因此“abc”领先于“abcd”。如果算法执行到结尾任没有不匹配的元素对，此时短范围领先，如果第一个范围是短范围，则返回true。
- 大写字母领先于小写字母。
- 第一种形式由operator<执行比较，第二种形式使用binary_pred。
pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred);
7. 删除元素：
STL“删除”函数重新排列该序列，将“已被删除的”元素排在序列的末尾，“未删除的”排在序列的开头，返回一个指向序列的“新末尾”元素的迭代器（不包含删除元素的序列的末尾）。
如果new_last是删除函数返回的迭代器，则范围[first, new_last)是不包含任何被删除元素的序列，而范围[new_last, last)是被删除元素组成的序列。
-
删除（remove）：
ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
- 这里的每一种“删除”都从头到尾遍历[first, last)，找到符合删除标准的值，并且复制未被删除的元素覆盖已被删除的元素。未被删除的元素保持原始排序。返回超越末尾的迭代器，该范围不包含任何已被删除的元素，迭代器指向的元素的值未被指定。
- if版本的删除把每一个元素传递给判定函数pred()来决定是否删除（如果pred()返回true则删除）。
- copy版本不改变原始序列，复制未被删除的值到一个始于result的新范围并返回指向新范围的超越末尾迭代器。
-
去重（unique）：
ForwardIterator unique(ForwardIterator first, ForwardIterator last);
ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);
OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result);
OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred);
-
这里的每一种unique()算法遍历[first, last)，找到相邻的相等值（副本），通过复制覆盖它们来删除副本。未被删除的元素原始顺序不变。返回超越末尾的迭代器，该范围相邻副本已被删除。 -
由于只删除相邻的副本，因此在unique()之前调用sort()，确保全部副本都被删除。 -
对于包含binary_pred调用版本中： binary_pred(*i, *(i-1));
如果返回true，则认为*i是一个副本。 -
copy版本不改变原始序列，将未被删除的值放到开始于result的新范围，并返回超越新范围末尾的迭代器。
8. 对已排序的序列进行排序和运算
STL提供了大量独立的排序算法，分别对应于稳定的、部分的或仅是规则的（不稳定）排序。只有部分排序有复制的版本。
对已排好序的序列进行包括排序或运算的每个算法都有两种版本。第一种使用对象自己的operator<来执行比较，第二种使用operator()(a, b)来决定a和b的相对顺序。
-
排序（sort）：
排序算法需要由随机存取的迭代器来限制序列的范围，如vector或deque。list容器有自己的嵌入sort（）杉树，因为它仅提供双向的迭代。
void sort(RandomAccessIterator first, RandomAccessIterator last);
void sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering binary_pred);
sort()将[first, last)范围内的序列按升序排序。第一种使用operator<，第二种使用提供的比较器对象来决定顺序。
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering binary_pred);
stable_sort()进行稳定的升序排序，保持相等元素的原始顺序。
void partital_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
void partital_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, StrictWeakOrdering binary_pred)
partital_sort()对[first, last)范围中一定数量元素进行排序，这些元素可以放入范围[first, middle)中。排序结束时，在范围[middle, last)中其余的元素不保证他们的顺序。
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last);
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, StrictWeakOrdering binary_pred);
partital_sort_copy()对[first, last)中的一定数量的元素排序，这些元素可以放入[result_first, result_last)中，并且复制到其中。如果[first, last)比[result_first, result_last)小，则使用较少的元素。
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, StrictWeakOrdering binary_pred);
nth_element()如同partital_sort，部分的处理（排列）范围内的元素。但比partital_sort少处理得多。nth_element唯一保证无论选择什么位置，该位置都会成为一个分界点。范围[first, nth]内的所有元素都会成对的满足二元判定函数（通常默认是operator<），而范围(nth, last]内的所有元素都不满足该判定。- 任意一个范围都没有排序，而partital_sort（）的第一个范围已排好序。
- 如果需要很弱的排序处理（如中值、百分点等），这个算法比
partital_sort()快得多。
-
有序序列查找：
如果在未排序的范围内使用这些函数，结果不可预料。
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value);
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, StricWeakOrdering binary_pred);
binary_search()告诉value是否出现在已排序的范围[first, last)中。- 二分查找使用的是前向顺序查找的迭代器而不是随机存取迭代器，是因为随机存取迭代器“是（is-a）”向前顺序查找迭代器。如果传递给这些算法之一的迭代器实际支持随机存取，则使用对数时间查找，否则执行线性查找。
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, StricWeakOrdering binary_pred);
lower_bound()返回一个迭代器，指出value在已排序的范围[first, last)中第一次出现的位置。如果value没有出现，返回的迭代器则指出它应该在序列中出现的位置。
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, StricWeakOrdering binary_pred);
upper_bound()返回一个迭代器，指出value在已排序的范围[first, last)中超越value最后出现的一个位置。如果value没有出现，返回的迭代器则指出它应该在序列中出现的位置。
pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value);
pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering binary_pred);
equal_range()本质上结合了lower_bound（）和upper_bound()，返回一个指出value在已排序范围[first, last)中首次和超越最后出现的pair。如果没有找到，则两个迭代器指出value在该序列中应该出现的位置。
-
合并有序序列（merge）：
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering binary_pred);
merge()从[first1, last1)和[first2, last2)中复制元素到result中，在结果范围的序列以升序排序，是稳定的运算。
void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, StrictWeakOrdering binary_pred);
inplace_merge()假定[first, middle)和[middle, last）是在相同的序列中已排好序的两个范围，合并这两个范围到一个结果序列[first, last)，结合成一个有序的序列。
-
集合运算：
一旦范围排好序，就可以执行数学集合运算。
bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, StrictWeakOrdering binary_pred);
includes()算法中，如果[first2, last2)是[first1, last1)的一个子集，返回true。没有任何一个范围要求只持有与另一个范围完全不同的元素，但如果[first2, last2)持有n个特定的元素，假如要返回true，则[first1, last1)也必须同时持有至少n个元素。
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering binary_pred);
set_union()算法在result范围中创建两个已排序范围的数学并集，返回值指向输出范围的末尾。没有任何一个输入范围要求只持有与另一个范围完全不同的元素，但是，如果在两个输入集合中多次出现某个特定值，结果集合中将包含完全相同的值出现的较大次数。
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering binary_pred);
set_intersection()算法在result中产生两个输入集合的交集，返回值指向输出范围的末尾。如果某个特定值在两个输入集合中多次出现，结果集合中将包含完全相同的值出现的较小次数。
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering binary_pred);
set_difference()算法产生数学上集合的差，返回值指向输出结果范围的末尾。所有出现在[first1, last1)中，但不在[first2, last2)中出现的所有元素放入结果集合。如果某个特定值在两个输入集合中多次出现（在集合1中n次，集合2中m次），结果集合将包含这个值的max（n-m，0）个副本。
OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering binary_pred);
9. 堆运算
标准库中的堆运算允许一个序列被视为是一个”堆“数据结构，可以高效的返回最高优先权的元素，而无需全部排序整个序列。
优先权是依据某些比较函数决定的。第一种版本通过operator<执行比较，第二种版本使用StrictWeakOrdering对象的operator()(a, b)来比较两个对象：a<b。
-
堆（heap）：
void make_heap(RandomAccessIterator first, RandomAccessIterator last);
void make_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering binary_pred);
make_heap()算法将一个任意序列范围转化成堆。
void push_heap(RandomAccessIterator first, RandomAccessIterator last);
void push_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering binary_pred);
push_heap()算法向由范围[first, last-1)决定的堆中增加元素*（last-1)。将最后一个元素放入堆中适合的位置。
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
void pop_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering binary_pred);
pop_heap()算法将最大的元素*first 放入位置*（last-1)并重新组织剩余的范围，使其保持堆的结构。如果只取*first,下一个元素将不是下一个最大的元素，故要保持堆，必须调用pop_heap()完成运算。
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
void sort_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering binary_pred);
sort_heap()算法使一个以堆顺序排列的序列，转化成普通的排列顺序，这样它就不再是一个堆。不稳定排序。- 调用sort_heap()后将不能在这个序列范围内调用push_heap()或pop_heap()。
10. 对某一范围内的所有元素进行运算
这些算法遍历整个范围并对每个元素执行运算。
-
遍历运算：
UnaryFunction for_each(InputIterator first, InputIterator last, UnaryFuction f);
for_each()算法对[first, last)中每个元素应用函数对象f，丢弃f的返回值。如果f仅是一个函数指针，说明与返回值无关；如果f是一个保留某些内部状态的对象，则该对象可以捕获一个返回值，它们结合到一起应用到该范围。最终返回值是f。
OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryFunction f);
OutputIterator transform(InputIterator1 first, InputIterator1 last, InputIterator2 first2, OutputIterator result, BinaryFunction f);
transform()对范围[first, last)中每个元素应用函数对象f。但是不丢弃调用结果。transform（）将结果复制（operator=）到*result，每次复制后增加result的内容。（result指向的序列必须有足够的空间；否则，用一个插入符强迫插入来代替赋值。）- 第一种形式调用
f(*first)，第二种形式调用f(*first1, *first2)。返回值都是超越末尾的迭代器，迭代器指出结果输出的范围。
11. 数值算法
这些算法包含在头文件 <numeric>中，主要用来执行数值计算。
-
合计：
T accumulate(InputIterator first, InputIterator last, T result);
T accumulate(InputIterator first, InputIterator last, T result, BinaryFunction f);
accumulate()的第一种形式是一般化的求和，对迭代器i指向的[first, last)的每一个元素执行result=result+*i，result是T类型。- 第二种形式对范围内每一个元素*i应用函数
f(result, *i)。
-
内积：
T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init);
T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init, BinaryFunction1 op1, BinaryFunction2 op2);
-
inner_product()算法计算范围[first1, last1）和[first2, first2 + (last1-first1) )的一个广义内积。用第一个序列中元素乘以第二个序列中“平行”的元素并对积进行累加来产生返回值。
-
参数init是内积的初始化值，可能是0也可能是任何值。 -
第二个序列至少含有第一个序列一样多的元素。 -
第二种形式对序列应用一对函数。函数op1代替加法，函数op2代替乘法。
序列{1，1，2，2}和{1，2，3，4}，内积为
(
1
?
1
)
+
(
1
?
2
)
+
(
2
?
3
)
+
(
2
?
4
)
(1*1)+(1*2)+(2*3)+(2*4)
(1?1)+(1?2)+(2?3)+(2?4)
第二种版本表示会进行以下运算：
init = op1(init, op2(1,1));
init = op1(init, op2(1,2));
init = op1(init, op2(2,3));
init = op1(init, op2(2,4));
-
广义部分和：
OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result);
OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryFunction op);
-
partial_sum()计算一个广义部分和。创建一个新的result开始的序列，新序列中每个元素都是[first, last)范围中从第一个元素到当前选择元素的累加和。
序列{1，1，2，2，3}，
输出为{1，1+1，1+1+2，1+1+2+2，1+1+2+2+3}={1，2，4，6，9}。
-
第二种版本使用二元函数op代替+运算符，取得积累到那个点的所有的“合计”，并于新值结合起来。
对{1，1，2，2，3}使用multiplies<int>()（一种乘法op)作为对象，
输出为{1，1，2，4，12}.
-
返回值指向输出范围[result, result+(last-first) )的末尾。
-
相邻元素差：
OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result);
OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryFunction op);
-
adjacent_difference()算法计算[first, last)中相邻的元素的差。这意味着在新序列中，每个元素的值是原始序列中当前元素于前面元素的差值（第一个值不变）。
序列{1，1，2，2，3}
输出{1，1-1，2-1，2-2，3-2}={1，0，1，0，1}
-
第二种形式使用二元函数op代替‘-’运算符执行“求差”。
例如使用multiplies<int>()（乘法代替减法）
输出{1，1，2，4，6}
-
返回值指向输出范围[result, result+(last-first) )的末尾。
12. 基本工具
和其他算法一起使用的一些基本工具。
-
pair:
(templates in the <utility> header)
template<class T1, class T2> struct pair;
template<class T1, class T2>
pair<T1, T2> make_pair(const T1&, const T2&);
- pair是简单将两个对象封装成一个对象的方法。
- 可以直接
insert()一个pair到map或multimap中，对于这些容器来说pair是value_type。
-
元素个数:
(From <iterator>)
difference_type distance(InputIterator first, InputIterator last);
distance()算法计算[first, last)之间的元素个数，返回一个整数，表示first等于last之前必须增加的次数。这一过程不会解析迭代器。
-
创建迭代器：
(From <iterator>)
back_insert_iterator<Container> back_inserter(Container& x);
front_insert_iterator<Container> front_inserter(Container& x);
insert_iterator<Container> inserter(Container& x, Iterator i);
back_inserter()、front_inserter()和inserter()用来为给定容器创建迭代器，以便向容器中插入元素，而不是用operator=覆盖容器中已存在的元素（默认行为）。- 每种类型迭代器有不同的插入运算。back_insert_iterator使用
push_back()，front_insert_iterator使用push_front()，insert_iterator使用insert()。
-
较小值:
const LessThanComparable& min(const LessThanComparable& a, const LessThanComparable& b);
const T& min(const T& a, const T& b, BinaryPredicate binary_pred);
min()算法返回两个参数中较小的一个，如果相等则返回第一个参数。- 第一个版本执行operator<，第二个版本将参数传给binary_pred执行比较。
-
较大值：
const LessThanComparable& max(const LessThanComparable& a, const LessThanComparable& b);
const T& max(const T& a, const T& b, BinaryPredicate binary_pred);
-
交换：
void swap(Assignable& a, Assignable& b);
void iter_swap(ForwardIterator1 a, ForwardIterator2 b);
swap()和iter_swap()使用赋值的方法交换a和b的值。- 所有容器都有特化的swap（）版本，更高效。
|