第9章 泛型算法

9.1 概述

顺序容器只定义了很少的操作，在多数情况下，我们可以对顺序容器进行添加元素、删除元素、访问首尾元素、确定容器是否为空以及获得指向首元素或尾元素之后位置的迭代器等操作。我们还希望做其他很多有用的操作，比如查找特定元素、替换或删除一个特定值、重排元素顺序等。标准库定义了一组泛型算法来实现这些操作。大多数泛型算法都定义在头文件algorithm中，在头文件numeric中还定义了一组数值泛型算法。
1.find算法
假定我们有一个vector容器，数据类型为int，希望知道该容器中是否包含一个特定值，最简单的方法是使用标准库算法find。

int val = 42;
auto result = find(vec.begin(),vec.end(),val);
cout<<"the value"<<val<<(result==vec.cend()?"is not present":"is present")<<endl;

传递给find的前两个参数是表示元素范围的迭代器，第三个参数是一个值（表示要搜索的值）。find算法将范围内每个元素与要搜索的值进行比较。如果要搜索的值存在，返回指向第一个等于给定值的元素的迭代器。如果范围内搜索不到要找的值，则返回第二个参数来表示搜索失败。
2.find算法如何工作
1.访问序列中的首元素
2.比较此元素与我们要查找的的值
3.如果此元素与要查找的值匹配，find返回标识此元素的值（迭代器）
4.否则，find前进到下一个元素，重复执行步骤2和3
5.如果到达序列尾，搜索停止，它返回一个指出元素未找到的值（默认为序列末元素迭代器）

9.2 初识泛型算法

9.2.1 只读算法

一些算法只会读取其输入范围内的元素而不改变元素，find 就是这样一种算法。
1.求和算法accumulate
accumulate定义在头文件numeric中，算法 accumulate 接受三个参数，前两个指出了需要求和的元素的范围，第三个参数是和的初值。

int sum = accumulate(vec.cbegin(),vec.cend(),0);

注意： 序列中元素的类型必须与第三个参数匹配或者是能够转换为第三个参数的类型，否则无法求和。
2.比较算法equal
equal 用于确定两个序列是否保存相同的值。它将第一个序列中的每个元素与第二个序列中的对应元素进行比较。如果所有对应的元素都相等则返回true，否则返回false。此算法接受三个迭代器：前两个表示第一个序列中的元素范围，第三个迭代器表示第二个序列的首元素。

equal(vec1.cbegin(),vec1.cend(),vec2.cbegin()); // vec2中的元素数目至少与vec1的一样多

注意： 可以通过调用equal来比较两个不同类型的容器中的元素，只要我们能用相等运算符来比较这两个元素类型即可。

9.2.2 写容器元素的算法

一些算法会修改容器中元素的值，使用这类算法时必须确保原序列长度不小于算法要写入的元素数目。记住，算法不会执行容器操作，因此使用算法不会改变容器的大小。
1.算法fill
算法 fill 接受一对迭代器表示一个范围，还接受一个值作为第三个参数。fill 用第三个参数来修改迭代器表示的范围中的每个元素。

fill(vec.begin(),vec.end(),0);  //将每个元素重置为0

2.算法fill_n
算法 fill_n接受一个迭代器a，一个计数值b和一个值c，它将值c赋予迭代器a指向的元素开始的b个元素。我们可以用fill_n将一个新值赋予vector中的元素，如下所示：

vector<int>vec（10，1）;
fill_n(vec.begin(),vec.size(),0);    //将所有元素重置为0

3.back_inserter
一种保证算法有足够元素空间来容纳输出数据的方法是使用插入迭代器，插入迭代器是一种向容器中添加元素的迭代器。通常情况下当我们通过一个迭代器向容器元素赋值时，值被赋予迭代器指向的元素。而当我们通过一个插入迭代器赋值时，一个与赋值号右侧值相等的元素被添加到容器中。back_inserter是定义在头文件iterator中的一个函数，它接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器。当我们通过此迭代器赋值时，赋值运算符会调用push_back将一个具有给定值的元素添加到容器中，如下所示：

vector<int>vec;
auto it = back_inserter(vec);
*it = 42;   //vec添加一个元素42
vector<int>vec;
fill_n(back_inserter(vec),10,0);

4.算法copy
此算法接受三个迭代器，前两个表示一个输入范围，第三个表示目的序列的起始位置。此算法将输入范围中的元素拷贝到目的序列中，传递给copy的目的序列至少要包含与输入序列一样多的元素。

int a1[] = {
   0,1,2,3,4,5,6,7,8,9};
int a2[sizeof(a1)/sizeof(*a1)];      //a2和a1一样大
auto ret = copy(begin(a1),end(a1),a2); //把a1拷贝给a2

copy返回的是其目的位置迭代器（递增后）的值，即 ret 恰好指向拷贝到 a2 的尾元素之后的位置。
5.算法replace
replace算法读入一个序列，并将其中所有等于给定值的元素都改为另一个元素。此算法接受四个参数：前两个是迭代器，表示输入序列，第三个是要搜索的元素a，最后一个是用来替换的元素b，它将所有等于值a的元素替换为值b。

replace(ist.begin(),ist.end(),0,42);

9.2.3 重排容器元素的算法

某些算法会重排容器中元素的顺序，一个明显的例子是sort。调用sort会重排序列中的元素，它是利用序列中元素类型的小于运算符来实现的。假定我们有一个 vector 保存了多个故事的文本，我们希望简化这个vector，使得每个单词只出现一次，而不管单词在任意给定文档中到底出现了多少次。使上面变成下面：

the quick red fox jumps over the slow red turtle
fox jumps over quick red slow the turtle

1.消除重复单词
首先将 vector 排序使得重复单词都相邻出现。一旦 vector 排序完毕，就可以使用一个名为 unique 的标准库算法来重排vector，使得不重复的元素出现在 vector 的开始部分，由于算法不能执行容器的操作，使用 vector 的 erase 成员来完成真正的删除操作。

void elimDups(vector<string>&words)
{
   
  //按字典序排序words,以便查找重复单词
  sort(words.begin(),words.end());
  //unique重排输入范围，使得每个单词只出现一次并排列在前部，重复单词置于后面，返回指向不重复区域之后第一个位置的迭代器
  auto end_que=unique(words.begin(