C++标准库 -- 泛型算法 (Primer C++ 第五版 · 阅读笔记)

喜欢ヅ旅行 2024-03-23 15:26 84阅读 0赞

#### C++标准库 -- 泛型算法 (Primer C++ 第五版 · 阅读笔记） ####

*  第10章 泛型算法------(持续更新)
 *   *  10.1、概述
     *  10.2、初识泛型算法
     *   *  10.2.1、只读算法
         *  10.2.2、写容器元素的算法
         *  10.2.3、重排容器元素的算法
     *  10.3、定制操作
     *   *  10.3.1、向算法传递函数
         *  10.3.2、lambda表达式
         *  10.3.3、lambda捕获和返回
         *  10.3.4、参数绑定
     *  10.4、再探迭代器
     *   *  10.4.1、插入迭代器
         *  10.4.2、iostream迭代器
         *  10.4.3、反向迭代器
     *  10.5、泛型算法结构
     *   *  10.5.1、5类迭代器
         *  10.5.2、算法形参模式
         *  10.5.3、算法命名规范
     *  10.6、特定容器算法(list、forward\_list)

## 第10章 泛型算法------(持续更新) ##

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

我们可以想象用户可能还希望做其他很多有用的操作:查找特定元素、替换或删除一个特定值、重排元素顺序等。

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

**关系图：**  
![在这里插入图片描述][900a0ab3fcd74fbc89556eda9c4c2285.jpeg]

### 10.1、概述 ###

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

一般情况下，这些算法并不直接操作容器，而是遍历由两个迭代器指定的一个元素范围来进行操作。通常情况下，算法遍历范围，对其中每个元素进行一些处理。

例如，假定我们有一个`int`的`vector`，希望知道`vector`中是否包含一-个特定值。回答这个问题最方便的方法是调用标准库算法`find`:

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`在一个`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);

**算法如何工作**

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

1.  访问序列中的首元素。
2.  比较此元素与我们要查找的值。
3.  如果此元素与我们要查找的值匹配，`find`返回标识此元素的值。
4.  否则，`find`前进到下一个元素，重复执行步骤2和3。
5.  如果到达序列尾，`find`应停止。
6.  如果`find` 到达序列末尾，它应该返回一个指出元素未找到的值。此值和步骤3返回的值必须具有相容的类型。

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

**迭代器令算法不依赖于容器，……**

在上述`find` 函数流程中，除了第2步外，其他步骤都可以用迭代器操作来实现:利用迭代器解引用运算符可以实现元素访问;

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

**……，但算法依赖于元素类型的操作**

虽然迭代器的使用令算法不依赖于容器类型，但大多数算法都使用了一个（或多个)元素类型上的操作。例如，

*  在步骤2中，`find`用元素类型的 `==` 运算符完成每个元素与给定值的比较。
 *  其他算法可能要求元素类型支持 `<` 运算符。
 *  不过，我们将会看到，大多数算法提供了一种方法，允许我们使用**自定义的操作**来代替默认的运算符。

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

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

### 10.2、初识泛型算法 ###

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

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

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

#### 10.2.1、只读算法 ####

一些算法只会读取其输入范围内的元素，而从不改变元素。`find`就是这样一种算法，以及`count`函数也是如此。

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

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

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

**算法和元素类型**

`accumulate`将第三个参数作为求和起点，这蕴含着一个编程假定:将元素类型加到和的类型上的操作必须是可行的。即，序列中元素的类型必须与第三个参数匹配.或者能够转换为第三个参数的类型。

在上例中, `vec` 中的元素可以是`int`,或者是`double`、`long long`或任何其他可以加到`int`上的类型。

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

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

**注意**，

*  我们通过第三个参数**显式地创建了**一个`string`。
 *  将空串当做一个字符串字面值传递给第三个参数是不可以的，会导致一个编译错误。原因在于，如果我们传递了一个字符串字面值，用于保存和的对象的类型将是`const char*`。如前所述，此类型决定了使用哪个 `+` 运算符。由于`const char*` 并没有 `+` 运算符，此调用将产生编译错误。

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

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

另一个只读算法是`equal`，用于确定两个序列是否保存相同的值。它将第一个序列中的每个元素与第二个序列中的对应元素进行比较。如果所有对应元素都相等，则返回`true`，否则返回`false`。

