泛型算法概述

泛型算法概述

顺序容器只定义了很少的操作：在多数情况下，我们可以添加和删除元素。访问首尾元素、确定容器是否为空以及获得指向首元素或尾元素之后位置的迭代器。

如果我们想要做：查找特定元素、替换或删除一个特定值、重排元素顺序等。标准库并未给每个容器都定义成员函数来实现这些操作，而是定义了一组泛型算法：称它们为“算法”，是因为它们实现了一些经典算法的公共接口，如排序和搜索；称它们是“泛型的”，是因为它们可用于不同类型的元素和多种容器类型（不仅包括标准库类型，如vector或list，还包括内置的数组类型）。

概述

大多数算法都定义在头文件algorithm中。标准库还在头文件numeric中定义了一组数值泛型算法。

一般情况下，这些算法并不直接操作容器，而是遍历由两个迭代器指定的一个元素范围来进行操作。通常情况下，算法遍历范围，对其中每个元素进行一些处理。例如，假定我们有一个int的vector，希望指定vector中是否包含一个特定值。回答这个问题最方便的方法是调用标准库算法find：

int val=42;     //我们将查找的值
//如果在vec中找到想要的元素，则返回结果指向它，否则返回结果为vec.cend()
auto result=find(vec.cbegin(),vec.cend(),val);

传递给find的前两个参数是表示元素范围的迭代器，第三个参数是一个值。find将范围中每个元素与给定值进行比较。它返回指向第一个等于给定值的元素的迭代器。如果范围中无匹配元素，则find返回第二个参数来表示搜索失败。因此，我们可以通过比较返回值和第二个参数来判断搜索是否成功。

由于find操作的是迭代器，因此我们可以用同样的find函数在任何容器中查找值。例如，可以用find在一个string的list中查找一个给定值：

string val="a value";
auto result=find(lst.cbegin(),lst.cend(),val);

类似的，由于指针就像内置数组上的迭代器一样，我们可以用find在数组中查找值：

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]中查找指定的元素：

auto result=find(ia+1,ia+4;val);

算法如何工作

为了弄清这些算法如何用于不同类型的容器，让我们来观察一下find。find的工作是在一个未排序的元素序列中查找一个特定的元素。概念上，find应该执行如下步骤：

1 访问序列中的首元素

2 比较此元素与我们要查找的值

3 如果此元素与我们要查找的值匹配，find返回标识此元素的值。

4 否则，find前进到下一个元素，重复执行步骤2和3

5 如果到达序列尾，find应停止

6 如果find到达序列尾，它应该返回一个指出元素未找到的值。此值和步骤3返回的值必须具有相容的类型。

这些步骤都不依赖于容器所保存的元素类型。因此，只要有一个迭代器可用来访问元素，find就完全不依赖于容器类型（甚至无须理会保存元素的是不是容器）。

迭代器令算法不依赖于容器，但算法依赖于元素类型的操作

虽然迭代器的使用令算法不依赖于容器类型。但大多数算法都使用了一个(或多个)元素类型上的操作。例如，在步骤2中，find用元素的==运算符完成每个元素与给定值的比较。其他算法可能要求元素类型支持<运算符。不过，我们将会看到，大多数算法提供了一种方法，允许我们使用自定义的操作来代替默认的运算符。

注意：算法永远不会执行容器的操作

泛型算法本身不会执行容器的操作，它们只会运行与迭代器之上，执行迭代器的操作。泛型算法运行于迭代器之上而不会执行容器操作的特性带来了一个令人惊讶但非常必要的编程假定：算法永远不会改变底层容器的大小。算法可能改变容器中保存的元素的值，也可能在容器内移动元素，但永远不会直接添加或删除元素。

初始泛型算法

除了少数例外，标准库算法都对一个范围内的元素进行操作。我们将此元素范围称为“输入范围”。接受输入范围的算法总是使用前两个参数来表示此范围，两个参数分别是指想要处理的第一个元素和尾元素之后位置的迭代器。

虽然大多数算法遍历输入范围的方式相似，但它们使用范围中元素的方式不同。理解算法的最基本的方法就是了解它们是否读取元素、改变元素、或是重排元素顺序。

只读算法

一些算法只会读取其输入范围内的元素，而从不改变元素。find就是这样一种算法。

另一个只读算法是accumulate，它定义在头文件numeric中。accumulate函数接受三个参数，前两个指出了需要求和的元素的范围，第三个参数是和的初值。假定vec是一个整数序列，则：

//对vec中元素的求和，和的初值是0
int sum=accumulate(vec.cbegin(),vec.cend(),0);

这条语句将sum设置为vec中元素的和，和的初值被设置为0.

accumulate的第三个参数的类型决定了函数中使用哪个加法运算符以及返回值的类型。

算法和元素类型

accumulate将第三个参数作为求和起点，这蕴含着一个编程假定：将元素类型加到和的类型上的操作必须是可行的。即，序列中元素的类型必须与第三个参数匹配，或者能够转换为第三个参数的类型。在上例中，vec中的元素可以是int，或者是double、long long或任何其他可以加到int上的类型。

