C++ STL泛型算法

泛型算法

定义了大约 80 个标准算法。
它们操作由一对迭代器定义的（输入）序列或单一迭代器定义的（输出）序列。
当对两个序列进行拷贝、比较操作时，第一个序列由一对迭代器[b,e)表示，但第二个序列只由一个迭代器b2表示，b2指出了序列的起始位置。
应当保证第二个序列包含足够多的的元素供算法使用。
大多数标准库算法返回迭代器；特别是，它们不返回结果的容器。
大多数标准库算法都有两个版本：

• 一个“普通”版本使用常规操作（如<和==）完成其任务。
• 另一个版本接受关键操作参数
  在某些情况下，实参既可以解释为谓词，也可以解释为值。

不修改序列的算法

for_each()

最简单的算法是 for_each()，它简单地对序列中的每个元素执行指定操作。

vector<int> v{ 2,4,6,8 };for_each( v.begin(), v.end(), [](int x) {cout << x << ' '; } );/* 输出 2 4 6 8 */

序列谓词

vector<int> v{ 2,4,6,8 };auto flag = all_of(v.begin(), v.end(), [](int x) { return x > 0; });cout << flag << endl; // v 中的每个元素大于 0 ，输出 1

当一个序列谓词失败时，它不会告知我们是哪个元素导致了失败。

vector<int> v{ 0,4,8,3 };auto flag = any_of(v.begin(), v.end(), [](int x) { return x > 5; });cout << flag << endl; //有元素大于 5 ，但不知道是哪个元素大于5

count()

vector<int> v{ 1,0,1,1,3 };cout << count(v.begin(), v.end(), 1) << endl; // 1 的数目为 3，输出 3

find()

find() 系列算法顺序搜索具有特定值或令谓词为真的元素。
谓词是一个可调用的表达式，其结果是一个能用作条件的值。
算法 find() 和 find_if() 都返回一个迭代器，分别指向匹配给定值和给定谓词的第一个元素。

vector<char> v{ 'e','E','d','E','A'};auto p = find(v.begin(),v.end(),'E');cout << *p << endl; //输出 Ecout << *(p + 1) << endl; //输出 d

算法 find_first_of() 查找序列中与另一个序列中元素相等的第一个元素。

vector<char> v{ 'e','E','d','B','b' };array<char, 4> arr{ 'A','B','C','D' };auto p = find_first_of( v.begin(),v.end(),arr.begin(),arr.end() );cout << *p << endl; //输出 B

equal()

算法 equal() 比较两个序列中的元素是否都相同。

vector<char> v{ 'A','B','C','D','b' };array<char, 4> arr{ 'A','B','C','D' };auto b = equal( v.begin(),v.end() -1 ,arr.begin(),arr.end() );cout << b << endl; //输出 1 

mismatch()

算法 mismatch() 查找两个序列中第一对不匹配的元素，返回指向这两个元素的迭代器。
并没有参数指出第二个序列的末尾；算法假定第二个序列中至少包含与第一个序列一样多的元素。

vector<char> v{ 'A','B','e','D' };array<char, 4> arr{ 'A','B','C','D' };auto p = mismatch( v.begin(),v.end() ,arr.begin() );cout << *(p.first) << endl;//输出 ecout << *(p.second) << endl; //输出 C

search()

算法 search() 和 search_n() 查找给定序列是否是另一个序列的子序列。

vector<char> v{ 'E','A','B','C','D' };array<char, 3> arr{ 'A','B','C' } ;auto p = search(v.begin(), v.end(), arr.begin(), arr.end());cout << *p << endl; //输出 A；'A','B','C' 是 'E','A','B','C','D' 的子序列

修改序列的算法

transform()

数据写入操作不能超出目标序列的末尾。

array<char, 4> arr{ 'A','B','C','D' };vector<char> v{ 'E','A','B','C','Z'};transform(arr.begin(), arr.end(), v.begin(), [](char x) { return x += 32; });/* V 中的元素变为：a b c d Z */

输出和输入可能是同一个序列。

vector<char> v{ 'E','A','B','C','Z'};transform(v.begin(), v.end(), v.begin(), [](char x) { return x += 32; });/* V 中的元素变为：e a b c z */

copy()

copy() 系列算法从一个序列拷贝至另一个序列。
为了读取一个序列，需要一对迭代器描述起始位置和结尾位置；为了向序列中写入数据，则只需一个迭代器。

array<int,4> arr { 1,3,5,7 };vector<int> v{ 2,4,6,8 };auto p =copy( arr.begin(),arr.end(),v.begin() ); /* v 内的元素变为 1 3 5 7 */cout<< * (p-1) << endl; //输出 7；p = arr.end()

数据写入操作不能超出目标序列的末尾；但是，可以使用一个插入器按需增长目标序列。

array<int,4> arr { 1,3,5,7 };vector<int> v{ 2,4,6,8 };copy(arr.begin(), arr.end(), back_inserter(v));/* v 内的元素变为 2 4 6 8 1 3 5 7 */

拷贝算法的目标序列不一定是一个容器，任何可用一个输出迭代器描述的东西都可以作为它的目标。

unique()

算法 unique() 将不重复的元素移动到序列的头部，并返回指向不重复元素末尾位置的迭代器。

