C++ Primer：第10章泛型算法

今天药忘吃喽~ 2023-07-23 14:55 42阅读 0赞

--------------------

### C++ Primer：第10章 泛型算法 ###

*  10.1 概述
 *  10.2 初始泛型算法
 *   *  10.2.1 只读算法（find、count、accumulate、equal）
     *  10.2.2 写容器元素的算法（fill、copy、replace）
     *  10.2.3 重排容器元素的算法（sort、unique）
 *  10.3 定制操作
 *   *  10.3.1 向算法传递函数
     *  10.3.2 lambda表达式
     *  10.3.3 lambda捕获和返回
     *  10.3.4 参数绑定
 *  10.4 再探迭代器
 *   *  10.4.1 插入迭代器
     *  10.4.2 流迭代器
     *  10.4.3 反向迭代器
 *  10.5 泛型算法结构
 *   *  10.5.1 5类迭代器
     *  10.5.2 算法形参模式
     *  10.5.3 算法命名规范
 *  10.6 特定容器算法

--------------------

# 10.1 概述 #

1.  泛型指可用于不同容器类型和元素类型，算法指实现了一些经典算法的公共接口。
2.  迭代器令算法不依赖与容器，但算法依赖于元素类型的操作。
3.  算法执行迭代器操作，而不会执行容器操作。算法永远不会**直接**改变底层容器大小。算法可能改变容器中保存的元素的值，也可能在容器内移动元素，但永远不会**直接**添加或删除元素

> **find(beg, end, val)**  
> **find\_if(beg, end, unaryPred)**  
> **find\_if\_not(beg, end, unaryPred)**

在\[beg,end)内查找元素。若找到，返回一个迭代器，指向第1个满足条件的元素。若未找到，返回end。

> **count(beg, end, val)**  
> **count\_if(beg, end, unaryPred)**

统计\[beg,end)内满足条件的元素的个数。返回一个计数器。

# 10.2 初始泛型算法 #

## 10.2.1 只读算法（find、count、accumulate、equal） ##

1.  只读算法只会读取其输入范围内的元素，而从不改变元素。
2.  对于只读算法，最好使用cbegin()和cend()。

> **accumulate(beg, end, init)**  
> **accumulate(beg, end, init, binaryPred)**

计算\[beg,end)内所有值的和。和的初值从init指定的值开始。返回类型与init的类型相同。

> **equal(beg1, end1, beg2)**  
> **equal(beg1, end1, beg2, binaryPred)**

判断\[beg1,end1)与从beg2开始的序列是否相等。若\[beg1,end1)中每个元素都与从beg2开始的序列中对应的元素相等，则返回true。

## 10.2.2 写容器元素的算法（fill、copy、replace） ##

1.  此类算法需确保输出序列中的元素个数不小于写入的元素个数。
2.  算法不检查写操作，注意目标容器不能为空。
3.  插入迭代器可以新建元素并赋值，可保证算法有足够元素空间来容纳输出数据。

> **fill(beg, end, val)**  
> **fill\_n(dest, cnt, val)**

将val赋值给输入序列。返回一个迭代器，指向输出序列中写入的最后一个元素之后的位置。

> **copy(beg, end, dest)**  
> **copy\_if(beg, end, dest, unaryPred)**  
> **copy\_n(beg, n, dest)**

将输入序列拷贝到输出序列。返回一个迭代器，指向输出序列中拷贝的最后一个元素之后的位置。

> **replace(beg, end, old\_val, new\_val)**  
> **replace\_if(beg, end, unaryPred, new\_val)**

将\[beg,end)中满足条件的元素替换为new\_val。返回void。

> **replace\_copy(beg, end, dest, old\_val, new\_val)**  
> **replace\_copy\_if(beg, end, dest, unaryPred, new\_val)**

将\[beg,end)中的元素拷贝到从dest开始的输出序列，并将满足条件的元素替换为new\_val。返回一个迭代器，指向输出序列中拷贝的最后一个元素之后的位置。

## 10.2.3 重排容器元素的算法（sort、unique） ##

1.  标准库算法对迭代器进行操作，而非对容器进行操作。故算法不能直接添加或删除元素。

