【C++基础】系列博客为参考《C++ Primer中文版（第5版）》（C++11标准）一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.前言
标准库容器定义的操作集合惊人得小。标准库并未给每个容器添加大量功能，而是提供了一组算法，这些算法中的大多数都独立于任何特定的容器。这些算法是通用的（generic，或称泛型的）：它们可用于不同类型的容器和不同类型的元素。
顺序容器只定义了很少的操作：在多数情况下，我们可以添加和删除元素、访问首尾元素、确定容器是否为空以及获得指向首元素或尾元素之后位置的迭代器。
我们可以想象用户可能还希望做其他很多有用的操作：查找特定元素、替换或删除一个特定值、重排元素顺序等。
标准库并未给每个容器都定义成员函数来实现这些操作，而是定义了一组泛型算法（generic algorithm）：称它们为“算法”，是因为它们实现了一些经典算法的公共接口，如排序和搜索；称它们是“泛型的”，是因为它们可以用于不同类型的元素和多种容器类型（不仅包括标准库类型，如vector或list，还包括内置的数组类型），以及我们将看到的，还能用于其他类型的序列。
2.概述
大多数算法都定义在头文件algorithm中。标准库还在头文件numeric中定义了一组数值泛型算法。
一般情况下，这些算法并不直接操作容器，而是遍历由两个迭代器指定的一个元素范围来进行操作。通常情况下，算法遍历范围，对其中每个元素进行一些处理。例如，假定我们有一个int的vector，希望知道vector中是否包含一个特定值。回答这个问题最方便的方法是调用标准库算法find：
1
2
3
4
5
int val = 42; //我们将查找的值
//如果在vec中找到想要的元素，则返回结果指向它，否则返回结果为vec.cend()
auto result = find(vec.cbegin(), vec.cend(), val);
//报告结果
cout << "The value " << val << (result == vec.cend() ? " is not present" : " is present") << endl;
传递给find的前两个参数是表示元素范围的迭代器，第三个参数是一个值。find将范围中每个元素与给定值进行比较。它返回指向第一个等于给定值的元素的迭代器。如果范围中无匹配元素，则find返回第二个参数来表示搜索失败。因此，我们可以通过比较返回值和第二个参数来判断搜索是否成功。
由于find操作的是迭代器，因此我们可以用同样的find函数在任何容器中查找值。例如，可以用find在一个string的list中查找一个给定值：
1
2
3
string val = "a value"; //我们要查找的值
//此调用在list中查找string元素
auto result = find(lst.cbegin(), lst.cend(), val);
类似的，由于指针就像内置数组上的迭代器一样，我们可以用find在数组中查找值：
1
2
3
int ia[] = {27, 210, 12, 47, 109, 83};
int val = 83;
int* result = find(begin(ia), end(ia), val);
此例中我们使用了标准库begin和end函数来获得指向ia中首元素和尾元素之后位置的指针，并传递给find。
还可以在序列的子范围中查找，只需将指向子范围首元素和尾元素之后位置的迭代器（指针）传递给find。例如，下面的语句在ia[1]、ia[2]和ia[3]中查找给定元素：
1
2
//在从ia[1]开始，直至（但不包含）ia[4]的范围内查找元素
auto result = find(ia+1, ia+4, val);
2.1.算法如何工作
find的工作是在一个未排序的元素序列中查找一个特定元素。概念上，find应执行如下步骤：
- 访问序列中的首元素。
- 比较此元素与我们要查找的值。
- 如果此元素与我们要查找的值匹配，find返回标识此元素的值。
- 否则，find前进到下一个元素，重复执行步骤2和3。
- 如果到达序列尾，find应停止。
- 如果find到达序列末尾，它应该返回一个指出元素未找到的值。此值和步骤3返回的值必须具有相容的类型。
这些步骤都不依赖于容器所保存的元素类型。因此，只要有一个迭代器可用来访问元素，find就完全不依赖于容器类型（甚至无须理会保存元素的是不是容器）。
迭代器令算法不依赖于容器，……
在上述find函数流程中，除了第2步外，其他步骤都可以用迭代器操作来实现：利用迭代器解引用运算符可以实现元素访问；如果发现匹配元素，find可以返回指向该元素的迭代器；用迭代器递增运算符可以移动到下一个元素；尾后迭代器可以用来判断find是否到达给定序列的末尾；find可以返回尾后迭代器来表示未找到给定元素。
……，但算法依赖于元素类型的操作
虽然迭代器的使用令算法不依赖于容器类型，但大多数算法都使用了一个（或多个）元素类型上的操作。例如，在步骤2中，find用元素类型的==运算符完成每个元素与给定值的比较。其他算法可能要求元素类型支持<运算符。不过，我们将会看到，大多数算法提供了一种方法，允许我们使用自定义的操作来代替默认的运算符。
关键概念：算法永远不会执行容器的操作
泛型算法本身不会执行容器的操作，它们只会运行于迭代器之上，执行迭代器的操作。泛型算法运行于迭代器之上而不会执行容器操作的特性带来了一个令人惊讶但非常必要的编程假定：算法永远不会改变底层容器的大小。算法可能改变容器中保存的元素的值，也可能在容器内移动元素，但永远不会直接添加或删除元素。
后续博文中会介绍，标准库定义了一类特殊的迭代器，称为插入器（inserter）。与普通迭代器只能遍历所绑定的容器相比，插入器能做更多的事情。当给这类迭代器赋值时，它们会在底层的容器上执行插入操作。因此，当一个算法操作一个这样的迭代器时，迭代器可以完成向容器添加元素的效果，但算法自身永远不会做这样的操作。