vector<char> v{ 'A','A','C','E','E','B'};auto p = unique(v.begin(), v.end()); auto iter = v.begin();while (iter != p){cout << *iter++ << ' ';}cout << endl;/* 输出： A C E B */

为了从一个容器中删除重复元素，必须显示地收缩容器。

vector<char> v{ 'A','A','C','E','E','B'};auto p = unique(v.begin(), v.end()); v.erase(p,v.end());

remove()

算法 remove() “删除”序列末尾的元素；它是通过将元素移动到左侧来实现“删除”的。

vector<char> v{ 'A','B','C','E','E','D' };auto p = remove(v.begin(), v.end(),'E');auto iter = v.begin();while (iter != p){cout << *iter++ << ' ';}cout << endl;/*输出：A B C D*/

raplace()

算法 raplace() 将新值赋予选定的元素。

vector<char> v{ 'E','A','E','B','C','D' };replace(v.begin(), v.end(),'E','F'); // 将 E 替换为 F/* v 内的元素变为 F A F B C D */

rotable() 、 random_shuffle() 和 partition()

算法 rotable() 、 random_shuffle() 和 partition() 提供了移动序列中元素的系统方法。
rotable()（以及洗牌和划分算法）是用 swap() 来移动元素的。

rotable()

vector<char> v{ 'A','B','C','D','E' };auto p = rotate(v.begin(),v.begin()+2, v.end());/* v 内的元素变为 C D E A B */cout << *p << endl; // *p = A

random_shuffle()

默认情况下，random_shuffle() 用均匀分布随机数发生器洗牌序列。
即，它选择序列元素的一个排列，使得每种排列被选中的概率相等。

vector<char> v{ 'A','D','C','B','E' };random_shuffle(v.begin(),v.end());/* v 内的元素变为 E D B C A */

partition()

划分算法基于某种划分标准将序列分为两部分。

vector<char> v{ 'A','H','C','B','F' };auto p = partition(v.begin(), v.end(), [](char x) {return x < 'E'; });/* v 内的元素变为 A C B H F */cout << *p << endl; // *p = H

排列

例：打印序列 ABC 的所有排列组合：

vector<char> v{ 'A','B','C' };bool x = true;while ( x ){x = next_permutation(v.begin(), v.end());for (auto i : v)cout << i << ' ';cout << endl;}/*输出：A C BB A CB C AC A BC B AA B C*/

算法 next_permutation() 接受一个序列，将其变换为下一个排列。
“下一个”的定义基于这样一个假设：所有的排列组合已按字典序排序。
如果存在”下一个“排列组合，next_permutation() 返回 true；否则，它将序列变换为升序中排在第一位的排列组合（例中的 ABC），并返回 false；

fill()

fill() 系列算法提供了向序列元素赋值和初始化元素的方法。
算法 fill() 反复用指定值进行赋值。

vector<char> v{ 'A','H','C','B','F' };fill(v.begin(), v.end(), 'E');/* v 内的元素变为 E E E E E */

算法 generate() 则通过反复调用其函数实参得到的值进行赋值。

vector<char> v{ 'A','H','C','B','F' };int i = 0;generate( v.begin(), v.end(), [&i] { ++i; return 'A'+ i; } );/* v 内的元素变为 B C D E F */

算法 uninitialized_fill() 或 uninitialized_copy() 的目标元素必须是内置类型或是未初始化的。

排序和搜索

排序

默认的比较操作是<运算符；值 a 和 b 的相等性通过!(a<b)&&!(b来判定，而不是使用==运算符。
算法 sort() 要求使用随机访问迭代器。
基础的 sort() 算法很高效，平均时间复杂性为$O(N\ast \log (N))$。。
如果需要一个稳定的排序算法，可以使用 stable_sort()，其平均时间复杂性为$O(N\ast \log (N)\log (N))$；当系统有足够的额外内存时，可缩短为$O(N\ast \log (N))$。
算法 stable_sort() 可以保证相等元素的相对顺序，然而 sort() 则不能保证。
如果需要由 partial_sort() 排序的元素数少于元素总数，则其时间复杂性接近$O(N)$。
算法 partial_sort_copy() 的目标必须是一个随机访问迭代器。
算法 nth_element() 只需将升序结果中排在第 n 位的元素放置到正确位置即可（即，之前的元素都不大于它，之后的元素都不小于它）。

二分搜索

binary_serach() 系列算法提供有序序列上的二分搜索。
一旦序列已排序，就可以使用二分搜索查找元素了。

merge()

算法 merge() 将两个有序序列合并为一个序列。
算法 merge() 可以接受不同类别的序列和不同类型的元素。

集合算法

这些算法将序列当作一个元素集合来处理，并提供基本的集合操作。
输入序列应是排好序的，输出序列也会被排序。

堆

堆是一种按最大值优先的方式组织元素的紧凑数据结构。
堆算法允许将一个随机访问序列作为堆处理。
堆的关键特点是提供了快速插入新元素和快速访问最大元素的能力；其主要用途是实现优先队列。

lexicographical_compare()

字典序比较就是我们用来排序字典中单词的规则。

最大值和最小值

如果比较两个左值，返回的是指向结果的引用；否则，返回一个右值。
但是，接受左值的版本接受的是 const 左值，因此永远也不能修改这些函数的返回结果。