> **sort(beg, end)**  
> **sort(beg, end, comp)**

对\[beg,end)中的元素进行排序。返回void。

> **unique(beg, end)**  
> **unique(beg, end, binaryPred)**  
> **unique\_copy(beg, end, dest)**  
> **unique\_copy(beg, end, dest, binaryPred)**

重排序列，通过覆盖实现“删除”相邻的重复元素。返回一个迭代器，指向不重复元素的尾后位置。

# 10.3 定制操作 #

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

1.  谓词包括一元谓词和二元谓词，它是一个可调用的表达式，其返回结果是一个能用作条件的值。
2.  算法若接受谓词作为参数，元素类型必须能够转换为谓词的参数类型。

> **stable\_sort(beg, end)**  
> **stable\_sort(beg, end, comp)**

对\[beg,end)中的元素进行排序。稳定排序算法，维持相等元素的原有顺序。返回void。

> **partition(beg, end, unaryPred)**

使用unaryPred划分\[beg,end)中的元素。返回一个迭代器，指向最后一个满足unaryPred的元素之后的位置。若所有元素都不满足unaryPred，返回beg。

## 10.3.2 lambda表达式 ##

1.  可调用对象：可使用调用运算符的对象或表达式。
2.  可调用对象包括函数、函数指针、重载了调用运算符的类、lambda表达式。
3.  lambda表达式表示一个可调用的代码单元，可理解为一个未命名的内联函数。
4.  lambda可以在函数内定义，必须使用尾置返回，不能有默认参数。
5.  lambda有捕获列表、参数列表、返回类型、函数体组成，其中参数列表和返回类型可省略，但必须包含捕获列表和函数体。

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

1.  当忽略返回类型，若函数体内只有一个return语句，则返回类型从返回的表达式的类型推断出来，若还含有其它语句，则返回类型是void。
2.  捕获列表只用于局部非static变量，lambda可以直接使用局部static 变量和在它所在函数之外声明的名字。

> **for\_each(beg, end, unaryOp)**

对输入序列中的每个元素应用可调用对象unaryOp。

> **stable\_partition(beg, end, unaryPred)**

使用unaryPred划分\[beg,end)中的元素。返回一个迭代器，指向最后一个满足unaryPred的元素之后的位置。若所有元素都不满足unaryPred，返回beg。保持满足unaryPred的元素的相对位置。

## 10.3.3 lambda捕获和返回 ##

1.  当向一个函数传递一个lambda时，同时定义了一个新类型和该类型的一个对象：传递的参数就是此编译器生成的类类型的未命名对象。
2.  值捕获（前提是变量可以拷贝）。参数的值是调用时拷贝，而被捕获的变量的值是在lambda创建时拷贝。
3.  引用捕获。当捕获一个指针，迭代器，或采用引用捕获方式，必须确保在lambda 执行时，绑定到迭代器、指针或引用的对象仍然存在，并且需要保证对象具有预期的值。
4.  尽量减少捕获的数据量，避免捕获指针或引用。
5.  隐式捕获。隐式捕获与显式捕获混用时，捕获列表第一个元素必须是&或=，且对于之后显式捕获的参数，其捕获方式必须隐式捕获的方式不同。
6.  默认情况下，捕获列表中值捕获的变量在lambda函数体内不可修改，若想修改，必须在参数列表后加上关键字mutable。对于引用捕获的变量，若它绑定的是const，则不可修改，反之可以修改。

> **transform(beg, end, dest, unaryOp)**  
> **transform(beg1, end1, beg2, dest, binaryOp)**

调用特定操作Op，将结果写入输出序列。返回一个迭代器，指向输出序列最后一个变换的元素。输入序列与输出序列可相同。

## 10.3.4 参数绑定 ##

1.  若只在一两个地方进行简单操作，则使用lambda表达式；若在很多地方使用相同的操作，或者操作复杂需要多条语句完成，则使用函数。
2.  若lambda捕获列表为空，通常可直接用函数替代；若捕获列表不为空，则用bind接受多的捕获变量。
3.  bind可看作一个通用的函数适配器，它可接受一个可调用对象，生成一个新的可调用对象来“适应”原对象的参数列表。