此算法接受三个迭代器:前两个(与以往一样）表示第一个序列中的元素范围，第三个表示第二个序列的首元素:

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

由于`equal`利用迭代器完成操作，因此我们可以通过调用`equal` 来比较两个不同类型的容器中的元素。而且，元素类型也不必一样，只要我们能用–来比较两个元素类型即可。

例如，在此例中，`roster1`可以是`vector<string>`，而`roster2`是`list<const char*>`。

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

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

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

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

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

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

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

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

**算法不检查写操作**

一些算法接受一个迭代器来指出一个单独的目的位置。这些算法将新值赋予一个序列中的元素，该序列从目的位置迭代器指向的元素开始。

例如，函数`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`)。

*  插入迭代器是一种向容器中添加元素的迭代器。
 *  通常情况，当我们通过一个迭代器向容器元素赋值时，值被**赋予**迭代器指向的元素。而当我们通过一个插入迭代器赋值时，一个与赋值号右侧值相等的元素被**添加**到容器中。

我们将在10.4.1节中详细介绍**插入迭代器**的内容。但是，为了展示如何用算法向容器写入数据,我们现在将使用`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与al大小一样
    // ret指向拷贝到a2的尾元素之后的位置
    auto ret = copy(begin(al), end(al), a2); //把a1的内容拷贝给a2

`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。

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

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

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

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

the quick red fox jumps over the slow red turtle

**消除重复单词**

为了消除重复单词,

*  首先将`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());
    }

`unique`并不真的删除任何元素，它只是覆盖相邻的重复元素，使得不重复元素出现在序列开始部分。`unique`返回的迭代器指向最后一个不重复元素之后的位置。此位置之后的元素仍然存在，但我们不知道它们的值是什么。

为了真正地删除无用元素，我们必须使用容器操作，本例中使用`erase`。

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

### 10.3、定制操作 ###

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

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

**谓词（predicate）**

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

*  **一元谓词**（**unary predicate**，意味着它们只接受单一参数）;
 *  **二元谓词**( **binary predicate**，意味着它们有两个参数)。

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

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

//比较函数，用来按长度排序单词
    bool isShorter(const string &s1, const string &s2){
        
    	return sl.size() < s2.size();
    }
    
    //按长度由短至长排序words
    sort(words.begin(), words.end(), isshorter);

**排序算法**

在我们将 `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

#### 10.3.2、lambda表达式 ####

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

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

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

我们可以使用标准库`find_if` 算法来查找第一个具有特定大小的元素, `find_if` 的第三个参数是一个谓词。但是，`find_if` 接受一元谓词——我们传递给 `find_if` 的任何函数都必须严格接受一个参数，以便能用来自输入序列的一个元素调用它。没有任何办法能传递给它第二个参数来表示长度。为了解决此问题，需要使用另外一些语言特性。

**介绍lambda**

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

到目前为止，

*  我们使用过的仅有的两种**可调用对象**是**函数**和**函数指针**。
 *  还有其他两种**可调用对象**:
    
     *  **重载了函数调用运算符的类**，我们将在14.8节介绍;
     *  以及`lambda`表达式（`lambda expression`)。

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

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

*  `capture list`（捕获列表）是一个`lambda`所在函数中定义的局部变量的列表(通常为空);
 *  `return type`、`parameter list`和 `function body`与任何普通函数一样，分别表示返回类型、参数列表和函数体。
 *  但是，与普通函数不同，`lambda`必须使用**尾置返回**（参见6.3.3节，第206页) 来指定返回类型。

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

//我们定义了一个可调用对象 `f` ，它不接受参数，返回42。
    auto f = [] {
         return 42;};
    
    //lambda 的调用方式与普通函数的调用方式相同，都是使用调用运算符:
    cout << f() << endl; //打印42

在 `lambda`中忽略括号和参数列表等价于指定一个空参数列表。在此例中，当调用f时，参数列表是空的。如果忽略返回类型，`lambda`根据函数体中的代码**推断出返回类型**。如果函数体只是一个`return`语句，则返回类型从返回的表达式的类型推断而来。否则，返回类型为`void`。

