C++ STL 算法总结 gaunthan Posted on Sep 30 2016 ? C++ ? > 本文提到的STL算法都位于`algorithm`头文件。所有这些函数都位于名字空间std。 ## 迭代器种类 为了简化我们将要介绍的模板算法，我们介绍以下的迭代器名称，以及它们用于STL算法的模板参数时的含义： |迭代器名称|译名|定义|特点| |--| |InputIterator|输入迭代器|只允许向序列读入单个元素的输入迭代器|前向传递使用 `operator++` 和 `operator*`，可以通过`operator==`和`operator!=`检测输入迭代器| |OutputIterator|输出迭代器|只允许向序列写入单个元素的输出迭代器|前向传递使用`operator++`和`operator*`。另外由于假定其涉及的容器可以持有无限个数的对象，因此不需要结尾检查。不能使用`operator==`和`operator!=`检测| |ForwardIterator|前向迭代器|可同时读写的OutputIterator或InputIterator|可以用来取代OutputIterator和InputIterator| |BidrectionalIterator|双向迭代器|可以进行后向移动的ForwardIterator|支持ForwardIterator所做的全部操作，另外还增加了`operator--`操作| |RandomAccessIterator|随机迭代器|支持一个常规指针所做的全部运算的迭代器|可以通过增加或减少某个整数值来向前或向后跳跃移动；可以用`operator[]`作为下标索引；可以从一个迭代器中减去另一个迭代器；可以用`operator<`和`operator>`来比较迭代器哪个更大| ## 填充和生成 下面讲述的算法能够自动用一个特定值来填充（容器中的）某个范围的数据，或为（容器中的）某个特定范围生成一组值。“填充（fill）”函数向容器中多次插入一个值，“生成（generate）”函数使用发生器来产生插入到容器中的值。 ### fill ``` cpp void fill (ForwardIterator first, ForwardIterator last, const T& val); ``` ### fill_n ``` cpp OutputIterator fill_n (OutputIterator first, Size n, const T& val); ``` ### generate ``` cpp void generate (ForwardIterator first, ForwardIterator last, Generator gen); ``` ### generate_n ``` cpp OutputIterator generate_n (OutputIterator first, Size n, Generator gen); ``` ### 例子 ``` cpp #include <algorithm> #include <vector> #include <iostream> #include <iterator> using namespace std; int current = 0; int UniqueNumber () { return ++current; } int main(void) { vector<int> ivec(5); generate(ivec.begin(), ivec.end(), UniqueNumber); fill_n(back_inserter(ivec), 3, 6); copy(ivec.begin(), ivec.end(), ostream_iterator<int>(cout, " ")); } ``` ## 计数 所有的容器都含有一个成员函数`size()`，它告知容器含有元素的数量。`size()`的返回类型是迭代器的 difference_type（通常是 ptrdiff_t)。简单起见，下面我们用 IntegralValue 表示这个返回类型。使用下面的算法可以对容器进行对象计数。 ### count ``` cpp IntegralValue count (InputIterator first, InputIterator last, const T& val); ``` 在这个算法中，产生[first, last)范围内其值等于value（用`operator==`测试）的元素的个数。 ### count_if ``` cpp IntegralValue count_if (InputIterator first, InputIterator last, UnaryPredicate pred); ``` 这个算法产生[first, last)范围内能使pred返回true的元素的个数。 ### 例子 下面的程序使用`count_if`统计容器中小写字母的数量： ``` cpp #include <algorithm> #include <functional> #include <vector> #include <iostream> using namespace std; int main(void) { vector<char> vc = {'a', 'b', 'c', 'd', 'A', 'B'}; int cnt = count_if(vc.begin(), vc.end(), bind2nd(greater_equal<char>(), 'a')); cout << cnt << endl; return 0; } ``` ## 操作序列 下面提到的都是有关移动序列的算法： ### copy ``` cpp OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result); ``` `copy`算法从范围[first, last)复制序列到destination，每次赋值后都会增加destination。算法有几点限制： - 源序列不能包含目的序列 - 目的序列范围的空间必须存在（允许赋值） 因为使用了赋值操作，因此不能直接向空容器或容器末尾插入元素，但是可以把destination迭代器封装在`insert_iterator()`里达到目的（在与容器发生联系的情况下，使用`back_inserter()`或`inserter()`。 ### copy_backward ``` cpp BidirectionalIterator2 copy_backward ( BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result); ``` 这个算法如同`copy()`一样，但是以相反的顺序复制元素。它将源范围[first, last)序列复制到目的序列，但第一个目的元素是destinationEnd - 1。 ### reverse ``` cpp void reverse (BidirectionalIterator first, BidirectionalIterator last); ``` 该算法倒置范围[first, last)内的元素。 ### reverse_copy ``` cpp OutputIterator reverse_copy (BidirectionalIterator first, BidirectionalIterator last, OutputIterator result); ``` 该算法保持原序列范围元素顺序不变，而将倒置的元素复制到destination，返回结果序列范围的尾后迭代器。 ### swap_ranges ``` cpp ForwardIterator2 swap_ranges (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); ``` 该算法通过交换对应的元素来交换相等大小的两个范围的内容。 ### rotate ``` cpp ForwardIterator rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last); ``` 该算法把[first, middle)范围中的内容移到该序列的末尾，并且将[middle, last)范围中的内容移动到该序列的开始位置。 ### rotate_copy ``` cpp OutputIterator rotate_copy (ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result); ``` 使用`rotate_copy()`不改变原始序列范围，且将轮转后版本的元素复制到destination，返回尾后迭代器。 ## 查找和替换 ### find ``` cpp InputIterator find (InputIterator first, InputIterator last, const T& val); ``` `find()`在范围 [first, last) 中查找值val，若找到则返回该值第一次出现的位置，否则返回last。该算法是线性复杂度的，它对每个连续的元素依次执行相等测试。 ### find_if ``` cpp InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred); ``` 该算法如同`find()`一样，只是代替查找val，它查找一个满足pred的元素。 ### adjacent_find ``` cpp ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last); ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last); ``` 如同`find()`一样，这些算法也执行线性查找，但不是仅查找一个元素，而是查找两个临近的相等元素。函数`adjacent_find()`的第一种形式通过`operator==`查找两个相等的元素，而第二种形式查找两个相邻且满足`binary_pred`的元素。对于该函数的返回值，当找到时返回指向两个元素中第一个元素的迭代器，否则返回last。 ### find_first_of ``` cpp InputIterator find_first_of (InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2); InputIterator find_first_of (InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2, BinaryPredicate pred); ``` 该算法在两个范围序列中查找第一个相等的元素（第二种形式查找满足pred的元素），若找到则返回该元素在序列1中的迭代器，否则返回last1。由于一个序列中的任意一个元素都要与另外一个序列的每一个元素做相等比较，该算法是平方级复杂度的。 ### search ```cpp ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); ``` `search()` 检查第二个序列范围是否出现在第一个序列的范围内（顺序也完全一致），如果是则返回一个迭代器，该迭代器指向第一个范围序列中第二个范围序列出现的位置。否则，返回last1。第一种形式测试使用 `operator==`，第二种形式检测被比较的每对元素是否能使 `binary_pred` 返回 true。 ### find_end ``` cpp ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); ``` 这些算法的形式和参数如同`search()`，其查找第二个范围的序列是否在第一个范围内作为子集出现，但是与`search()`查找该子集首先出现的位置有所不同，`find_end()`查找该子集最后出现的位置，并且返回指向该子集的第一个元素的迭代器。 ### search_n ``` cpp ForwardIterator search_n (ForwardIterator first, ForwardIterator last, Size count, const T& val); ForwardIterator search_n ( ForwardIterator first, ForwardIterator last, Size count, const T& val, BinaryPredicate pred ); ``` 这些算法在[first, last)范围内查找一组共coun个连续的值，这些值都与valu相等（在第一种形式中）或者将这些与value相同的值传递给binary_pred时返回true（在第二种形式中）。如果不能找到这样一组数值就返回last。 ### min_element ``` cpp ForwardIterator min_element (ForwardIterator first, ForwardIterator last); ForwardIterator min_element (ForwardIterator first, ForwardIterator last, Compare comp); ``` `min_element()`算法返回一个迭代器，该迭代器指向范围内“最小的”值首次出现的位置，如果找不到则返回last。第一种形式使用`operator<`进行比较；第二种形式使用`binary_pred`比较，其意义是：对于范围[first, r)中每个元素e，`binary_pred(*e, *r)`都为假，其中r为返回值。 ### max_element ``` cpp ForwardIterator max_element (ForwardIterator first, ForwardIterator last); ForwardIterator max_element (ForwardIterator first, ForwardIterator last, Compare comp); ``` `max_element()`查找范围内“最大的”值首次出现的位置。与`min_element()`算法类似，唯一不同在于其参加测试的参数位置相调。比如对于第二种形式，需要对于每一个元素，`binary_pred(*r, *e)`都为假。 ### replace ``` cpp void replace (ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value); void replace_if (ForwardIterator first, ForwardIterator last, UnaryPredicate pred, const T& new_value ); ``` `replace()`在范围[first, last)内进行查找，找到与old_value相等的值并用new_value替换它们。而`replace_if()`则是查找满足判定函数pred的值。 ### replace_copy ``` cpp 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, UnaryPredicate pred, const T& new_value); ``` `replace_copy()`不修改原始范围，而是将其作为一个替代的副本赋给result。若满足条件，则将原值赋给result，否则将new_value赋给result，以更新它的值。每次赋值后都是增加result。 ## 比较范围 ### equal ``` cpp bool equal (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); bool equal (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred); ``` `equal()`比较两个范围，如果它们相同（相同的元素和相同的顺序），则返回true；否则，返回false。在第一种形式中，使用`operator==`执行比较，第二种形式由`binary_pred`来决定两个元素是否相同。 ### lexicographical_compare ``` cpp bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp); ``` 这两个函数决定第一个范围是否“字典序小于(lexicographically less)”第二个范围。如果是，返回true，否则返回false。 所谓**字典序比较**就是： > 每次比较一个元素。如果第一个元素不同，则其就决定了两个字符串比较的结果。如果相同，则算法移动下一个元素继续检查它们。如此下去直到遇到不匹配的那对元素为止。如果范围1序列中的这个元素小于范围2序列中的相应元素，则算法返回true，否则返回false。 如果从头至尾扫描都没有发现不相等的地方，算法会认为范围1不小于范围2，从而返回false。 > 如果两个范围的长度不同，按字典序，一个范围内缺少的元素起到“领先于（precede）”另一个范围内存在元素的作用，因此短的范围小。在这种情况下，如果短的范围是序列1，则结果是true，否则是false。 ### mismatch ``` cpp pair<InputIterator1, InputIterator2> mismatch (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); pair<InputIterator1, InputIterator2> mismatch (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred); ``` 这些算法如同在`equal()`中一样，进行比较的两个范围的长度完全相同，因此仅需要第二个范围的first迭代器，第一个范围的长度可以用来做第二个范围的长度。这个函数的功能与`equal()`正好相反，`equal()`仅比较两个范围是否相同，`mismatch()`告诉比较从哪里开始不同。如果找到不同点，则将第一个范围内出现不匹配元素的位置和第二个范围内出现不匹配的元素的位置一起装入一个pair对象并返回。如果没有找到，则将两个范围的尾后迭代器返回。 `pair`模板类是定义在`<utility>`头文件中的一个模板类，其函数两个用成员名first和second表示的元素。 ## 删除元素 在STL中，迭代器可以指向数组、vector和lis等，如果试图销毁正被删除的元素和改变输入范围的大小是不安全或不是不合理的（例如，一个已存在数组不能改变它的大小）。为了通用性，STL的“删除”函数仅仅重新排列序列，使得“已被删除的”元素排在序列末尾，“未被删除的”元素排在序列开头，然后返回不含被删除元素的序列的末尾迭代器，即被删除元素序列的开头。换句话说，如果new_last是从“删除”函数返回的迭代器，则范围[first, new_last)是不包含任何被删除元素的序列，而范围[new_last, last)是被删除元素组成的序列。 如果使用的是一个可以调整大小的容器，并且想真正删除元素，可以使用`erase-remove idiom`： c.erase(remove(c.begin(), c.end(), value), c.end()); ### remove ``` cpp ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val); ForwardIterator remove_if (ForwardIterator first, ForwardIterator last, UnaryPredicate pred); ``` `remove()` 找到删除条件的值，并且赋值未被删除的元素覆盖已被删除的元素。未被删除的元素的原始排列顺序仍然保持。 ### remove_copy ``` cpp OutputIterator remove_copy (InputIterator first, InputIterator last, OutputIterator result, const T& val); OutputIterator remove_copy_if (InputIterator first, InputIterator last, OutputIterator result, UnaryPredicate pred); ``` `remove_copy()`版本的删除不需要修改原始序列，而取而代之是复制未被删除的值到一个开始于result的新范围，并返回指向新范围的超越末尾的迭代器。 ### unique ``` cpp ForwardIterator unique (ForwardIterator first, ForwardIterator last); ForwardIterator unique (ForwardIterator first, ForwardIterator last, BinaryPredicate pred); ``` `unique`的每一种版本都从头至尾遍历范围[first, last)，找到**相邻**的相等值（即副本），并且通过赋值覆盖它们来“删除”这些副本。未被删除的元素的原始顺序仍然保持不变。返回值是指向该范围的尾后迭代器，该范围相邻副本已被删除。 因为要删除的只是相邻的副本，因此如果有可能的话，在调用`unique`算法之前，调用`sort()`，这样就能保证全部的副本都被删除掉。 ### unique_copy ``` cpp OutputIterator unique_copy (InputIterator first, InputIterator last, OutputIterator result); OutputIterator unique_copy (InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred); ``` “copy”版本不改变原始序列，取而代之复制未被删除的值到一个开始于result的新范围，并返回该新范围的尾后迭代器。 ## 对某一范围内的所有元素进行运算 下面的算法遍历整个范围并对每个元素执行运算。它们在利用运算的结果方面有所不同：`for_each()`丢弃运算的返回值，而`transform()`将每个运算的结果放入一个目的序列（也可以是原始序列）。 ### for_each ``` cpp Function for_each (InputIterator first, InputIterator last, Function fn); ``` `for_each()`对[first, last)的每个元素应用函数fn，丢弃每个个别的fn应用的返回值。如果fn仅是一个函数指针，说明调用与返回值无关；然而如果fn是一个保留某些内部状态的函数对象，则该对象可以捕获一个返回值，它们结合到一起应用到该范围上。`for_each()`的最终返回值是fn。 ### transform ``` cpp OutputIterator transform (InputIterator first1, InputIterator last1, OutputIterator result, UnaryOperation op); OutputIterator transform (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binary_op); ``` 如同`for_each()`一样，`transform()`对范围[first, last)中的每个元素应用op，但是其不丢失函数调用的结果，而是将结果复制（使用`operator=`）到*result，每次复制后增加result的内容。result指向的序列必须有足够的存储空间，否则，需要用一个插入器来强迫使用插入而不是赋值。 ## References - Meyers S. Effective C++[M]. 电子工业出版社, 2011. - StanleyB.Lippman, JoseeLajoie, BarbaraE.Moo, 等. C++ Primer 中文版 [M]. 电子工业出版社, 2013. 赏 Wechat Pay Alipay C++ 处理好赋值运算符的自赋值 C++ 函数对象