auto newCallable = bind(callable, arg_list)

1.  arg\_list中的\_n定义在std::placeholders。
2.  默认情况下，arg\_list中的不是\_n的参数被拷贝到bind返回的可调用对象中。故对于不可拷贝的参数，使用ref或cref来完成拷贝。

# 10.4 再探迭代器 #

<table> 
 <thead> 
  <tr> 
   <th align="left">迭代器</th> 
   <th align="left">描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">插入迭代器</td> 
   <td align="left">被绑定到一个容器上，用于向容器插入元素</td> 
  </tr> 
  <tr> 
   <td align="left">流迭代器</td> 
   <td align="left">被绑定到输入流或输出流上，用来遍历绑定的IO流</td> 
  </tr> 
  <tr> 
   <td align="left">反向迭代器</td> 
   <td align="left">迭代器反向移动，forward_list除外</td> 
  </tr> 
  <tr> 
   <td align="left">移动迭代器</td> 
   <td align="left">移动元素</td> 
  </tr> 
 </tbody> 
</table>

## 10.4.1 插入迭代器 ##

// 插入迭代器操作
    it = t
    *it, ++it, it++

1.  插入器类型：back\_inserter(c )、front\_inserter(c )、inserter(c, iter)。
2.  只有当容器支持push\_back，才能使用back\_inserter；只有当容器支持front\_inserter，才能使用front\_inserter。
3.  使用front\_inserter时，元素总是插入到容器第一个元素之前。故front\_inserter会颠倒插入的元素序列，而back\_inserter和inserter不会。

## 10.4.2 流迭代器 ##

1.  istream\_iterator从输入流读取数据，ostream\_iterator向输出流写入数据。
2.  istream\_iterator允许懒惰求值：当istream\_iterator被绑定到一个流上时，标准库并不保证迭代器立即从流读取数据，使用istream\_iterator时才会真正读取。
3.  当istream\_iterator未使用便销毁，或者从两个不同的对象同步读取同一个流，需注意何时读取数据。

// istream_iterator操作
    istream_iterator<T> in(is);
    istream_iterator<T> end;
    in1==in2, in1!=in2
    *in
    in->num
    ++in, in++

1.  ostream\_iterator必须绑定流，不允许空或表示尾后位置的ostream\_iterator。

// ostream_iterator操作
    ostream_iterator<T> out(os);
    ostream_iterator<T> out(os, d);
    out=val
    *out, ++out, out++

1.  只有类定义输入运算符（>>）便可创建istream\_iterator；只有类定义输出运算符（<<）便可创建ostream\_iterator。

## 10.4.3 反向迭代器 ##

1.  反向迭代器即容器中从尾元素向首元素反向移动的迭代器。
2.  forward\_list不支持递减。不能在流上反向移动。故不可能在一个forward\_list和流上创建反向迭代器。
3.  reverse\_iterator的base可将反向迭代器转换成普通迭代器，转换前后的两个迭代器指向相邻元素。

# 10.5 泛型算法结构 #

<table> 
 <thead> 
  <tr> 
   <th align="left">迭代器类别</th> 
   <th align="left">描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">输入迭代器</td> 
   <td align="left">只读不写，单遍扫描，只能递增</td> 
  </tr> 
  <tr> 
   <td align="left">输出迭代器</td> 
   <td align="left">只写不读，单遍扫描，只能递增</td> 
  </tr> 
  <tr> 
   <td align="left">前向迭代器</td> 
   <td align="left">可读可写，多遍扫描，只能递增</td> 
  </tr> 
  <tr> 
   <td align="left">双向迭代器</td> 
   <td align="left">可读可写，多遍扫描，递增递减</td> 
  </tr> 
  <tr> 
   <td align="left">随机访问迭代器</td> 
   <td align="left">可读可写，多遍扫描，支持全部迭代器运算</td> 
  </tr> 
 </tbody> 
</table>

## 10.5.1 5类迭代器 ##