> 如果 `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; };

> 一个`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`来输出“`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`。

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

**完整的biggies**

到目前为止，我们已经解决了程序的所有细节，下面就是完整的程序:

void biggies(vector<string> &words, vector<string>::size_type sz)
    {
        
    	elimDups(words); //将words按字典序排序，删除重复单词
    	//按长度排序，长度相同的单词维持字典序
    	stable_sort(words.begin(), words.end(),
    				[](const string &a, const string &b)
    					{
        return a.size() < b.size();});
    	//获取一个迭代器，指向第一个满足size() >= sz的元素
    	auto wc = find_if(words.begin (), words.end(),
    					[sz] (const string &a)
    					{
         return a.size() >= sz; });
    	//计算满足size >= sz的元素的数目
    	auto count = words.end() - wc;
    	cout << count << " " << make_plural(count, "word", "s")
    		<< " of length " << sz << " or longer" << endl;
    	//打印长度大于等于给定值的单词，每个单词后面接一个空格
    	for_each (wc, words.end(),
    				[]（const string &s){
        cout << s << " ";});
    	cout << endl;
    }

#### 10.3.3、lambda捕获和返回 ####

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

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

**值捕获**

类似参数传递，变量的捕获方式也可以是**值**或**引用**。表10.1列出了几种不同的**构造捕获列表**的方式。到目前为止，我们的 `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`内对应的值。

![在这里插入图片描述][464dbed0f5ca425f8b7554ac2f716efc.png]

**引用捕获**

我们定义`lambda`时可以采用**引用方式捕获**变量。例如:

void fcn2()
    {
        
    	size_t v1 = 42;	//局部变量
    	//对象f2包含v1的引用
    	auto f2 = [&v1] {
         return vl; };
    	vl = 0;
    	auto j = f2();	// j为0;f2保存v1的引用，而非拷贝
    }

`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= ' ')
    {
        
    	//与之前例子一样的重排words的代码
    	//打印count的语句改为打印到os
    	for_each (words.begin(), words.end(),
    				[&os, c](const string &s){
         os << s << c; });
    }

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

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

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

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

![在这里插入图片描述][d632fa55519547a7be9f3b99700c5f50.png]

**隐式捕获**

除了显式列出我们希望使用的来自所在函数的变量之外,还可以让编译器根据`lambda`体中的代码来**推断**我们要使用哪些变量。为了指示编译器**推断**捕获列表，应在捕获列表中写一个 `&` 或 `=`。

*  `&` 告诉编译器采用捕获引用方式，
 *  `=`则表示采用值捕获方式。

例如，我们可以**重写传递**给 `find_if` 的 `lambda` :

// sz为隐式捕获，值捕获方式
    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 = '')
    {
        
    	//其他处理与前例一样
    	// os隐式捕获，引用捕获方式; c显式捕获，值捕获方式
    	for_each (words.begin(), words.end(),
    				[&, c] (const string &s){
         os << s << c; });
    	// os显式捕获，引用捕获方式;c隐式捕获，值捕获方式
    	for_each (words.begin(), words.end(),
    				[=, &os](const string &s){
         os << s << c;});
    }

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

当混合使用隐式捕获和显式捕获时，显式捕获的变量必须使用与隐式捕获不同的方式。即，

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

**可变lambda**

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

void fcn3(){
        
    	size_t v1 = 42;//局部变量
    	// f可以改变它所捕获的变量的值
    	auto f = [v1] () mutable {
         return ++v1; };
    	vl = 0;
    	auto j = f();// j为43
    }

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

void fcn4 (){
        
    	size_t v1 = 42; //局部变量
    	// v1是一个非const变量的引用
    	//可以通过f2中的引用来改变它
    	auto f2 = [&v1] {
         return ++vl; };
    	v1 = 0;
    	auto j = f2();// j为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` 一个`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`定义返回类型时，必须使用**尾置返回类型**:

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

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

#### 10.3.4、参数绑定 ####

对于那种只在一两个地方使用的简单操作，`lambda`表达式是最有用的。

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

如果`lambda`的捕获列表为空，通常可以用**函数来**代替它。

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

但是，对于**捕获局部变量**的 `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`函数看作一个**通用的函数适配器**（参见9.6节)
 *  它接受一个**可调用对象**，生成一个**新的可调用对象**来“适应”原对象的**参数列表。**

