《C++ Primer 5th》笔记（10 / 19）：泛型算法

我会带着你远行 2023-01-22 08:53 14阅读 0赞

### 文章目录 ###

*   *  概述
     *   *  算法如何工作
         *  迭代器令算法不依赖于容器
         *  但算法依赖于元素类型的操作
         *  关键概念：算法永远不会执行容器的操作
     *  初识泛型算法
     *   *  只读算法
         *   *  算法和元素类型
             *  操作两个序列的算法
         *  写容器元素的算法
         *   *  关键概念：迭代器参数
             *  算法不检查写操作
         *  介绍back\_inserter
         *   *  拷贝算法
         *  重排容器元素的算法
         *   *  消除重复单词
             *  使用unique
             *  使用容器操作删除元素
     *  定制操作（lambda）
     *   *  向算法传递函数
         *   *  谓词
             *  排序算法
         *  lambda表达式
         *   *  介绍lambda
             *  向lambda传递参数
             *  使用捕获列表
             *  调用find\_ if
             *  for\_each算法
             *  完整的biggies
         *  lambda捕获和返回
         *   *  值捕获
             *  引用捕获
             *  建议：尽量保持lambda的变量捕获简单化
             *  隐式捕获
             *  可变lambda捕获值
             *  指定lambda返回类型
         *  参数绑定
         *   *  标准库bind函数
             *  绑定check\_size的sz参数
             *  使用placeholders名字（使用命名空间using namespace）
             *  bind的参数顺序
             *  用bind重排参数顺序（实例）
             *  绑定引用参数
             *  向后兼容：参数绑定
     *  再探迭代器
     *   *  插入迭代器
         *  iostream迭代器
         *   *  istream\_iterator操作
             *  使用算法操作流迭代器
             *  istream\_iterator允许使用懒惰求值
             *  ostream\_iterator操作
             *  使用流迭代器处理类类型
     *  泛型算法结构
     *   *  5类迭代器
         *   *  迭代器类别
         *  算法形参模式
         *   *  接受单个目标迭代器的算法
             *  接受第二个输入序列的算法
         *  算法命名规范
         *   *  一些算法使用重载形式传递一个谓词
             *  \\\_if版本的算法
             *  区分拷贝元素的版本和不拷贝的版本
     *  特定容器算法（链表）
     *   *  splice成员
         *  链表特有的操作会改变容器

顺序容器只定义了很少的操作：在多数情况下，我们可以

*  添加和删除元素、
 *  访问首尾元素、
 *  确定容器是否为空
 *  获得指向首元素或尾元素之后位置的迭代器。

我们可以想象用户可能还希望做其他很多有用的操作：

*  查找特定元素、
 *  替换或删除一个特定值、
 *  重排元素顺序
 *  …

标准库并未给每个容器都定义成员函数来实现这些操作，而是定义了一组**泛型算法**（generic algorithm），称它们为“算法”，是因为它们实现了一些经典算法的公共接口，如**排序**和**搜索**；称它们是“泛型的”，**是因为它们可以用于不同类型的元素和多种容器类型**（不仅包括标准库类型，如 vector或list，还包括内置的数组类型），以及我们将看到的，还能用于其他类型的序列。

## 概述 ##

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

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

int val = 42; // value we'll look for
    // result will denote the element we want if it's in vec, or vec.cend() if not
    auto result = find(vec.cbegin(), vec.cend(), val);
    // report the result
    cout << "The value " << val
        << (result == vec.cend()
        ? " is not present" : " is present") << endl;

传递给find 的前两个参数是表示元素范围的迭代器，第三个参数是一个值。find 将范围中每个元素与给定值进行比较。它返回指向第一个等于给定值的元素的迭代器。如果范围中无匹配元素，则find返回第二个参数来表示搜索失败。因此，我们可以通过比较返回值和第二个参数来判断搜索是否成功。我们在输出语句中执行这个检测，其中使用了条件运算符来报告搜索是否成功。

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

string val = "a value"; //我们要查找的值
    //此调用在list中查找string元素
    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\]中查找给定元素:

//在从ia[1]开始，直至（但不包含)ia[4]的范围内查找元素
    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就完全不依赖于容器类型（甚至无须理会保存元素的是不是容器）。

### 迭代器令算法不依赖于容器 ###

在上述find函数流程中，除了第2步外，其他步骤都可以用迭代器操作来实现：

*  利用迭代器解引用运算符可以实现元素访问;
 *  如果发现匹配元素，find可以返回指向该元素的迭代器;
 *  用迭代器递增运算符可以移动到下一个元素;
 *  尾后迭代器可以用来判断find是否到达给定序列的末尾;
 *  find可以返回尾后迭代器来表示未找到给定元素。

### 但算法依赖于元素类型的操作 ###

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

### 关键概念：算法永远不会执行容器的操作 ###

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

随后将介绍到，标准库定义了一类特殊的迭代器，称为**插入器**（inserter）。与普通迭代器只能遍历所绑定的容器相比，插入器能做更多的事情。当给这类迭代器赋值时，它们会在底层的容器上执行插入操作。因此，**当一个算法操作一个这样的迭代器时，迭代器可以完成向容器添加元素的效果，但算法自身永远不会做这样的操作**。

## 初识泛型算法 ##

标准库提供了超过100个算法。幸运的是，与容器类似，这些算法有一致的结构。比起死记硬背全部100多个算法，理解此结构可以帮助我们更容易地学习和使用这些算法。

在本章中，我们将展示如何使用这些算法，并介绍刻画了这些算法的统一原则。附录A按操作方式列出了所有算法。

除了少数例外，**标准库算法都对一个范围内的元素进行操作**。我们将此元素范围称为“输入范围”。接受输入范围的算法总是使用前两个参数来表示此范围，两个参数分别是指向要处理的第一个元素和尾元素之后位置的迭代器。  
虽然大多数算法遍历输入范围的方式相似，但它们使用范围中元素的方式不同。

理解算法的最基本的方法就是了解它们是否读取元素、改变元素或是重排元素顺序。

### 只读算法 ###

一些算法只会读取其输入范围内的元素，而从不改变元素。find就是这样一种算法。头文件algorithm种的count（返回给定值在序列中出现的次数）也是这样一种算法。

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

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

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

**Note**：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\*并没有+运算符，此调用将产生编译错误。

**Best Practices**：对于只读取而不改变元素的算法，通常最好使用cbegin()和cend()。但是，如果你计划使用算法返回的迭代器来改变元素的值，就需要使用begin()和end()的结果作为参数。

#### 操作两个序列的算法 ####

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

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

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

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

**WARNING**：那些只接受一个单一迭代器来表示第二个序列的算法，都假定第二个序列至少与第一个序列一样长。

### 写容器元素的算法 ###

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

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

例如，算法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，接受三个迭代器：前两个表示第一个序列的范围，第三个表示第二个序列中的首元素。其他算法接受四个迭代器：前两个表示第一个序列的元素范围，后两个表示第二个序列的范围。

**用一个单一迭代器表示第二个序列的算法都假定第二个序列至少与第一个一样长**。确保算法不会试图访问第二个序列中不存在的元素是程序员的责任。例如，算法 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中并没有元素——它是空的。这条语句的结果是未定义的。

Note：向目的位置迭代器写入数据的算法假定目的位置足够大，能容纳要写入的元素。（MyNote：量体裁衣。）

### 介绍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的目的序列至少要包含与输入序列一样多的元素，这一点很重要。

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

