C++ Primer

泛型算法

我们前一章学习了容器，不知道你有没有发现，其实容器是一个模板类，就是说在类的上面还有一层，看下面这句话：

vector<int> a;

这里面包含了模板类vector->类vector<int>->对象a，也就是说vector不独立于任何数据类型，它是在数据类型之上的那一层，模板类。

这个特征跟我们这一章要学的泛型算法有些类似，我们有很多的标准库容器，那我们是不是要给每个标准库容器写算法呢？C++不是这样做的，这样太麻烦了，C++的做法是提供一组算法，独立于任何特定的容器，这些算法是类型无关的，是泛型（generic）的：就是说它们可以用于不同类型的容器和不同类型的元素。

在前面学的顺序容器中，我们提供的操作都很基本，增删元素，访问头尾元素等，这一章我们会提供更多有用的操作（而且它们基本可以用于所有的容器）

概述

大多数算法都定义在algorithm中。

算法一般不直接操作容器，而是遍历由两个迭代器指定的一个元素范围（这个就是有点泛型的意思了）。我们来举个例子，假定有一个int的vector，我们要判断里面是否包含一个特定值，代码如下：

int val = 24;
auto res = find(vec.begin(), vec.end(), val);
cout << (res == vec.end() ? "不存在" : "存在") << endl;

是不是超级简单？而且这个find函数可以适用于各种容器，是泛型的。

为什么会这么6这么神奇呢，我们来仔细看看find算法是怎么做的： find算法通过迭代器去依次访问元素，找到就停止，直到尾后元素。

这些都不依赖于容器所保存的元素类型或者是容器类型，它就是迭代器去访问。

迭代器令算法不依赖于容器，这个我们知道了，还有一句话是这样的，但算法依赖于元素类型的操作，这句话怎么理解呢？因为算法在执行时肯定要操作元素，比如我们的find算法，它至少要使用==符号来判等，所以就要求元素类型支持 ==，这里的类型是int，当然支持了。

算法本身不会执行容器的操作，它们只会运行于迭代器之上

初识泛型算法

我们学习的泛型算法基本都对一个范围内的元素进行操作，这个范围由两个参数表示，前一个指向要处理的第一个元素，后一个指向尾元素之后的位置。

只读算法

只读取其输入范围内的元素，从不改变元素。例如之前的find函数，再来一个例子：

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

这个函数是对容器内元素求和，第三个参数是求和的初值，这个算法要求容器内的元素类型支持+，再来一个例子，string定义了+，所以可以对string求和：

int sum = accumulate(vec.cbegin(), vec.cend(), string("")); //泛型，跟上面几乎一样

操作两个序列的算法

equal(vec1.cbegin(), vec1.cend(), vec2.cbegin());

vec2元素数量要大于等于vec1，前面每个元素都对应相等蔡返回true

写容器元素的算法

举个例子：

fill(vec.begin(), vec.end(), 0); //将所有元素重置为0
//但是算法不会去检查写这个操作，例如
vector<int> v;
fill_n(v.beg(), 10, 0); //这个函数企图把v开头的10个元素置为0
//但是会出错，而且不会报编译错误

//再介绍一个函数back_inserter，定义在iterator头文件
vector<int> vv;
auto it = back_inserter(vec); //返回一个插入迭代器，通过向插入迭代器赋值
*it = 24; //就可以成功插入了，vv中有一个元素24
//这里我们调用了它，作用是用插入迭代器来插值
fill_n(back_insertet(v), 10, 0);

拷贝算法

甩代码：

int a1[] = {0, 1, 2, 3, 4};
int a2[sizeof(a1)/sizeof(*a1)]; //相同元素个数
auto ret = copy(begin(a1), end(a1), a2); //把a1的内容拷贝给a2，返回a2尾元素之后的值

还有一个replace算法：

replace(list.begin(), list.end(), 0, 42); //把list中所有的0改为42
//还有一种重载，保留了原来的list
replace(list.cbegin(), list.cend(), back_inserter(ivec), 0, 42);
//list不变，ivec包含list的一份拷贝，不过里面的0都变成42了

重排容器元素的算法

我们要通过一个任务来学习这部分，假定我们要化简一个vector，使得里面保存的单词只出现一次：

//假设原来的vector为a, b, d, c, a, b
void Unique(vector<string> &words)
{
    sort(word.begin(), words.end()); //a, a, b, b, c, d
    auto end_unique = unique(words.begin(), words.end()); //a, b, c, d, a, b
    //end_unique的位置就是第一个重复的元素位置
    words.eraser(end_unique, wors.end()); //a, b, c, d
}