调用`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);
    
    string s = "hello";
    bool b1 = check6(s); // check6(s)会调用check_size(s,6)

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

使用`bind`，我们可以将原来基于`lambda`的`find_if`调用，替换为如下使用`check_size`的版本:

auto wc = find_if(words.begin(), words.end(),
    					[sz] (const string &a)
    					{
         return a.size() >= sz; });
    //替换为
    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名字**

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

using std::placeholders::_1;

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

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

using namespace namespace_name;

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

using namespace std::placeholders;
    
    //一般直接使用
    using namespace std;

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

**bind的参数**

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

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

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

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

g(_1, _2)
    //映射为
    f(a, b, _2, c, _1)

**用bind 重排参数顺序**

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

//按单词长度由短至长排序
    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, _l, ' '));

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

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

函数 **`ref`** 返回一个对象，包含给定的引用, 此对象是可以拷贝的。标准库中还有一个`cref`函数，生成一个保存`const`引用的类。与`bind`一样，函数`ref`和`cref`也定义在头文件`functional` 中。

![在这里插入图片描述][a652f212b3e74b88baa004badc62beaa.png]

### 10.4、再探迭代器 ###

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

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

#### 10.4.1、插入迭代器 ####

插入器是一种**迭代器适配器**（参见9.6节)，**它接受一个容器，生成一个迭代器**，能实现向给定容器添加元素。当我们通过一个插入迭代器进行赋值时，该迭代器调用容器操作来向给定容器的指定位置插入一个元素。表10.2列出了这种迭代器支持的操作。  
![在这里插入图片描述][896e214682eb45f8a19d940d0155d669.png]

插入器有**三种类型**,差异在于元素**插入的位置**:

*  **`back_inserter`** (参见10.2.2节）创建一个使用`push_back`的迭代器。
 *  **`front_inserter`** 创建一个使用`push_front`的迭代器。
 *  **`inserter`** 创建一个使用`insert`的迭代器。此函数接受**第二个参数**，这个参数必须是一个**指向给定容器的迭代器**。元素将被插入到给定迭代器所表示的元素之前。

> **注：** 只有在容器支持`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(c)`时，我们得到一个插入迭代器，接下来会调用`push_front`。当每个元素被插入到容器 `c` 中时，它变为 `c` 的新的首元素。因此，`front_inserter`生成的迭代器会将插入的元素序列的顺序颠倒过来，而 `inserter` 和 `back_inserter` 则不会。

#### 10.4.2、iostream迭代器 ####

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

*  **`istream_iterator`** (参见表10.3）**读取输入流**;
 *  **`ostream_ iterator`** (参见表10.4节）**向一个输出流写数据**。

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

**istream\_iterator操作**

当创建一个流迭代器时，必须指定迭代器将要读写的**对象类型**。

*  一个`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`，从而可以当作尾后迭代器来使用。

此程序最困难的部分是传递给`push_back`的参数，后置递增运算会从流中读取下一个值，向前推进，但返回的是迭代器的旧值。迭代器的旧值包含了从流中读取的前一个值，对迭代器进行解引用就能获得此值。

> 对于一个绑定到流的迭代器，一旦其关联的流遇到**文件尾**或遇到**IO错误**，迭代器的值就与尾后迭代器相等。

我们可以将程序重写为如下形式，这体现了`istream_iterator`更有用的地方:

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

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

![在这里插入图片描述][8240a579b6e142779480240838134d2f.png]

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

由于算法使用迭代器操作来处理数据，而流迭代器又至少支持某些迭代器操作，因此我们至少可以用某些算法来操作**流迭代器**。我们在10.5.1节会看到如何分辨哪些算法可以用于流迭代器。下面是一个例子，我们可以用一对`istream_iterator`来调用`accumulate`:

istream_iterator<int> in(cin), eof;
    //如果输入为： 23 109 45 89 6 34 12 90 34 23 56 23 8 89 23
    cout << accumulate(in, eof, 0) << endl; //输出为664

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

当我们将一个`istream_iterator`绑定到一个流时，标准库并不保证迭代器立即从流读取数据。具体实现可以推迟从流中读取数据，直到我们使用迭代器时才真正读取。

标准库中的实现所保证的是，在我们第一次解引用迭代器之前，从流中读取数据的操作已经完成了。

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

**ostream\_iterator操作**

我们可以对任何具有**输出运算符**（ `<<` 运算符）的类型定义`ostream_iterator`。

*  当创建一个`ostream_iterator`时，我们可以**提供(可选的）第二参数**，它是一个**字符串**，在输出每个元素后都会打印此字符串。此字符串必须是一个**C风格字符串**(即，一个`字符串字面常量`或者一个`指向以空字符结尾的字符数组的指针`)。
 *  必须将`ostream_iterator` 绑定到一个指定的流，**不允许空**的或表示尾后位置的`ostream_iterator`。

![在这里插入图片描述][7a7f721152eb44a18f016429c3c4b35d.png]

我们可以用`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迭代器重写1.6节（第21页）中的书店程序:

istream_iterator<sales_item> item_iter(cin), eof;
    ostream_iterator<Sales_item> out_iter(cout, "\n");
    //将第一笔交易记录存在 sum 中，并读取下一条记录
    sales_item sum = *item_iter++;
    while (item_iter != eof) {
        
    	//如果当前交易记录（存在iten_iter中）有着相同的ISBN号
    	if (item_iter->isbn() == sum.isbn())
    		sum += *item_iter++;			//将其加到sum上并读取下一条记录
    	else {
        
    		out_iter = sum;					//输出 sum当前值
    		sum = *item_iter++;				//读取下一条记录
    	}
    }
    out_iter = sum;							//记得打印最后一组记录的和

#### 10.4.3、反向迭代器 ####

反向迭代器就是在容器中从**尾元素**向**首元素**反向移动的迭代器。对于反向迭代器，**递增**（以及递减）操作的含义会颠倒过来。递增一个**反向迭代器**（`++it` ）会移动到**前一个元素**;递减一个迭代器（`--it`）会移动到下一个元素。

除了 `forward_list` 之外,其他容器都支持反向迭代器。我们可以通过调用`rbegin`、`rend`、`crbegin`和 `crend` 成员函数来获得**反向迭代器**。这些成员函数返回指向容器尾元素和首元素之前一个位置的迭代器。与普通迭代器一样，反向迭代器也有 `const` 和非 `const` 版本。

![在这里插入图片描述][bba3b1499b064be2a08ed4e9d64bc42d.png]  
下面的循环是一个使用反向迭代器的例子，它按逆序打印 `vec` 中的元素:

vector<int> vec = {
        0,1,2,3,4,5,6,7,8,9};
    //从尾元素到首元素的反向迭代器
    for (auto r_iter = vec.crbegin(); 			 //将r_iter绑定到尾元素
    			r_iter != vec.crend();			 //crend指向首元素之前的位置
    			++r_iter)			 			 //实际是递减，移动到前一个元素
    	cout << *r_iter << endl;		      	 //打印9，8， 7, ... 0
    
    
    sort(vec.begin(), vec.end()); //按“正常序”排序vec
    
    //按逆序排序:将最小元素放在vec的末尾
    sort(vec.rbegin(), vec.rend());

**反向迭代器需要递减运算符**

*  不必惊讶，我们只能从既支持 `++` 也支持 `--` 的迭代器来定义反向迭代器。毕竟反向迭代器的目的是在序列中反向移动。
 *  除了`forward_list` 之外，标准容器上的其他迭代器都既支持递增运算又支持递减运算。
 *  但是，**流迭代器不支持递减运算**，因为不可能在一个流中反向移动。因此，不可能从一个`forward_lis`t或一个`流迭代器`创建反向迭代器。

**反向迭代器和其他迭代器间的关系**

假定有一个名为`line` 的 `string`，保存着一个逗号分隔的单词列表，我们希望打印 `line` 中的第一个单词。使用`find`可以很容易地完成这一任务:

//在一个逗号分隔的列表中查找第一个元素
    auto comma = find(line.cbegin(), line.cend(), ',');
    cout << string(line.cbegin(), comma) << endl;
    
    //如果希望打印最后一个单词，可以改用反向迭代器
    //在一个逗号分隔的列表中查找最后一个元素
    auto rcomma = find(line.crbegin(), line.crend(), ',');
    
    //错误:将逆序输出单词的字符
    cout << string(line.crbegin(), rcomma) << endl;
    
    //正确:得到一个正向迭代器，从逗号开始读取字符直到line末尾 
    cout << string(rcomma.base(), line.cend())<< endl;

![在这里插入图片描述][ae21619ba97d42fc8d33589901b94d77.png]

图10.2中的对象显示了普通迭代器与反向迭代器之间的关系。例如，`rcomma`和 `rcomma.base()`指向不同的元素，`line.crbegin`和 `line.cend()`也是如此。这些不同保证了元素范围无论是正向处理还是反向处理都是相同的。

从技术上讲，普通迭代器与反向迭代器的关系反映了**左闭合区间**的特性。关键点在于`[line.crbegin()， rcomma)`和`[rcomma.base(), line.cend())` 指向 `line`中相同的元素范围。为了实现这一点，`rcomma`和`rcomma.base()`必须生成相邻位置而不是相同位置，`crbegin()`和`cend ()`也是如此。

