C++ Primer 第十章泛型算法

旧城等待， 2024-04-19 10:58 77阅读 0赞

### 文章目录 ###

*  1. 概述
 *   *   *  1.0.1 算法如何工作
         *  1.0.2 迭代器令算法不依赖于容器，但算法依赖于元素类型的操作
 *  2. 初识泛型算法
 *   *  2.1 只读算法
     *   *  2.1.1 算法和 元素类型
         *  2.1.2 操作两个序列的算法
     *  2.2 写容器元素的算法
     *   *  2.2.1 算法不检查写操作
         *  2.2.2 介绍back\_inserter
         *  2.2.3 拷贝算法
     *  2.3 重排容器元素的算法
     *   *  2.3.1 消除重复单词
         *  2.3.2 使用unique
         *  2.3.3 使用容器操作删除元素
 *  3. 定制操作
 *   *  3.1 向算法传递函数
     *   *  3.1.1 谓词
         *  3.1.2 排序算法
     *  3.2 lambda表达式
     *   *  3.2.1 介绍lambda
         *  3.2.2 向lambda传递参数
         *  3.2.3 使用捕获列表
         *  3.2.4 调用 find\_if
         *  3.2.5 for\_each 算法
         *  3.2.6 完整的biggies
     *  3.3 lambda 捕获和返回
     *   *  3.3.1 值捕获
         *  3.3.2 引用捕获
         *  3.3.3 隐式捕获
         *  3.3.4 可变lambda
         *  3.3.5 指定lambda返回类型
     *  3.4 参数绑定
     *   *  3.4.1 标准库bind函数
         *  3.4.2 绑定check\_size 的sz参数
         *  3.4.3 使用placeholders名字
         *  3.4.4 bind的参数
         *  3.4.5 用bind重排参数顺序
         *  3.4.6 绑定引用参数
 *  4. 再探迭代器
 *   *  4.1 插入迭代器
     *  4.2 iostream迭代器
     *   *  4.2.1 istream\_iterator 操作
         *  4.2.2 使用算法操作流迭代器
         *  4.2.3 istream\_iterator 允许使用懒惰求值
         *  4.2.4 ostream\_iterator 操作
         *  4.2.4 使用流迭代器处理类类型
     *  4.3 反向迭代器
     *   *  4.3.1 反向迭代器需要递减运算符
         *  4.3.2 反向迭代器和其他迭代器间的关系
 *  5. 泛型算法结构
 *   *  5.1 5类迭代器
     *   *  5.1.1 迭代器类别
     *  5.2 算法形参模式
     *   *  5.2.1 接受单个目标迭代器的算法
         *  5.2.2 接受第二个输入序列的算法
     *  5.3 算法命名规范
     *   *  5.3.1 一些算法使用重载形式传递一个谓词
         *  5.3.2 \_if 版本的算法
         *  5.3.3 区分拷贝元素的版本和不拷贝的版本
 *  6.特定容器算法
 *   *   *  6.0.1 splice成员
         *  6.0.2 链表的特有操作会改变容器

> 标准库并未给每个容器添加大量的功能，而是提供了一组算法，这些算法中的大多数都独立于任何独立的容器。这些算法是通用的(generic)：它们用于不同类型的容器和不同类型的元素

# 1. 概述 #

假定有一个int的vector,希望知道vector中是否包含一个特定值  
使用标准库算法find

int val = 42;
    auto result = find(vec.cbegin(), vec.cend(), val)；
    cout << "The value" << val << (result == vec.cend() ? "is not present" : "is present") << endl;

### 1.0.1 算法如何工作 ###

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

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

# 2. 初识泛型算法 #

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

## 2.1 只读算法 ##

只会读取输入范围内的元素，而从不改变

int sum = accumulate(vec.cbegin(), vec.cend(), 0);//对vec求和，设初值为0

### 2.1.1 算法和 元素类型 ###

string sum = accumalate(vec.cbegin(), vec.cend(), string(""));//通过第三个参数显示的创建了一个string.
    string sum = accumalate(vec.cbegin(), vec.cend(), "");//错误，const char*上没有定义+运算符

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

> equal:用于确定两个序列是否保存相同的值  
> 第二个序列至少和第一个序列一样长

equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());

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

> 算法不会执行容器操作，因此它们自身不可能改变容器大小

### 2.2.1 算法不检查写操作 ###

`fill_n(dest, n, val)`

### 2.2.2 介绍back\_inserter ###

> **插入迭代器**(insert iterator) : 一种保证算法有足够空间来容纳输出数据的方法

### 2.2.3 拷贝算法 ###

> 1.拷贝(copy)算法是向目的位置迭代器指向的输出序列中的元素写入数据的算法  
> 2. 接收三个迭代器，前两个表示输入范围，第三个表示目的序列的起始位置、  
> 3. 将输入范围的元素拷贝到目的序列中去  
> 4. 传递给copy的目的序列至少要包含和输入序列一样多的元素

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

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

给定输入：

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

> 1.  为了消除重复单词，首先将vector排序，使得重复的单词相邻出现。
> 2.  一旦vector排序完毕，使用unique的标准库算法来重排vector，使得不重复的元素出现在vector的开始部分
> 3.  用erase成员来完成正真的删除操作

### 2.3.2 使用unique ###

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

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

# 3. 定制操作 #

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

### 3.1.1 谓词 ###

谓词是一个可调用的表达式，其返回结果是一个能用做条件的值。

### 3.1.2 排序算法 ###

## 3.2 lambda表达式 ##

### 3.2.1 介绍lambda ###

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

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

### 3.2.4 调用 find\_if ###

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

### 3.2.6 完整的biggies ###

## 3.3 lambda 捕获和返回 ##

### 3.3.1 值捕获 ###

### 3.3.2 引用捕获 ###

### 3.3.3 隐式捕获 ###

### 3.3.4 可变lambda ###

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

## 3.4 参数绑定 ##

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

> 解决向check\_size传递一个长度参数的问题

`#include<functional>`

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

### 3.4.3 使用placeholders名字 ###

### 3.4.4 bind的参数 ###

### 3.4.5 用bind重排参数顺序 ###

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

# 4. 再探迭代器 #

## 4.1 插入迭代器 ##

## 4.2 iostream迭代器 ##

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

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

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

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

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

## 4.3 反向迭代器 ##

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

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

# 5. 泛型算法结构 #

## 5.1 5类迭代器 ##

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

1.  **输入迭代器**(input iterator)
2.  **输出迭代器**(output iterator)
3.  **前向迭代器**(forward iterator)
4.  **双向迭代器**(bidirectional iterator)
5.  **随机访问迭代器**(random-access iterator)

## 5.2 算法形参模式 ##

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

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

## 5.3 算法命名规范 ##

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

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

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

# 6.特定容器算法 #

### 6.0.1 splice成员 ###

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