下面是另一个例子，由于string定义了+运算符，所有我们可以通过调用accumulate来将vector中所有string元素连接起来“

string sum=accumulate(v.cbegin(),v.cend(),string(“”));

此调用将v中每个元素连接到一个string上，该string初始时是空串。注意，我们通过第三个参数显式地创建了一个string。将空串当做一个字符串字面值传递给第三个参数是不可以的，会导致一个编译错误。

//错误：const char*上没有定义+运算符
string sum=accumulate(v.cbegin(),v.cend(),"");

原因在于，如果我们传递了一个字符串字面值，用于保存和的对象的类型将是const char。如前所述，此类型决定了使用哪个+运算符。由于const char并没有+运算符，此调用将产生编译错误。

操作两个序列的算法

另一个只读算法是equal，用于确定两个序列是否保存相同的值，它将第一个序列中的每个元素与第二个序列中的对应元素进行比较。如果所有对应元素都相等，则返回true，否则返回false。此算法接受三个迭代器：前两个表示第一个序列中的元素的范围，第三个表示第二个序列的首元素：

//roster2中的元素数目应该至少与roster1一样多
equal(roster1.cbegin(),roster1.cend(),roster2.cbegin());

由于equal利用迭代器完成操作，因此我们可以通过调用equal来比较两个不同类型的容器中的元素。而且，元素类型也不必一样，只要我们能用==来比较两个元素类型即可。例如，在此例中，roster1可以是vector,而roster2是list。

但是，equal基于一个非常重要的假设：它假定第二个序列至少与第一个序列一样长。 此算法要处理第一个序列中的每个元素，它假定每个元素在第二个序列中都有一个与之对应的元素。

写容器元素的算法

一些算法将新值赋予序列中的元素。当我们使用这类算法时，必须注意确保序列原大小至少不小于我们要求算法写入的元素数目。记住，算法不会执行容器操作，因此它们自身不可能改变容器的大小。

一些算法会自己向输入范围写入元素，这些算法本质上并不危险，它们最多写入与给定序列一样多的元素。

例如，算法fill接受一对迭代器表示一个范围，还接受一个值作为第三个参数。fill将给定的这个值赋予输入序列中的每个元素。

fill(vec.begin(),vec.end(),0); //将每个元素重置为0
//将容器的一个子序列设置为10
fill(vec.begin(),vec.begin()+vec.size()/2,10);

由于fill向给定输入序列中写入数据，因此，只要我们传递一个有效的输入序列，写入操作就是安全的。

关键概念：迭代器参数

一些算法从两个序列中读取元素。构成这两个序列的元素可以来自于不同类型的容器。例如，第一个序列可能保存于一个vector中，而第二个序列可能保存于一个list、deque、内置数组或其它容器中。而且，两个序列中元素的类型也不要求严格匹配。算法要求的只是能够比较两个序列中的元素。例如，对equal算法，元素类型不要求相同，但是我们必须能使用==来比较来自两个序列中的元素。

操作两个序列的算法之间的区别在于我们如何传递第二个序列。一些算法，例如equal，接受三个迭代器：前两个表示一个序列的范围，第三个表示第二个序列中的首元素。其他算法接受四个迭代器：前两个表示第一个序列的元素范围，后两个表示第二个序列的范围。

用一个单一迭代器表示第二个序列的算法都假定第二个序列至少与第一个一样长。确保算法不会试图访问第二个序列中不存在的元素是程序员的责任。

算法不检查写操作

一些算法接受一个迭代器来指出一个单独的目的位置。这些算法将新值赋予一个序列中的元素，该序列从目的位置迭代器指向的元素开始。例如，函数fill_n接受一个单迭代器、一个计数值和一个值。它将给定值赋予迭代器指向的元素开始的指定个元素。我们可以用fill_n将一个新值赋予vector中的元素：

vector<int> vec;  //空vector
//使用vec，赋予它不同值
fill_n(vec.begin(),vec.size(),0);  //将所有元素重置为0

函数fill_n假定写入指定个元素是安全的。即，如下形式的调用

fill_n(dest,n,val)

函数fill_n假定dest指向一个元素，而dest开始的序列至少包含n个元素。

一个初学者非常容易犯的错误是在一个空容器上调用fill_n（或类似的写元素的算法）：

vector<int> vec;  //空向量
//灾难：修改vec中10个（不存在）元素
fill_n(vec.begin(),10,0);

这个调用是一场灾难，我们指定了要写入10个元素，但vec中并没有元素——它是空的，这条语句的结果是未定义的。

向目的迭代器写入数据的算法假定目的位置是足够大，能容纳要写入的元素。

介绍back_inserter

一种保证算法有足够元素空间来容纳输出数据的方法是使用插入迭代器。插入迭代器（insert iterator） 是一种向容器中添加元素的迭代器。通常情况下，当我们通过一个迭代器向容器元素赋值时，值被赋予迭代器指向的元素。而当我们通过一个插入迭代器赋值时，一个赋值号右侧值相等的元素被添加到容器中。

为了展示如何用算法向容器中写入数据，我们现在将使用back_inserter，它是定义在头文件iterator中的一个函数。