> 反向迭代器的目的是表示元素范围，而这些范围是不对称的，这导致一个重要的结果:当我们从一个普通迭代器初始化一个反向迭代器，或是给一个反向迭代器赋值时,结果迭代器与原迭代器指向的并不是相同的元素。

### 10.5、泛型算法结构 ###

任何算法的最基本的特性是它要求其**迭代器提供哪些操作**。

*  某些算法，如 `find`，只要求通过迭代器**访问元素**、**递增迭代器**以及**比较**两个迭代器是否相等这些能力。
 *  其他一些算法，如 `sort`，还要求**读**、**写** 和 **随机访问**元素的能力。

算法所要求的迭代器操作可以分为5个迭代器类别（`iterator category`)，如表10.5所示。每个算法都会对它的每个迭代器参数**指明**须提供哪类迭代器。

![在这里插入图片描述][a1bab06bf02046cfa26a039320e4f6f6.png]  
第二种算法分类的方式是按照是否 `读`、`写` 或是 `重排序列` 中的元素来分类。附录A按这种分类方法列出了所有算法。  
算法还共享一组**参数传递规范**和一组**命名规范**，我们在介绍迭代器类别之后将介绍这些内容。

#### 10.5.1、5类迭代器 ####

类似容器，迭代器也定义了一组公共操作。一些操作所有迭代器都支持，另外一些只有特定类别的迭代器才支持。例如，

*  `ostream_iterator` 只支持**递增**、**解引用**和 **赋值**。
 *  `vector`、`string`和 `deque` 的迭代器除了这些操作外，还支持**递减**、**关系** 和 **算术**运算。

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

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

*  `find` 算法在一个序列上进行一遍扫描，对元素进行**只读操作**，因此至少需要**输入迭代器**。
 *  `replace` 函数需要一对迭代器，至少是**前向迭代器**。
 *  类似的，`replace_copy` 的前两个迭代器参数也要求至少是**前向迭代器**。其第三个迭代器表示目的位置，必须至少是**输出迭代器**。
 *  其他的例子类似。对每个迭代器参数来说，其能力必须与规定的**最小类别至少相当**。向算法传递一个能力更差的迭代器会产生错误。

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

**迭代器类别**

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

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

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

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

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

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

**(3)、前向迭代器（forward iterator)**：可以**读写**元素。这类迭代器只能在序列中沿一个方向移动。

*  前向迭代器**支持**所有**输入和输出迭代器**的操作，而且可以多次读写同一个元素。因此，我们可以**保存前向迭代器的状态**，使用前向迭代器的算法可以对序列进行**多遍扫描**。
 *  算法`replace`要求前向迭代器，`forward_list`上的迭代器是前向迭代器。

**(4)、双向迭代器（bidirectional iterator)**：可以**正向/反向**读写序列中的元素。

*  除了**支持**所有**前向迭代器**的操作之外，双向迭代器还支持前置和后置递减运算符( `--` )。
 *  算法 `reverse` 要求双向迭代器，除了`forward_list` 之外，其他标准库都提供符合双向迭代器要求的迭代器。

**(5)、随机访问迭代器（random-access iterator)**：提供**在常量时间内访问序列**中任意元素的能力。

*  此类迭代器**支持** **双向迭代器**的所有功能，此外还支持表3.7中的操作:

![在这里插入图片描述][a5d466eb020f42b99d5d49eac28d3bed.png]

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

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

#### 10.5.2、算法形参模式 ####