int a1[] = {  0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int a2[sizeof(a1) / sizeof(*a1)];//a2与a1大小一样
    //ret指向拷贝到a2的尾元素之后的位置
    auto ret = copy(begin(a1), end(a1), a2); //把a1的内容拷贝给a2

此例中我们定义了一个名为a2的数组，并使用sizeof确保a2与数组a1包含同样多的元素。接下来我们调用copy 完成从 a1到a2的拷贝。在调用copy后，两个数组中的元素具有相同的值。

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

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

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

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

此调用将序列中所有的0都替换为42。

如果我们希望保留原序列不变，可以调用**replace\_copy**。此算法接受额外第三个迭代器参数，指出调整后序列的保存位置：

//使用back_inserter按需要增长目标序列
    replace_copy(ilst.cbegin(), ilst.cend(),
    		back_inserter(ivec), 0, 42);

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

### 重排容器元素的算法 ###

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

例如，假定我们想分析一系列儿童故事中所用的词汇。假定已有一个vector，保存了多个故事的文本。我们希望化简这个vector，使得每个单词只出现一次，而不管单词在任意给定文档中到底出现了多少次。

为了便于说明问题，我们将使用下面简单的故事作为输入：

the quick red fox jumps over the slow red turtle

给定此输入，我们的程序应该生成如下vector：

<table> 
 <thead> 
  <tr> 
   <th>fox</th> 
   <th>jumps</th> 
   <th>over</th> 
   <th>quick</th> 
   <th>red</th> 
   <th>slow</th> 
   <th>the</th> 
   <th>turtle</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

#### 消除重复单词 ####

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

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

sort算法接受两个迭代器，表示要排序的元素范围。在此例中，我们排序整个vector。完成sort后，words的顺序如下所示：

<table> 
 <thead> 
  <tr> 
   <th>fox</th> 
   <th>jumps</th> 
   <th>over</th> 
   <th>quick</th> 
   <th>red</th> 
   <th>red</th> 
   <th>slow</th> 
   <th>the</th> 
   <th>the</th> 
   <th>turtle</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

注意，单词red和 the各出现了两次。

#### 使用unique ####

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

<table> 
 <thead> 
  <tr> 
   <th>fox</th> 
   <th>jumps</th> 
   <th>over</th> 
   <th>quick</th> 
   <th>red</th> 
   <th>slow</th> 
   <th>the</th> 
   <th>turtle</th> 
   <th>？？？</th> 
   <th>？？？</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td>↑<br>end_unique<br>(最后一个不重复元素之后的位置)</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

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

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

#### 使用容器操作删除元素 ####

为了真正地删除无用元素，我们必须使用容器操作，本例中使用erase。我们删除从end\_unique开始直至words末尾的范围内的所有元素。这个调用之后，words包含来自输入的8个不重复的单词。

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

## 定制操作（lambda） ##

很多算法都会比较输入序列中的元素。默认情况下，这类算法使用元素类型的<或==运算符完成比较。标准库还为这些算法定义了额外的版本，允许我们提供自己定义的操作来代替默认运算符。

例如，sort算法默认使用元素类型的 < 运算符。但可能我们希望的排序顺序与<所定义的顺序不同，或是我们的序列可能保存的是未定义 < 运算符的元素类型（如Sales\_data）。在这两种情况下，都需要重载sort的默认行为。

### 向算法传递函数 ###

作为一个例子，假定希望在调用elimDups（在上一章）后打印vector的内容。此外还**假定希望单词按其长度排序，大小相同的再按字典序排列**。为了按长度重排vector，我们将使用sort的第二个版本，此版本是重载过的，它接受第三个参数，此参数是一个**谓词**（predicate）。

#### 谓词 ####

谓词是一个可调用的表达式，其返回结果是一个能用作条件的值。标准库算法所使用的谓词分为两类：

1.  一元谓词（unary predicate，意味着它们只接受单一参数）
2.  二元谓词（binary predicate，意味着它们有两个参数）

接受谓词参数的算法对输入序列中的元素调用谓词。因此，元素类型必须能转换为谓词的参数类型。

接受一个二元谓词参数的sort版本用这个谓词代替 < 来比较元素。当前，我们只需知道，此操作必须在输入序列中所有可能的元素值上定义一个一致的序。在第6章中定义的 isShorter就是一个满足这些要求的函数，因此可以将isShorter传递给sort。这样做会将元素按大小重新排序：

//比较函数，用来按长度排序单词
    bool isShorter(const string &s1, const string &s2){ 
    	return s1.size() < s2.size();
    }

//按长度由短至长排序words
    sort(words.begin() ,words.end(), isShorter);

调用sort会将words重排，使得所有长度为3的单词排在长度为4的单词之前，然后是长度为5的单词，依此类推。

#### 排序算法 ####

在我们将words按长度大小重排的同时，还希望具有相同长度的元素按字典序排列。为了保持相同长度的单词按字典序排列，可以使用stable\_sort算法。这种稳定排序算法维持相等元素的原有顺序。

通常情况下，我们不关心有序序列中相等元素的相对顺序，它们毕竟是相等的。但是，在本例中，我们定义的“相等”关系表示“具有相同长度”。而具有相同长度的元素，如果看其内容，其实还是各不相同的。通过调用stable\_sort，可以保持等长元素间的字典序：

elimDups(words); //将words按字典序重排，并消除重复单词
    //按长度重新排序，长度相同的单词维持字典序
    stable_sort(words.begin(), words.end() ,isShorter);
    for(const auto &s : words) //无须拷贝字符串
    	cout << s << "" ; //打印每个元素，以空格分隔
    cout << endl;

假定在此调用前words是按字典序排列的，则调用之后，words会按元素大小排序，而长度相同的单词会保持字典序。如果我们对原来的vector内容运行这段代码，输出为：

fox red the over slow jumps quick turtle

### lambda表达式 ###

根据算法接受一元谓词还是二元谓词，我们传递给算法的谓词必须严格接受一个或两个参数。但是，有时我们希望进行的操作需要更多参数，超出了算法对谓词的限制。

一个相关的例子是，我们将修改上一节的程序，**求大于等于一个给定长度的单词有多少。我们还会修改输出，使程序只打印大于等于给定长度的单词**。(设计目标)

我们将此函数命名为biggies，其框架如下所示：

void biggies(vector<string> &words, vector<string>::size_type sz)
    { 
        elimDups(words); // put words in alphabetical order and remove duplicates
        // resort by length, maintaining alphabetical order among words of the same length
        stable_sort(words.begin(), words.end(), isShorter);
        // get an iterator to the first element whose size() is >= sz
        // compute the number of elements with size >= sz
        // print words of the given size or longer, each one followed by a space
    }

我们的新问题是在vector中寻找第一个大于等于给定长度的元素。一旦找到了这个元素，根据其位置，就可以计算出有多少元素的长度大于等于给定值。

我们可以使用标准库 find\_if 算法来查找第一个具有特定大小的元素。类似find，find\_if算法接受一对迭代器，表示一个范围。但与find不同的是，find\_if的第三个参数是一个谓词。find\_if 算法对输入序列中的每个元素调用给定的这个谓词。它返回第一个使谓词返回非О值的元素，如果不存在这样的元素，则返回尾迭代器。

编写一个函数，令其接受一个string 和一个长度，并返回一个bool值表示该string的长度是否大于给定长度，是一件很容易的事情。但是，find\_if接受一元谓词——我们传递给 find\_if的任何函数都必须严格接受一个参数，以便能用来自输入序列的一个元素调用它。没有任何办法能传递给它第二个参数来表示长度。为了解决此问题，需要使用另外一些语言特性。

#### 介绍lambda ####

我们可以向一个算法传递任何类别的**可调用对象**（callable object）。**对于一个对象或一个表达式，如果可以对其使用调用运算符，则称它为可调用的**。即，如果e是一个可调用的表达式，则我们可以编写代码e(args)，其中args是一个逗号分隔的一个或多个参数的列表。

到目前为止，我们使用过的仅有的两种可调用对象是

1.  函数
2.  函数指针。

还有其他两种可调用对象：

1.  重载了函数调用运算符的类（第14章介绍）
2.  lambda表达式（lambda expression）。

一个lambda表达式表示一个可调用的代码单元。**我们可以将其理解为一个未命名的内联函数**。与任何函数类似，一个lambda具有一个返回类型、一个参数列表和一个函数体。但与函数不同，lambda可能定义在函数内部。一个lambda表达式具有如下形式

[capture list](parameter list) -> return type {  function body }

其中，

1.  capture list（捕获列表）是一个lambda所在函数中定义的局部变量的列表（通常为空）；
2.  return type、parameter list和 function body与任何普通函数一样，分别表示返回类型、参数列表和函数体。

但是，与普通函数不同，lambda必须使用**尾置返回**来指定返回类型。

> **尾置返回类型**（ trailing return type）。任何函数的定义都能使用尾置返回，但是这种形式对于返回类型比较复杂的函数最有效，比如返回类型是数组的指针或者数组的引用。尾置返回类型跟在形参列表后面并以一个->符号开头。为了表示函数真正的返回类型跟在形参列表之后，我们在本应该出现返回类型的地方放置一个auto：
> 
>     //func接受一个int类型的实参，返回一个指针，该指针指向含有10个整数的数组
>     auto func(int i) -> int (*)[10];
> 
> 来自第6章

我们可以忽略参数列表和返回类型，但必须永远包含捕获列表和函数体

auto f = []{  return 42;};

此例中，我们定义了一个可调用对象f，它不接受参数，返回42。

lambda 的调用方式与普通函数的调用方式相同，都是使用调用运算符：

cout << f() << endl;//打印42

在lambda中忽略括号和参数列表等价于指定一个空参数列表。在此例中，当调用f时，参数列表是空的。如果忽略返回类型，lambda根据函数体中的代码推断出返回类型。

如果函数体只是一个return语句，则返回类型从返回的表达式的类型推断而来。否则，返回类型为void。

**Note**：如果 lambda 的函数体包含任何单一 return语句之外的内容，且未指定返回类型,则返回void。

#### 向lambda传递参数 ####

与一个普通函数调用类似，调用一个lambda时给定的实参被用来初始化lambda的形参。通常，实参和形参的类型必须匹配。但与普通函数不同，lambda不能有默认参数。因此，一个lambda调用的实参数目永远与形参数目相等。一旦形参初始化完毕，就可以执行函数体了。

作为一个带参数的 lambda 的例子，我们可以编写一个与 isshorter 函数完成相同功能的 lambda：

[](const string &a, const string &b){ return a.size() < b.size();}

空捕获列表表明此lambda不使用它所在函数中的任何局部变量。lambda 的参数与isShorter 的参数类似，是const string 的引用。lambda 的函数体也与isShorter类似，比较其两个参数的size ( )，并根据两者的相对大小返回一个布尔值。

使用此 lambda来调用stable\_sort的示例：

//按长度排序，长度相同的单词维持字典序
    stable_sort(words.begin(), words.end(),
    	[](const string &a, const string &b){ return a.size() < b.size();});

当stable\_sort需要比较两个元素时，它就会调用给定的这个lambda表达式。

#### 使用捕获列表 ####

我们现在已经准备好解决原来的问题了——编写一个可以传递给find\_if的可调用表达式。我们希望这个表达式能将输入序列中每个string 的长度与biggies函数中的sz参数的值进行比较。

虽然一个lambda可以出现在一个函数中，使用其局部变量，但它只能使用那些明确指明的变量。**一个lambda通过将局部变量包含在其捕获列表中来指出将会使用这些变量**。捕获列表指引lambda在其内部包含访问局部变量所需的信息。

在本例中，我们的 lambda会捕获sz，并只有单一的 string 参数。其函数体会将string的大小与捕获的sz的值进行比较：

[sz](const string &a)
    	{ return a.size() >= sz;};

lambda以一对\[\]开始，我们可以在其中提供一个以逗号分隔的名字列表，这些名字都是它所在函数中定义的。

由于此lambda捕获sz，因此lambda的函数体可以使用sz。lambda不捕获words，因此不能访问此变量。如果我们给lambda提供一个空捕获列表，则代码会编译错误：

//错误:sz未捕获
    [](const string &a)
    	{ return a.size() >= sz;};

**Note：一个lambda只有在其捕获列表中捕获一个它所在函数中的局部变量，才能在函数体中使用该变量。**

#### 调用find\_ if ####

使用此lambda，我们就可以查找第一个长度大于等于sz的元素:

//获取一个迭代器，指向第一个满足size() >= sz的元素
    auto wc = find_if(words.begin(), words.end(),
    	[sz](const string &a)
    		{ return a.size() >= sz; });

这里对find\_ if 的调用返回一个迭代器，指向第一个长度不小于给定参数sz的元素。如果这样的元素不存在，则返回words.end()的一个拷贝。

我们可以使用find\_ if返回的迭代器来计算从它开始到words的末尾一共有多少个元素：

//计算满足size >= sz的元素的数目
    auto count = words.end() - wc;
    cout << count << " " << make_plural(count, "word", "s")
    	<< "of length" << sz << ”or longer" << endl;

我们的输出语句调用make\_ plural（第6章内容）来输出"word"或"words"，具体输出哪个取决于大小是否等于1。

#### for\_each算法 ####

问题的最后一部分 是打印words中长度大于等于sz的元素。为了达到这一目的， 我们可以使用for\_each算法。此算法接受一个可调用对象，并对输入序列中每个元素调用此对象：

//打印长度大于等于给定值的单词，每个单词后面接一个空格
    for_each(wc, words.end(),
    		[](const string &s) { cout << s << "";});
    cout << endl;

此lambda中的捕获列表为空，但其函数体中还是使用了两个名字: s和cout，前者是它自己的参数。

捕获列表为空，是因为我们只对lambda所在函数中定义的（非static）变量使用捕获列表。一个lambda可以直接使用定义在当前函数之外的名字。在本例中，cout不是定义在biggies中的局部名字，而是定义在头文件iostream中。因此，只要在biggies出现的作用域中包含了头文件iostream，我们的lambda就可以使用cout。

**Note：捕获列表只用于局部非static变量，lambda可以直接使用局部static变量和在它所在函数之外声明的名字。**

#### 完整的biggies ####

//求大于等于一个给定长度的单词有多少。我们还会修改输出，使程序只打印大于等于给定长度的单词
    void biggies(vector<string> &words,
    				vector<string>::size_type sz)
    { 
        elimDups(words); // put words in alphabetical order and remove duplicates
        // sort words by size, but maintain alphabetical order for words of the same size
        stable_sort(words.begin(), words.end(),
    			    [](const string &a, const string &b)
    				    {  return a.size() < b.size();});
    
        // get an iterator to the first element whose size() is >= sz
        auto wc = find_if(words.begin(), words.end(),
    				    [sz](const string &a)
    					    {  return a.size() >= sz; });
    
        // compute the number of elements with size >= sz
        auto count = words.end() - wc;
        cout << count << " " << make_plural(count, "word", "s")
        	<< " of length " << sz << " or longer" << endl;
    
        // print words of the given size or longer, each one followed by a space
        for_each(wc, words.end(),
        				[](const string &s){ cout << s << " ";});
        cout << endl;
    }

### lambda捕获和返回 ###

当定义一个lambda时，编译器生成一个与lambda对应的新的（未命名的）类类型。我们将在第14章介绍这种类是如何生成的。

目前，可以这样理解，**当向一个函数传递一个lambda 时，同时定义了一个新类型和该类型的一个对象**：传递的参数就是此编译器生成的类类型的未命名对象。类似的，当使用auto定义一个用lambda初始化的变量时，定义了一个从lambda生成的类型的对象。

默认情况下，从lambda生成的类都包含一个对应该lambda所捕获的变量的数据成员。类似任何普通类的数据成员，lambda的数据成员也在 lambda对象创建时被初始化。

#### 值捕获 ####

类似参数传递，变量的捕获方式也可以是值或引用。下列出了几种不同的构造捕获列表的方式。

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>[]</td> 
   <td>空捕获列表。lambda不能使用所在函数中的变量。一个lambda只有捕获变量后才能使用它们</td> 
  </tr> 
  <tr> 
   <td>[names]</td> 
   <td>names是一个逗号分隔的名字列表，这些名字都是lambda所在函数的局部变量。默认情况下，捕获列表中的变量都被拷贝。名字前如果使用了&amp;，则采用引用捕获方式</td> 
  </tr> 
  <tr> 
   <td>[&amp;]</td> 
   <td>隐式捕获列表，采用引用捕获方式。lambda体中所使用的来自所在函数的实体都采用引用方式使用</td> 
  </tr> 
  <tr> 
   <td>[=]</td> 
   <td>隐式捕获列表，采用值捕获方式。lambda体将拷贝所使用的来自所在函数的实体的值</td> 
  </tr> 
  <tr> 
   <td>[&amp;, identifier_list]</td> 
   <td>identifier_list是一个逗号分隔的列表，包含0个或多个来自所在函数的变量。这些变量采用值捕获方式，而任何隐式捕获的变量都采用引用方式捕获。identifier_list中的名字前面不能使用&amp;</td> 
  </tr> 
  <tr> 
   <td>[=, identifier_list]</td> 
   <td>identifier_list中的变量都采用引用方式捕获,而任何隐式捕获的变量都采用值方式捕获。identifier_list中的名字不能包括this，且这些名字之前必须使用&amp;</td> 
  </tr> 
 </tbody> 
</table>

到目前为止，我们的 lambda采用**值捕获**的方式。与传值参数类似，采用值捕获的前提是变量可以拷贝。与参数不同，被捕获的变量的值是在lambda创建时拷贝，而不是调用时拷贝：

void fcn1(){ 
    	size_t v1 = 42; //局部变量
        //将v1拷贝到名为f的可调用对象
    	auto f = [v1] { return v1;};
    	v1 = 0 ;
    	auto j = f(); // j为42;f保存了我们创建它时v1的拷贝
    }

由于被捕获变量的值是在 lambda创建时拷贝，因此随后对其修改不会影响到lambda内对应的值。

#### 引用捕获 ####

void fcn2()
    { 
        size_t v1 = 42; // local variable
        // the object f2 contains a reference to v1
        auto f2 = [&v1] {  return v1; };
        v1 = 0;
        auto j = f2(); // j is 0; f2 refers to v1; it doesn't store it
    }

v1之前的&指出v1应该以引用方式捕获。**一个以引用方式捕获的变量与其他任何类型的引用的行为类似**。当我们在lambda函数体内使用此变量时，实际上使用的是引用所绑定的对象。在本例中，当lambda返回v1时，它返回的是v1指向的对象的值。

引用捕获与返回引用有着相同的问题和限制。如果我们采用引用方式捕获一个变量，就必须确保被引用的对象在lambda执行的时候是存在的。lambda捕获的都是局部变量，这些变量在函数结束后就不复存在了。如果 lambda可能在函数结束后执行，捕获的引用指向的局部变量已经消失。

引用捕获有时是必要的。例如，我们可能希望biggies函数接受一个ostream 的引用，用来输出数据，并接受一个字符作为分隔符：

void biggies(vector<string> &words,
                vector<string>::size_type sz,
                ostream &os = cout, char c = ' ')
    { 
        // code to reorder words as before
        // statement to print count revised to print to os
        for_each(words.begin(), words.end(),
        		[&os, c](const string &s) {  os << s << c; });
    }

我们**不能拷贝ostream对象**，因此捕获os 的唯一方法就是捕获其引用（或指向os的指针）。

当我们向一个函数传递一个lambda 时，就像本例中调用for\_each那样，lambda会立即执行。在此情况下，以引用方式捕获 os 没有问题，因为当for\_each 执行时，biggies 中的变量是存在的。

我们也可以从**一个函数返回lambda**。函数可以直接返回一个可调用对象，或者返回一个类对象，该类含有可调用对象的数据成员。如果函数返回一个lambda，则与函数不能返回一个局部变量的引用类似，此lambda也不能包含引用捕获。

**WARNING**：当以引用方式捕获一个变量时，必须保证在lambda执行时变量是存在的。

#### 建议：尽量保持lambda的变量捕获简单化 ####

一个 lambda捕获从lambda被创建（即，定义 lambda的代码执行时）到 lambda自身执行（可能有多次执行）这段时间内保存的相关信息。确保lambda每次执行的时候这些信息都有预期的意义，是程序员的责任。

捕获一个普通变量，如int、string或其他非指针类型，通常可以采用简单的**值捕获**方式。在此情况下，只需关注变量在捕获时是否有我们所需的值就可以了。

如果我们捕获一个指针或迭代器，或采用引用捕获方式，就必须确保在lambda执行时，绑定到迭代器、指针或引用的对象仍然存在。而且，需要保证对象具有预期的值。在lambda从创建到它执行的这段时间内,可能有代码改变绑定的对象的值。也就是说，在指针(或引用）被捕获的时刻，绑定的对象的值是我们所期望的，但在 lambda执行时，该对象的值可能已经完全不同了。

**一般来说，我们应该尽量减少捕获的数据量，来避免潜在的捕获导致的问题。而且，如果可能的话，应该避免捕获指针或引用。**

#### 隐式捕获 ####

除了显式列出我们希望使用的来自所在函数的变量之外，还可以让编译器根据lambda体中的代码来**推断**我们要使用哪些变量。为了指示编译器推断捕获列表，应在捕获列表中写一个&或=。&告诉编译器采用捕获引用方式，=则表示采用值捕获方式。例如，我们可以重写传递给find\_if的lambda：

// sz implicitly captured by value
    wc = find_if(words.begin(), words.end(),
                [=](const string &s)
                	{  return s.size() >= sz; });

如果我们希望对一部分变量采用值捕获，对其他变量采用引用捕获，可以**混合**使用隐式捕获和显式捕获：

void biggies(vector<string> &words,
                    vector<string>::size_type sz,
                    ostream &os = cout, char c = ' ')
    { 
        // other processing as before
        // os implicitly captured by reference; c explicitly captured by value
        for_each(words.begin(), words.end(),
        			[&, c](const string &s) {  os << s << c; });
        // os explicitly captured by reference; c implicitly captured by value
        for_each(words.begin(), words.end(),
        			[=, &os](const string &s) {  os << s << c; });
    }

当我们混合使用隐式捕获和显式捕获时，捕获列表中的第一个元素**必须**是一个&或=。此符号指定了默认捕获方式为引用或值。

当混合使用隐式捕获和显式捕获时，显式

捕获的变量必须使用与隐式捕获不同的方式。即，如果隐式捕获是**引用方式**（使用了&），则显式捕获命名变量必须采用**值方式**，因此不能在其名字前使用&。类似的，如果隐式捕获采用的是**值方式**（使用了=），则显式捕获命名变量必须采用**引用方式**，即，在名字前使用&。

#### 可变lambda捕获值 ####

默认情况下，对于一个值被拷贝的变量，lambda不会改变其值。如果我们希望能改变一个被捕获的变量的值，就必须在参数列表首加上关键字mutable。因此，可变lambda能省略参数列表：

void fcn3()
    { 
        size_t v1 = 42; // local variable
        // f can change the value of the variables it captures
        auto f = [v1] () mutable {  return ++v1; };
        v1 = 0;
        auto j = f(); // j is 43
    }

> mutable  
> 英 \[ˈmjuːtəbl\] 美 \[ˈmjuːtəbl\]  
> adj. 可变的;会变的

一个引用捕获的变量是否（如往常一样）可以修改依赖于此引用指向的是一个const类型还是一个非const类型：

void fcn4()
    { 
        size_t v1 = 42; // local variable
        // v1 is a reference to a non const variable
        // we can change that variable through the reference inside f2
        auto f2 = [&v1] {  return ++v1; };
        v1 = 0;
        auto j = f2(); // j is 1
    }

#### 指定lambda返回类型 ####

到目前为止，我们所编写的lambda都只包含单一的return语句。因此，我们还未遇到必须指定返回类型的情况。**默认情况下，如果一个lambda体包含return之外的任何语句，则编译器假定此lambda返回void**。与其他返回void的函数类似，被推断返回void的lambda不能返回值。

下面给出了一个简单的例子，我们可以使用标准库transform算法和一个lambda来将一个序列中的每个负数替换为其绝对值：

transform (vi.begin() ,vi.end() ,vi.begin(),
    		[](int i){  return i < 0 ? -i : i;});

函数transform接受三个迭代器和一个可调用对象。前两个迭代器表示输入序列，第三个迭代器表示目的位置。

算法对输入序列中每个元素调用可调用对象，并将结果写到目的位置。如本例所示，目的位置迭代器与表示输入序列开始位置的迭代器可以是相同的。当输入迭代器和目的迭代器相同时，transform 将输入序列中每个元素替换为可调用对象操作该元素得到的结果。

在本例中，我们传递给transform 一个lambda，它返回其参数的绝对值。lambda体是单一的return语句，返回一个条件表达式的结果。我们无须指定返回类型，因为可以根据条件运算符的类型推断出来。

但是，如果我们将程序改写为看起来是等价的if语句，就会**产生编译错误**：

//错误:不能推断lambda的返回类型
    transform (vi.begin(), vi.end(), vi.begin(),
    	[](int i){  if (i< 0) return -i; else return i; ));

编译器推断这个版本的lambda返回类型为void，但它返回了一个int值。

当我们需要为一个lambda定义返回类型时，必须使用**尾置返回类型**（第6章内容)：

transform (vi.begin() ,vi.end() ,vi.begin() ,
    			[](int i) -> int
    			 {  if (i < 0) return -i; else return i; });

在此例中，传递给transform的第四个参数是一个lambda，它的捕获列表是空的，接受单一int参数，返回一个int值。它的函数体是一个返回其参数的绝对值的if语句。

### 参数绑定 ###

对于那种只在一两个地方使用的简单操作，lambda表达式是最有用的。如果我们需要在很多地方使用相同的操作，通常应该定义一个函数，而不是多次编写相同的 lambda表达式。类似的，如果一个操作需要很多语句才能完成，通常使用函数更好。

如果 lambda的捕获列表为空，通常可以用函数来代替它。如前面章节所示，既可以用一个lambda，也可以用函数isShorter来实现将vector中的单词按长度排序。类似的，对于打印 vector内容的lambda，编写一个函数来替换它也是很容易的事情，这个函数只需接受一个string并在标准输出上打印它即可。

（MyNote：谈论使用lambda、函数的时机。）

但是，对于捕获局部变量的lambda，用函数来替换它就不是那么容易了。例如，我们用在find\_if调用中的 lambda比较一个string和一个给定大小。我们可以很容易地编写一个完成同样工作的函数:

bool check_size(const string &s, string::size_type sz){ 
    	return s.size() >= sz;
    }

但是，我们不能用这个函数作为find\_if的一个参数。如前文所示，find\_if接受一个一元谓词，因此传递给find\_if 的可调用对象必须接受单一参数。biggies传递给find\_if的lambda使用捕获列表来保存sz。**为了用check\_size来代替此lambda**，**必须解决如何向sz形参传递一个参数的问题**。

#### 标准库bind函数 ####

我们可以解决向 check\_size传递一个长度参数的问题，方法是使用一个新的名为**bind**的标准库函数，它定义在头文件functional中。可以将bind函数看作一个**通用的函数适配器**，它接受一个可调用对象，生成一个新的可调用对象来“适应”原对象的参数列表。

调用bind 的一般形式为：

auto newCallable = bind(callable, arg_list);

其中，newCallable本身是一个可调用对象，arg\_list 是一个逗号分隔的参数列表，对应给定的callable的参数。即，当我们调用newCallable时，newCallable会调用callable，并传递给它arg\_list中的参数。

arg\_list中的参数可能包含形如\_n的名字，其中n是一个整数。这些参数是“**占位符**”，  
表示newCallable的参数，它们占据了传递给newCallable的参数的“位置”。**数值n表示生成的可调用对象中参数的位置**：\_1为newCallable的第一个参数，\_2为第二个参数，依此类推。

#### 绑定check\_size的sz参数 ####

作为一个简单的例子，我们将使用bind生成一个调用check\_size的对象，如下所示，它用一个定值作为其大小参数来调用check\_size：

//check6是一个可调用对象，接受一个string类型的参数
    //并用此 string和值6来调用check_size
    auto check6 = bind(check_size, _1, 6);

此bind调用只有一个占位符，表示 check6只接受单一参数。占位符出现在 arg\_list 的第一个位置，表示 check6 的此参数对应 check\_size 的第一个参数。此参数是一个const string&。因此，调用check6必须传递给它一个string类型的参数，check6会将此参数传递给check\_size。

string s = "hello" ;
    bool b1 = check6(s); //check6(s)会调用check_size(s,6)

使用bind，我们可以将原来基于lambda的find\_if调用：

auto wc = find_if(words.begin(), words.end(),
    			[sz](const string &a)

替换为如下使用check\_size的版本：

auto wc = find_if(words.begin(), words.end(),
    			bind(check_size, _1, sz));

此bind调用生成一个可调用对象，将check\_size的第二个参数绑定到sz的值。当find\_if对words中的string调用这个对象时，这些对象会调用check\_size，将给定的string和sz传递给它。因此，find\_if可以有效地对输入序列中每个string调用check\_size，实现string的大小与sz的比较。

#### 使用placeholders名字（使用命名空间using namespace） ####

名字\_n都定义在一个名为placeholders的命名空间中，而这个命名空间本身定义在std命名空间中。为了使用这些名字，两个命名空间都要写上。与我们的其他例子类似，对bind的调用代码假定之前已经恰当地使用了using声明。例如，\_1对应的using声明为:

using std::placeholders::_1;

此声明说明我们要使用的名字\_1定义在命名空间placeholders 中，而此命名空间又定义在命名空间std中。

对每个占位符名字，我们都必须提供一个单独的using声明。编写这样的声明很烦人，也很容易出错。可以使用另外一种不同形式的using 语句（详细内容将在第18章中介绍），而不是分别声明每个占位符，如下所示：

using namespace namespace_name;

这种形式说明希望所有来自namespace\_name的名字都可以在我们的程序中直接使用。例如:

using namespace std::placeholders;

使得由placeholders定义的所有名字都可用。与 bind函数一样，placeholders命名空间也定义在functional头文件中。

#### bind的参数顺序 ####

如前文所述，我们可以用bind修正参数的值。更一般的，可以用bind绑定给定可调用对象中的参数或重新安排其顺序。例如，假定f是一个可调用对象，它有5个参数，则下面对bind的调用：

//g是一个有两个参数的可调用对象
    auto g = bind(f, a, b, _2, c, _1);

生成一个新的可调用对象，它有两个参数，分别用占位符\_2和\_1表示。这个新的可调用对象将它自己的参数作为第三个和第五个参数传递给f。f的第一个、第二个和第四个参数分别被绑定到给定的值a、b和c 上。

传递给g的参数按位置绑定到占位符。即，第一个参数绑定到\_1，第二个参数绑定到\_2。因此，当我们调用g 时，其第一个参数将被传递给f作为最后一个参数，第二个参数将被传递给f作为第三个参数。

实际上，这个bind 调用会将

g(_1, _2)

映射为

f(a, b, _2, c, _1)

即，对g的调用会调用f，用g的参数代替占位符，再加上绑定的参数a、b和c。

例如，调用g(X, Y)会调用

f(a, b, Y, c, X)

#### 用bind重排参数顺序（实例） ####

下面是用bind重排参数顺序的一个具体例子，我们可以用bind颠倒isShoter的含义：

//按单词长度由短至长排序
    sort(words.begin(), words.end(), isShorter);
    
    //按单词长度由长至短排序
    sort(words.begin(), words.end(), bind(isShorter, _2, _1));

在第一个调用中，当sort需要比较两个元素A和B时，它会调用isShorter (A, B)。在第二个对sort 的调用中，传递给isShorter的参数被交换过来了。因此，当sort比较两个元素时，就好像调用isShorter(B, A)一样。

#### 绑定引用参数 ####

**默认情况下，bind的那些不是占位符的参数被拷贝到bind返回的可调用对象中**。但是，与 lambda类似，有**时对有些绑定的参数我们希望以引用方式传递，或是要绑定参数的类型无法拷贝**。

例如，为了替换一个引用方式捕获ostream的lambda：

//os是一个局部变量，引用一个输出流
    //c是一个局部变量，类型为char
    for_each(words.begin(), words.end(),
    	[&os, c](const string &s) {  os << s << c;);

可以很容易地编写一个函数，完成相同的工作:

ostream &print(ostream &os, const string &s, char c){ 
    	return os << s << c;
    }

但是，不能直接用bind来代替对os的捕获:

//错误:不能拷贝os
    for_each(words.begin(), words.end(), bind(print, os, _1, ' '));

**原因在于bind拷贝其参数，而我们不能拷贝一个ostream**。如果我们希望传递给bind一个对象而又不拷贝它，就必须使用标准库ref函数：

for_each(words.begin(), words.end(),
    			bind(print, ref(os), _1, ' '));

函数ref返回一个对象，包含给定的引用,此对象是可以拷贝的。

标准库中还有一个cref函数，生成一个保存 const引用的类。与bind一样，函数ref和 cref也定义在头文件functional 中。

#### 向后兼容：参数绑定 ####

旧版本C++提供的绑定函数参数的语言特性限制更多，也更复杂。标准库定义了两个分别名为bind1st和 bind2nd的函数。类似bind，这两个函数接受一个函数作为参数，生成一个新的可调用对象，该对象调用给定函数，并将绑定的参数传递给它。但是，这些函数分别只能绑定第一个或第二个参数。由于这些函数局限太强,在新标准中已被弃用（deprecated）。所谓被弃用的特性就是在新版本中不再支持的特性。新的C++程序应该使用bind。

## 再探迭代器 ##

除了为每个容器定义的迭代器之外，标准库在头文件 iterator 中还定义了额外几种迭代器。这些迭代器包括以下几种。

*  插入迭代器（insert iterator）：这些迭代器被绑定到一个容器上，可用来向容器插入元素。
 *  流迭代器（stream iterator）：这些迭代器被绑定到输入或输出流上，可用来遍历所  
    关联的IO流。
 *  反向迭代器（reverse iterator）：这些迭代器向后而不是向前移动。除了forward\_list之外的标准库容器都有反向迭代器。
 *  移动迭代器（move iterator）：这些专用的迭代器不是拷贝其中的元素，而是移动它们。我们将在第13章介绍移动迭代器。

### 插入迭代器 ###

**插入器是一种迭代器适配器，它接受一个容器，生成一个迭代器，能实现向给定容器添加元素**。当我们通过一个插入迭代器进行赋值时，该迭代器调用容器操作来向给定容器的指定位置插入一个元素。

下表列出了这种迭代器支持的操作。

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>it=t</td> 
   <td>在it指定的当前位置插入值t。<br>假定c是it绑定的容器，依赖于插入迭代器的不同种类，<br>此赋值会分别调用c.push_back (t) 、c.push_front(t)或c.insert (t,p)，<br>其中p为传递给inserter的迭代器位置</td> 
  </tr> 
  <tr> 
   <td>*it, ++it, it++</td> 
   <td>这些操作虽然存在，但不会对it做任何事情。每个操作都返回it</td> 
  </tr> 
 </tbody> 
</table>

插入器有三种类型，差异在于元素插入的位置：

*  back \_inserter创建一个使用push\_back的迭代器。
 *  front\_inserter创建一个使用push\_front的迭代器。
 *  inserter创建一个使用insert的迭代器。此函数接受第二个参数，这个参数必须是一个指向给定容器的迭代器。元素将被插入到给定迭代器所表示的元素之前。

Note：只有在容器支持push\_front的情况下，我们才可以使用front\_inserter。类似的，只有在容器支持 push\_back的情况下，我们才能使用back\_inserter。

理解插入器的工作过程是很重要的：当调用inserter(c, iter)时，我们得到一个迭代器，接下来使用它时，会将元素插入到iter原来所指向的元素之前的位置。即，如果it是由inserter生成的迭代器，则下面这样的赋值语句

*it = val;

其效果与下面代码一样

it = c.insert(it, val) ; // it指向新加入的元素
    ++it; //递增it使它指向原来的元素

front\_inserter生成的迭代器的行为与inserter生成的迭代器完全不一样。当我们使用front\_inserter时，元素总是插入到容器第一个元素之前。即使我们传递给inserter的位置原来指向第一个元素，只要我们在此元素之前插入一个新元素，此元素就不再是容器的首元素了:

list<int> lst = {  1, 2, 3, 4};
    list<int> lst2,lst3; //空list
    
    //拷贝完成之后，lst2包含4 3 2 1
    copy(lst.cbegin(), lst.cend(), front_inserter(lst2));
    
    //拷贝完成之后，lst3包含1 2 3 4
    copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));

当调用front\_inserter©时，我们得到一个插入迭代器，接下来会调用push\_front。当每个元素被插入到容器c中时，它变为c的新的首元素。因此，front\_inserter生成的迭代器会将插入的元素序列的顺序颠倒过来，而inserter和back\_inserter则不会。

### iostream迭代器 ###

虽然iostream类型不是容器，但标准库定义了可以用于这些IO类型对象的迭代器。

*  istream\_iterator读取输入流，
 *  ostream\_iterator向一个输出流写数据。

这些迭代器将它们对应的流当作一个特定类型的元素序列来处理。通过使用流迭代器，我们可以用泛型算法从流对象读取数据以及向其写入数据。

#### istream\_iterator操作 ####

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>istream_iterator&lt;T&gt; in (is);</td> 
   <td>in从输入流is读取类型为T的值</td> 
  </tr> 
  <tr> 
   <td>istream_iterator&lt;T&gt; end;</td> 
   <td>读取类型为T的值的istream_iterator迭代器，表示尾后位置</td> 
  </tr> 
  <tr> 
   <td>inl == in2</td> 
   <td>in1和in2必须读取相同类型。如果它们都是尾后迭代器，或绑定到相同的输入，则两者相等</td> 
  </tr> 
  <tr> 
   <td>inl != in2</td> 
   <td>同上一条</td> 
  </tr> 
  <tr> 
   <td>*in</td> 
   <td>返回从流中读取的值</td> 
  </tr> 
  <tr> 
   <td>in-&gt;mem</td> 
   <td>与(*in).mem的含义相同</td> 
  </tr> 
  <tr> 
   <td>++in, in++</td> 
   <td>使用元素类型所定义的&gt;&gt;运算符从输入流中读取下一个值。与以往一样，前置版本返回一个指向递增后迭代器的引用，后置版本返回旧值</td> 
  </tr> 
 </tbody> 
</table>

当创建一个流迭代器时，必须指定迭代器将要读写的对象类型。一个istream\_iterator使用>>来读取流。因此， istream\_iterator要读取的类型必须定义了输入运算符。当创建一个istream\_iterator时，我们可以将它绑定到一个流。当然，我们还可以默认初始化迭代器，这样就创建了一个可以当作尾后值使用的迭代器。

istream_iterator<int> int_it(cin);//从cin读取int
    istream_iterator<int> int_eof;//尾后迭代器
    ifstream in("afile");
    istream_iterator<string> str_it (in);//从"afile"读取字符串

下面是一个用istream\_iterator从标准输入读取数据，存入一个vector的例子：

istream_iterator<int> in_iter(cin);//从cin读取int
    istream_iterator<int> eof;// istream尾后迭代器
    
    while (in_iter != eof) //当有数据可供读取时
        //后置递增运算读取流，返回迭代器的旧值
        //解引用迭代器，获得从流读取的前一个值
        vec.push_back (*in_iter++);

此循环从cin读取int 值，保存在vec中。在每个循环步中，循环体代码检查in\_iter是否等于eof。eof被定义为空的istream\_iterator，从而可以当作尾后迭代器来使用。对于一个绑定到流的迭代器，一旦其关联的流遇到文件尾或遇到IO错误，迭代器的值就与尾后迭代器相等。

此程序最困难的部分是传递给push\_back的参数，其中用到了解引用运算符和后置递增运算符。该表达式的计算过程与我们之前写过的其他结合解引用和后置递增运算的表达式一样。后置递增运算会从流中读取下一个值，向前推进，但返回的是迭代器的旧值。迭代器的旧值包含了从流中读取的前一个值，对迭代器进行解引用就能获得此值。

我们可以将程序重写为如下形式，这体现了istream\_iterator更有用的地方：

istream_iterator<int> in_iter(cin), eof; // 从cin 读取 int
    vector<int> vec(in_iter, eof); //从迭代器范围构造vec

本例中我们用一对表示元素范围的迭代器来构造vec。这两个迭代器是istream\_iterator，这意味着元素范围是通过从关联的流中读取数据获得的。这个构造函数从cin中读取数据，直至遇到文件尾或者遇到一个不是int的数据为止。从流中读取的数据被用来构造vec。

#### 使用算法操作流迭代器 ####

由于算法使用迭代器操作来处理数据，而流迭代器又至少支持某些迭代器操作，因此我们至少可以用某些算法来操作流迭代器。稍后会看到如何分辨哪些算法可以用于流迭代器。下面是一个例子，我们可以用一对istream\_iterator来调用accumulate：

istream_iterator<int> in(cin), eof;
    cout << accumulate(in, eof, 0) << endl;

此调用会计算出从标准输入读取的值的和。如果输入为：

23 109 45 89 6 34 12 90 34 23 56 23 8 89 23

则输出为664。

#### istream\_iterator允许使用懒惰求值 ####

当我们将一个istream\_iterator绑定到一个流时，标准库并不保证迭代器立即从流读取数据。具体实现可以推迟从流中读取数据，直到我们使用迭代器时才真正读取。标准库中的实现所保证的是，在我们第一次解引用迭代器之前，从流中读取数据的操作已经完成了。

对于大多数程序来说，立即读取还是推迟读取没什么差别。但是，如果我们创建了一个istream iterator，没有使用就销毁了，或者我们正在从两个不同的对象同步读取同一个流，那么何时读取可能就很重要了。

（MyNote：懒加载）

#### ostream\_iterator操作 ####

我们可以对任何具有输出运算符（<<运算符）的类型定义ostream\_iterator。当创建一个ostream\_iterator时，我们可以提供（可选的）第二参数，它是一个字符串，在输出每个元素后都会打印此字符串。此字符串必须是一个C风格字符串（即，一个字符串字面常量或者一个指向以空字符结尾的字符数组的指针）。必须将ostream\_iterator绑定到一个指定的流，不允许空的或表示尾后位置的ostream\_iterator。

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>ostream_iterator&lt;T&gt; out (os);</td> 
   <td>out将类型为T的值写到输出流os 中</td> 
  </tr> 
  <tr> 
   <td>ostream_iterator&lt;T&gt; out (os, d);</td> 
   <td>out将类型为T的值写到输出流os 中，每个值后面都输出一个d。d指向一个空字符结尾的字符数组</td> 
  </tr> 
  <tr> 
   <td>out = val</td> 
   <td>用&lt;&lt;运算符将val写入到out所绑定的ostream 中。val的类型必须与out可写的类型兼容</td> 
  </tr> 
  <tr> 
   <td>*out, ++out, out++</td> 
   <td>这些运算符是存在的，但不对out做任何事情。每个运算符都返回out</td> 
  </tr> 
 </tbody> 
</table>

我们可以用ostream\_iterator来输出值的序列：

ostream_iterator<int> out_iter (cout, " ");
    
    for (auto e : vec)
    	*out_iter++ = e; //赋值语句实际上将元素写到cout
    cout << endl;

此程序将vec中的每个元素写到cout，每个元素后加一个空格。每次向out\_iter赋值时，写操作就会被提交。

值得注意的是，当我们向out\_iter赋值时，可以忽略解引用和递增运算。即，循环可以重写成下面的样子：

for (auto e : vec)
    	out_iter = e; //赋值语句将元素写到cout
    cout << endl;

运算符\*和++实际上对ostream\_iterator对象不做任何事情，因此忽略它们对我们的程序没有任何影响。但是，**推荐第一种形式**。在这种写法中，流迭代器的使用与其他迭代器的使用保持一致。如果想将此循环改为操作其他迭代器类型，修改起来非常容易。而且，对于读者来说，此循环的行为也更为清晰。

可以通过调用copy来打印vec中的元素，这比编写循环更为简单：

copy(vec.begin(), vec.end(), out_iter);
    cout << endl;

#### 使用流迭代器处理类类型 ####

我们可以为任何定义了输入运算符（>>）的类型创建istream\_iterator对象。类似的，只要类型有输出运算符（<<），我们就可以为其定义ostream\_iterator。

由于Sales\_item既有输入运算符也有输出运算符，因此可以使用IO迭代器重写第一章中的书店程序：

istream_iterator<Sales_item> item_iter(cin), eof;
    ostream_iterator<Sales_item> out_iter(cout, "\n");//写入cout，每个结果后面都跟一个换行符
    
    //将第一笔交易记录存在sum中，并读取下一条记录
    //此处，我们对item_iter执行后置递增操作，对结果进行解引用操作。
    //这个表达式读取下一条交易记录，并用之前保存在item_iter中的值来初始化sum。
    Sales_item sum = *item_iter++;
    
    while (item_iter != eof) { //while循环会反复执行，直至在cin上遇到文件尾为止
        //如果当前交易记录（存在item_iter 中)有着相同的ISBN号
        if (item_iter->isbn() == sum.isbn())
            sum += *item_iter++; //将其加到sum上并读取下一条记录
        else { 
            out_iter = sum; //输出sum当前值
            sum = *item_iter++; //读取下一条记录
        }
        // sum = *item_iter++;重复代码，可优化
    }
    out_iter = sum; //记得打印最后一组记录的和

此程序使用item\_iter从cin读取Sales\_item交易记录，并将和写入cout，每个结果后面都跟一个换行符。

## 泛型算法结构 ##

任何算法的最基本的特性是它要求其迭代器提供哪些操作。某些算法，如 find，只要求通过迭代器访问元素、递增迭代器以及比较两个迭代器是否相等这些能力。其他一些算法，如 sort，还要求读、写和随机访问元素的能力。算法所要求的迭代器操作可以分为**5个迭代器类别**（iterator category），如下表所示。

每个算法都会对它的每个迭代器参数指明须提供哪类迭代器。

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>输入迭代器</td> 
   <td>只读，不写；单遍扫描，只能递增</td> 
  </tr> 
  <tr> 
   <td>输出迭代器</td> 
   <td>只写，不读；单遍扫描，只能递增</td> 
  </tr> 
  <tr> 
   <td>前向迭代器</td> 
   <td>可读写；多遍扫描，只能递增</td> 
  </tr> 
  <tr> 
   <td>双向迭代器</td> 
   <td>可读写；多遍扫描，可递增递减</td> 
  </tr> 
  <tr> 
   <td>随机访问迭代器</td> 
   <td>可读写，多遍扫描，支持全部迭代器运算</td> 
  </tr> 
 </tbody> 
</table>

第二种算法分类的方式是按照是否读、写或是重排序列中的元素来分类。附录A按这种分类方法列出了所有算法。

### 5类迭代器 ###

类似容器，迭代器也定义了一组公共操作。一些操作所有迭代器都支持，另外一些只有特定类别的迭代器才支持。例如，ostream\_iterator只支持递增、解引用和赋值。vector、string和 deque 的迭代器除了这些操作外，还支持递减、关系和算术运算。

迭代器是按它们所提供的操作来分类的，而这种分类形成了一种层次。除了输出迭代器之外，一个高层类别的迭代器支持低层类别迭代器的所有操作。

C++标准指明了泛型和数值算法的每个迭代器参数的最小类别。例如，

*  find算法在一个序列上进行一遍扫描，对元素进行只读操作，因此至少需要输入迭代器。
 *  replace函数需要一对迭代器，至少是前向迭代器。
 *  类似的，replace\_copy的前两个迭代器参数也要求至少是前向迭代器。其第三个迭代器表示目的位置，必须至少是输出迭代器。

其他的例子类似。对每个迭代器参数来说，其能力必须与规定的最小类别至少相当。向算法传递一个能力更差的迭代器会产生错误。

**WARNING**：对于向一个算法传递错误类别的迭代器的问题,很多编译器不会给出任何警告或提示。

#### 迭代器类别 ####

**输入迭代器**（input iterator）：可以读取序列中的元素。一个输入迭代器必须支持

*  用于比较两个迭代器的相等和不相等运算符（==、!=）
 *  用于推进迭代器的前置和后置递增运算（++）
 *  用于读取元素的解引用运算符（\*）；解引用只会出现在赋值运算符的右侧
 *  箭头运算符（->），等价于(\*it) .member，即，解引用迭代器，并提取对象的成员\*

输入迭代器只用于顺序访问。对于一个输入迭代器，\*it++保证是有效的，但递增它可能导致所有其他指向流的迭代器失效。其结果就是，不能保证输入迭代器的状态可以保存下来并用来访问元素。因此,输入迭代器只能用于单遍扫描算法。算法find和 accumulate要求输入迭代器；而istream\_iterator是一种输入迭代器。

**输出迭代器**（output iterator）：可以看作输入迭代器功能上的补集——只写而不读元素。输出迭代器必须支持

*  用于推进迭代器的前置和后置递增运算（++）
 *  解引用运算符（\*），只出现在赋值运算符的左侧（向一个已经解引用的输出迭代器赋值，就是将值写入它所指向的元素）

我们只能向一个输出迭代器赋值一次。类似输入迭代器，输出迭代器只能用于单遍扫描算法。用作目的位置的迭代器通常都是输出迭代器。例如，copy函数的第三个参数就是输出迭代器。ostream\_iterator类型也是输出迭代器。

**前向迭代器**（forward iterator）：可以读写元素。这类迭代器只能在序列中沿一个方向移动。前向迭代器支持所有输入和输出迭代器的操作，而且可以多次读写同一个元素。因此，我们可以保存前向迭代器的状态，使用前向迭代器的算法可以对序列进行多遍扫描。算法replace要求前向迭代器，forward\_list 上的迭代器是前向迭代器。

**双向迭代器**（bidirectional iterator）：可以正向/反向读写序列中的元素。除了支持所有前向迭代器的操作之外，双向迭代器还支持前置和后置递减运算符（–）。算法reverse要求双向迭代器，除了forward\_list之外，其他标准库都提供符合双向迭代器要求的迭代器。

**随机访问迭代器**（random-access iterator）：提供在常量时间内访问序列中任意元素的能力。此类迭代器支持双向迭代器的所有功能，此外还支持如下操作：

*  用于比较两个迭代器相对位置的关系运算符（<、<=、>和>=）
 *  迭代器和一个整数值的加减运算（+、+=、-和-=），计算结果是迭代器在序列中前进(或后退）给定整数个元素后的位置
 *  用于两个迭代器上的减法运算符（-），得到两个迭代器的距离
 *  下标运算符(iter\[n\])，与\* (iter\[n\])等价

算法sort要求随机访问迭代器。array、deque、string和 vector的迭代器都是随机访问迭代器，用于访问内置数组元素的指针也是。

### 算法形参模式 ###

在任何其他算法分类之上，还有一组参数规范。理解这些参数规范对学习新算法很有帮助——通过理解参数的含义，你可以将注意力集中在算法所做的操作上。大多数算法具有如下4种形式之一：

alg(beg, end, other args);
    alg(beg, end, dest, other args);
    alg(beg, end, beg2, other args);
    alg(beg, end, beg2, end2, other args);

其中 alg是算法的名字，beg和 end表示算法所操作的输入范围。几乎所有算法都接受一个输入范围，是否有其他参数依赖于要执行的操作。这里列出了常见的一种——dest、beg2和 end2，都是迭代器参数。顾名思义，如果用到了这些迭代器参数，它们分别承担指定目的位置和第二个范围的角色。除了这些迭代器参数，一些算法还接受额外的、非迭代器的特定参数。

#### 接受单个目标迭代器的算法 ####

dest参数是一个表示算法可以写入的目的位置的迭代器。算法假定（assume)：按其需要写入数据，不管写入多少个元素都是安全的。

**WARNING：向输出迭代器写入数据的算法都假定目标空间足够容纳写入的数据。**

如果dest是一个直接指向容器的迭代器，那么算法将输出数据写到容器中已存在的元素内。更常见的情况是，dest被绑定到一个**插入迭代器**或是一个**ostream\_iterator**。插入迭代器会将新元素添加到容器中，因而保证空间是足够的。ostream\_iterator 会将数据写入到一个输出流，同样不管要写入多少个元素都没有问题。

#### 接受第二个输入序列的算法 ####

接受单独的beg2或是接受beg2和end2的算法用这些迭代器表示第二个输入范围。这些算法通常使用第二个范围中的元素与第一个输入范围结合来进行一些运算。

如果一个算法接受 beg2和end2，这两个迭代器表示第二个范围。这类算法接受两个完整指定的范围：\[beg, end)表示的范围和\[beg2, end2)表示的第二个范围。

只接受单独的 beg2(不接受end2)的算法将beg2作为第二个输入范围中的首元素。此范围的结束位置未指定，这些算法假定从beg2开始的范围与 beg和end所表示的范围至少一样大。  
接受单独beg2的算法假定从 beg2开始的序列与 beg和end所表示的范围至少一样大。

**WARNING**：接受单独beg2的算法假定从 beg2开始的序列与beg和end所表示的范围至少一样大。

### 算法命名规范 ###

除了参数规范，算法还遵循一套命名和重载规范。这些规范处理诸如:如何提供一个操作代替默认的<或–运算符以及算法是将输出数据写入输入序列还是一个分离的目的位置等问题。

#### 一些算法使用重载形式传递一个谓词 ####

接受谓词参数来代替<或–运算符的算法，以及那些不接受额外参数的算法，通常都是重载的函数。函数的一个版本用元素类型的运算符来比较元素；另一个版本接受一个额外谓词参数，来代替<或–：

unique(beg, end); //使用==运算符比较元素
    unique(beg, end, comp); //使用comp比较元素

两个调用都重新整理给定序列，将相邻的重复元素删除。

*  第一个调用使用元素类型的==运算符来检查重复元素;
 *  第二个则调用comp来确定两个元素是否相等。

由于两个版本的函数在参数个数上不相等，因此具体应该调用哪个版本不会产生歧义。

#### \_if版本的算法 ####

接受一个元素值的算法通常有另一个不同名的（不是重载的）版本，该版本接受一个谓词代替元素值。接受谓词参数的算法都有附加的\_if前缀：

find(beg, end, val) ; //查找输入范围中val第一次出现的位置
    find_if(beg, end, pred) ; //查找第一个令pred为真的元素

这两个算法都在输入范围中查找特定元素第一次出现的位置。算法find查找一个指定值;算法find\_if查找使得pred返回非零值的元素。

这两个算法提供了命名上差异的版本，而非重载版本，因为两个版本的算法都接受相同数目的参数。因此可能产生重载歧义，虽然很罕见，但为了避免任何可能的歧义，标准库选择提供不同名字的版本而不是重载。

#### 区分拷贝元素的版本和不拷贝的版本 ####

默认情况下，重排元素的算法将重排后的元素写回给定的输入序列中。这些算法还提供另一个版本，将元素写到一个指定的输出目的位置。如我们所见，写到额外目的空间的

算法都在名字后面附加一个\_copy:

reverse(beg, end); //反转输入范围中元素的顺序
    reverse_copy(beg, end, dest);//将元素按逆序拷贝到dest

一些算法同时提供\_copy和\_if版本。这些版本接受一个目的位置迭代器和一个谓词:

//从v1中删除奇数元素
    remove_if(v1.begin(), v1.end(),
    			[](int i) {  return i % 2; });
    //将偶数元素从v1拷贝到v2; v1不变
    remove_copy_if(v1.begin(), v1.end(), back_inserter(v2) ,
    				[](int i){  return i % 2; });

两个算法都调用了lambda来确定元素是否为奇数。

*  在第一个调用中，我们从输入序列中将奇数元素删除。
 *  在第二个调用中，我们将偶数元素从输入范围拷贝到v2中。

## 特定容器算法（链表） ##

与其他容器不同，链表类型list和 forward\_list定义了几个成员函数形式的算法，如下表所示。特别是，它们定义了独有的sort、merge、remove、reverse和unique。**通用版本的sort要求随机访问迭代器，因此不能用于list和forward\_list，因为这两个类型分别提供双向迭代器和前向迭代器**。

链表类型定义的其他算法的通用版本可以用于链表，但代价太高。这些算法需要交换输入序列中的元素。**一个链表可以通过改变元素间的链接而不是真的交换它们的值来快速“交换”元素**。因此，这些链表版本的算法的性能比对应的通用版本好得多。

**Best Practices**：对于list和forward\_list，应该优先使用成员函数版本的算法而不是通用算法。

注：表内操作都返回void

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>lst.merge(lst2)</td> 
   <td>将来自lst2的元素合并入lst。lst和lst2都必须是有序的。</td> 
  </tr> 
  <tr> 
   <td>lst.merge(lst2, comp)</td> 
   <td>元素将从lst2中删除。在合并之后，lst2变为空。第一个版本使用&lt;运算符；第二个版本使用给定的比较操作</td> 
  </tr> 
  <tr> 
   <td>lst.remove(val)</td> 
   <td>调用erase删除掉与给定值相等（==）或令一元谓词为真的每个元素</td> 
  </tr> 
  <tr> 
   <td>lst.remove_if(pred)</td> 
   <td>同上一条</td> 
  </tr> 
  <tr> 
   <td>lst.reverse()</td> 
   <td>反转lst中元素的顺序</td> 
  </tr> 
  <tr> 
   <td>lst.sort()</td> 
   <td>使用&lt;或给定比较操作排序元素</td> 
  </tr> 
  <tr> 
   <td>lst.sort(comp)</td> 
   <td>同上一条</td> 
  </tr> 
  <tr> 
   <td>lst.unique()</td> 
   <td>调用erase删除同一个值的连续拷贝。第一个版本使用==；第二个版本使用给定的二元谓词</td> 
  </tr> 
  <tr> 
   <td>lst.unique(pred)</td> 
   <td>同上一条</td> 
  </tr> 
 </tbody> 
</table>

### splice成员 ###

链表类型还定义了splice算法，其描述见下表。此算法是链表数据结构所特有的，因此不需要通用版本。

list和forward\_list的splice成员函数的参数：

lst.splice(args)或flst.splice\_after(args)

<table> 
 <thead> 
  <tr> 
   <th>list和forward_list的splice成员函数的参数args</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>(p, lst2)</td> 
   <td>p是一个指向lst中元素的迭代器，或一个指向flst首前位置的迭代器。函数将lst2的所有元素移动到lst中 p之前的位置或是flst中p之后的位置。将元素从lst2中删除。lst2的类型必须与lst或flst相同，且不能是同一个链表</td> 
  </tr> 
  <tr> 
   <td>(p, lst2, p2)</td> 
   <td>p2是一个指向lst2中位置的有效的迭代器。将p2指向的元素移动到lst中，或将p2之后的元素移动到flst中。lst2可以是与lst或flst相同的链表</td> 
  </tr> 
  <tr> 
   <td>(p, lst2, b, e)</td> 
   <td>b和e必须表示 lst2中的合法范围。将给定范围中的元素从lst2移动到lst或flst。lst2与lst（或flst）可以是相同的链表，但p不能指向给定范围中元素</td> 
  </tr> 
 </tbody> 
</table>

> splice  
> 英 \[splaɪs\] 美 \[splaɪs\]  
> v. 绞接，捻接(两段绳子);胶接，粘接(胶片、磁带等)  
> n. 胶接处;粘接处;绞接处

### 链表特有的操作会改变容器 ###

多数链表特有的算法都与其通用版本很相似，但不完全相同。链表特有版本与通用版本间的一个至关重要的区别是链表版本会改变底层的容器。例如，

*  remove 的链表版本会删除指定的元素。
 *  unique 的链表版本会删除第二个和后继的重复元素。

类似的，merge和 splice会销毁其参数。例如，

*  通用版本的merge将合并的序列写到一个给定的目的迭代器；两个输入序列是不变的。
 *  而链表版本的merge函数会销毁给定的链表——元素从参数指定的链表中删除，被合并到调用merge 的链表对象中。在merge之后，来自两个链表中的元素仍然存在，但它们都已在同一个链表中。