back_inserter接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器。当我们通过此迭代器赋值时，赋值运算符会调用push_back将一个具有给定值的元素添加到容器中：

vector<int> vec;   //空容器
auto it=back_inserter(vec); //通过它赋值会将元素添加到vec中
*it=42;//vec现在有一个元素，值为42

我们常常使用back_inserter来创建一个迭代器，作为算法的目的位置来使用。例如：

vector<int> vec;  //空向量
//正确：back_inserter创建一个插入迭代器，可以用来向vec添加元素
fill_n(back_inserter(vec),10,0);  //添加10个元素到vec

在每步迭代中，fill_n向给定容器序列的一个元素赋值。由于我们传递的参数是back_inserter返回的迭代器，因此每次赋值都会在vec上调用push_back。最终，这条fill_n调用语句向vec的末尾添加了10个元素，每个元素的值都是0.

拷贝算法

拷贝算法是另一个向目的位置迭代器指向的输出序列中的元素写入数据的算法。此算法接受三个迭代器，前两个表示一个输入范围，第三个表示目的序列的起始位置。此算法将输入范围中的元素拷贝到目的序列中。传递给copy的目的序列至少要包含与输入序列一样多的元素，这一点很重要。

我们可以用copy实现内置数组的拷贝，如下面代码所示：

int a[]={0,1,2,3,4,5,6,7,8,9};
int a2[sizeof(a1)/sizeof(*a1)];
auto ret=copy(begin(a1),end(a1),a2); //把a1的内容拷贝到a2

copy返回的是其目的位置迭代器（递增后）的值。即，ret恰好指向拷贝到a2的尾元素之后的位置。

多个算法都提供所谓的“拷贝”版本。这些算法计算新元素的值，但不会将它们放置在输入序列的末尾，而是创建以新序列保存这些结果。

例如，replace算法读入一个序列，并将其中所有等于给定值的元素都改为另一个值。此算法接受4个参数：前两个是迭代器，表示输入序列，后两个一个是要搜索的值，另一个是新值。它将所有等于第一个值的元素替换为第二个值：

//将所有值为0的元素改为42
replace(ilist.begin(),ilist.end(),0,42);

此调用将序列中所有0都替换为42,。如果我们希望保留原序列不变，可以调用replace_copy。此算法接受额外第三个迭代器参数，指出调整后序列的保存位置：

//使用back_inserter按需要增长目标序列
vector<int> ivec = {1,2,3,3,3,4,4,5,6,7};
vector<int> a;
replace_copy(ivec.cbegin(),ivec.cend(),back_inserter(a),4,19);

此调用后，ivec并未改变，a包含与ivec的一份拷贝，不过原来在ivec中值为0的元素在a中都变为42。

重排容器元素的算法

某些算法会重排容器中元素的顺序，一个明显的例子是sort。调用sort会重排输入序列中的元素，使之有序，它是利用元素类型的<运算符来实现排序的。

消除重复单词

为了消除重复单词，首先将vector排序，使得重复的单词都相邻出现。一旦vector排序完毕，我们就可以使用另一个称为unique的标准库算法来重排vector，使得不重复的元素出现在vector的开始部分（重复的元素都在末尾，返回指向不重复区域之后一个位置的迭代器），由于算法不能执行容器的操作，我们将使用vector的erase成员来完成真正的删除操作：

vector<string> words = {"to","be","or","not","not","to","be"};
//按字典序排序words,以便查找重复单词
sort(words.begin(),words.end());
//unique重排输入范围，使得每个单词只出现一次,重复的单词放在后面
//排列在范围的前部，返回指向不重复区域之后一个位置的迭代器
auto end_unique = unique(words.begin(),words.end());
//使用向量操作erase删除重复单词
words.erase(end_unique,words.end());

使用unique

words排序完毕后，我们希望将每个单词都只保存一次。unique算法重排输入序列，将相邻的重复项“消除”，并返回一个指向不重复范围末尾的迭代器。

words的大小并未改变，但是这些元素的顺序被改变了——相邻的重复元素被“删除”了。我们将删除打引号是因为unique并不真正的删除任何元素，它只是覆盖相邻的重复元素，使得不重复元素出现在序列开始部分，重复的元素出现在后面部分，unique返回的迭代器指向最后一个不重复元素之后的位置。此位置之后的元素仍然存在，但我们不知道它们的值是什么。

标准库算法对迭代器而不是容器进行操作。因此，算法不能（直接）添加或删除元素。

使用容器操作删除元素

为了真正删除无用元素，我们必须使用容器操作，本例中使用erase。我们删除从end_unique开始直至words末尾的范围内的所有元素。这个调用之后，words包含的重复元素真正被删除了。

值得注意的是，即使words中没有重复单词，这样调用erase也是安全的。在此情况下，unique会返回words.end()。因此，传递给erase的两个参数具有系相同的值：words.end()。迭代器相等意味着传递给erase的元素范围为空。删除一个空范围没有什么不良后果，因此程序中即使在输入元素中无重复元素的情况下也是正确的。