在任何其他算法分类之上，还有一组参数规范。理解这些参数规范对学习新算法很有帮助——通过理解参数的含义，你可以将注意力集中在算法所做的操作上。大多数算法具有如下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`):按其需要写入数据，不管写入多少个元素都是安全的。

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

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

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

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

*  如果一个算法接受 `beg2`和 `end2`，这两个迭代器表示第二个范围。这类算法接受两个完整指定的范围:`[beg,end)`表示的范围和`[beg2 end2)`表示的第二个范围。
 *  只接受单独的`beg2`(不接受`end2`)的算法将`beg2`作为第二个输入范围中的首元素。此范围的结束位置未指定，这些算法假定从`beg2`开始的范围与`beg`和 `end` 所表示的范围至少一样大。

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

#### 10.5.3、算法命名规范 ####

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

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

**接受谓词参数**来代替 `<` 或 `==` 运算符的算法，以及那些**不接受额外参数**的算法, 通常都是重载的函数。

*  函数的一个版本用**元素类型的运算符**来比较元素;
 *  另一个版本接受一个额外**谓词参数**，来代替 `<` 或 `==`:

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

两个调用都重新整理给定序列，将相邻的重复元素删除。第一个调用使用**元素类型**的 `==` 运算符来检查重复元素; 第二个则调用`comp`来确定两个元素是否相等。由于两个版本的函数在参数个数上不相等,因此具体应该调用哪个版本不会产生歧义(参见6.4节)。

**`_if` 版本的算法**

**接受一个元素值**的算法通常有另一个不同名的(**不是重载的**)版本，该版本接受一个**谓词**(参见10.3.1节)代替元素值。接受谓词参数的算法都有附加的 `_if` 前缀:

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

*  这两个算法都在输入范围中查找特定元素第一次出现的位置。算法 `find` 查找一个**指定值**;算法 `find_if` 查找使得`pred`返回非零值的元素。
 *  这两个算法提供了**命名上差异**的版本，而非重载版本，因为两个版本的算法都接受相同数目的参数。因此可能产生重载歧义，虽然很罕见，但为了避免任何可能的歧义，标准库选择提供**不同名字的版本**而不是重载。

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

默认情况下，**重排元素的算法**将重排后的元素**写回**给定的输入序列中。这些算法还提供另一个版本，将元素写到一个指定的**输出目的位置**。如我们所见，写到额外目的空间的算法都在名字后面附加一个 `copy`（参见10.2.2节):

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(vl.begin(), v1.end(), back_inserter(v2),
    							[](int i) {
         return i % 2;});

两个算法都调用了`lambda`(参见10.3.2节)来确定元素是否为奇数。

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

### 10.6、特定容器算法(list、forward\_list) ###

与其他容器不同，链表类型 `list` 和 `forward_list` 定义了几个成员函数形式的算法，如表10.6所示。特别是，它们定义了独有的 `sort`、`merge`、`remove`、`reverse`和`unique`。

> 通用版本的`sort`要求**随机访问迭代器**,因此不能用于`list`和`forward_list`,因为这两个类型分别提供**双向迭代器**和**前向迭代器**。

![在这里插入图片描述][ccb4ba09f7da4befbd2ea709876001b0.png]  
![在这里插入图片描述][7eb9563847694a61be4390718ea2f2ec.png]

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

> 对于 `list` 和 `forward_list`,应该**优先使用成员函数版本**的算法而不是通用算法。

**splice成员**

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

![在这里插入图片描述][ca61802ab30248a2bb3d97fb0ea97c60.png]

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

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

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

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

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

**注：仅供学习参考，如有不足，欢迎指正！**

[900a0ab3fcd74fbc89556eda9c4c2285.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/d636f0994e524f159c2b3b9022defacb.png
[464dbed0f5ca425f8b7554ac2f716efc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/687c5d012ace4f9f9689e310af68eaf6.png
[d632fa55519547a7be9f3b99700c5f50.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/9579cc367aeb4ff5aaebd2be75a0fcb0.png
[a652f212b3e74b88baa004badc62beaa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/84169a1500114a2580e4b3587270c9dd.png
[896e214682eb45f8a19d940d0155d669.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/4724fa1e8ffb4e34b10b2a9ece5185e6.png
[8240a579b6e142779480240838134d2f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/e629822312e7477c903e4622be8b4ab2.png
[7a7f721152eb44a18f016429c3c4b35d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/08155340fdaf4b67b30b3a9e04629dbc.png
[bba3b1499b064be2a08ed4e9d64bc42d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/7c31c0fb25154387960e40fb2c26f568.png
[ae21619ba97d42fc8d33589901b94d77.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/e5f399b2d13544b1bdd07f28a556bd36.png
[a1bab06bf02046cfa26a039320e4f6f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/3a769f0bbb7b4e69ae02e2000c015125.png
[a5d466eb020f42b99d5d49eac28d3bed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/b08ce4e4a07046579e2389d0d2d790c1.png
[ccb4ba09f7da4befbd2ea709876001b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/9224008a87bd4a958a2ed709cf65030d.png
[7eb9563847694a61be4390718ea2f2ec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/7dc24499c68b4da0b626211dcf36207c.png
[ca61802ab30248a2bb3d97fb0ea97c60.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/d00d3cd6f0db45808254fb5730417720.png