1.  istream\_iterator是输入迭代器。要求输入迭代器的算法：find和accumulate。

// 输入迭代器支持的操作
    ==, != 
    ++
    * //只出现在赋值语句右侧
    ->

1.  ostream\_iterator是输出迭代器。要求输出迭代器的算法：copy。

// 输出迭代器支持的操作
    ++
    * //只出现在赋值语句左侧

1.  forward\_list上的迭代器是前向迭代器。要求前向迭代器的算法：replace。

// 前向迭代器支持的操作
    ==, !=
    ++
    *
    ->

1.  除forward\_list外，其它容器上的迭代器都是双向迭代器。要求双向迭代器的算法：reverse。

// 双向迭代器支持的操作
    ==, !=
    ++, --
    *
    ->
    iter[n]

1.  vector、string、deque、array和内置数组上的迭代器都是随机访问迭代器。要求随机访问迭代器的算法：sort。

## 10.5.2 算法形参模式 ##

alg(beg, end, args);
    alg(beg, end, dest, args); // 假定目标空间足够容纳写入数据，或者dest被绑定到插入迭代器
    alg(beg1, end1, beg2, args);// 假定从beg2开始的范围比[beg1, end1)至少一样大
    alg(beg1, end1, beg2, end2, args);

## 10.5.3 算法命名规范 ##

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

unique(beq, end) // 使用==比较元素
    unique(beq, end, comp) // 使用comp比较元素

1.  \_if版本的算法

find(beq, end, val) // 通过==找到值为val的元素
    find_if(beq, end, pred) // 通过pred找到第一个满足条件的元素

1.  区分拷贝元素与不拷贝元素的版本

reverse(beq, end) // 颠倒[beg, end)
    reverse_copy(beq, end, dest) // 将[beg, end)逆序拷贝到dest

# 10.6 特定容器算法 #

1.  list提供双向迭代器，forward\_list提供前向迭代器。
2.  链表交换元素时，是改变元素间链接，而非交换元素值。
3.  链表版本的算法会改变底层容器。remove删除指定元素，unique删除重复元素，merge和splice会删除给定链表中对应的元素。

<table> 
 <thead> 
  <tr> 
   <th align="left">list和forward_list成员函数版本的算法</th> 
   <th align="left">描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">lst.reverse()</td> 
   <td align="left">颠倒lst中元素的顺序，返回void</td> 
  </tr> 
  <tr> 
   <td align="left">lst.sort()<br>lst.sort(comp)</td> 
   <td align="left">对lst中的元素排序，返回void</td> 
  </tr> 
  <tr> 
   <td align="left">lst.remove(val)<br>lst.remove_if(pred)</td> 
   <td align="left">调用erase删除满足条件的元素，返回void</td> 
  </tr> 
  <tr> 
   <td align="left">lst.unique()<br>lst.unique(pred)</td> 
   <td align="left">调用erase删除重复的元素，返回void</td> 
  </tr> 
  <tr> 
   <td align="left">lst1.merge(lst2)<br>lst1.merge(lst2, comp)</td> 
   <td align="left">将lst2合并到lst1，返回void</td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <thead> 
  <tr> 
   <th align="left">list和forward_list中splice的参数</th> 
   <th align="left">描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">lst1.splice(p1, lst2)<br>lst1.splice(p1, lst2, p2)<br>lst1.splice(p1, lst2, b2, e2)</td> 
   <td align="left">将lst2的所有元素移动到lst1中p1之前的位置<br>将lst2中p2指向的元素移动到lst1中p1之前的位置<br>将lst2中[b2, e2)内的元素移动到lst1中p1之前的位置</td> 
  </tr> 
  <tr> 
   <td align="left">flst1.splice_after(p1, flst2)<br>flst1.splice_after(p1, flst2, p2)<br>flst1.splice_after(p1, flst2, b2, e2)</td> 
   <td align="left">将flst2的所有元素移动到flst1中p1之后的位置<br>将flst2中p2之后的一个元素移动到flst1中p1之后的位置<br>将flst2中[b2, e2)内的元素移动到flst1中p1之后的位置</td> 
  </tr> 
 </tbody> 
</table>