二、C++、STL标准模板库和泛型编程 ——迭代器、算法、仿函数（侯捷）

妖狐艹你老母 2024-03-23 14:22 44阅读 0赞

> ***侯捷 C++八部曲笔记汇总 - - - 持续更新 ! ! !***  
> **一、C++ 面向对象高级开发**  
> [1、C++面向对象高级编程(上)][1_C]  
> [2、C++面向对象高级编程(下)][2_C]  
> **二、STL 标准库和泛型编程**  
> [1、分配器、序列式容器][1]  
> [2、关联式容器][2]  
> [3、迭代器、 算法、仿函数][3_]  
> [4、适配器、补充][4]  
> **三、C++ 设计模式**  
> **四、C++ 新标准**  
> **五、C++ 内存管理机制**  
> **六、C++ 程序的生前和死后**

#### 二、C++、STL标准模板库和泛型编程 ——迭代器、 算法、仿函数 （侯捷） ####

*  迭代器
 *   *  iterator\_category
 *  算法
 *   *  accumulate
     *  for\_each
     *  replace
     *  count
     *  find
     *  sort
     *  binary\_search
 *  仿函数 functors(六大部件中最简单的一种！)

> 使用一个东西，却不明白它的道理，不高明！—— 林语堂

> **阶段学习**  
> 使用C++标准库  
> 认识C++标准库（胸中自有丘壑！）  
> 良好使用C++标准库  
> 扩充C++标准库

所谓 `Generic Programming` （`GP`，泛型编程），就是使用 `template` （模板）为主要工具来编写程序。

*  `GP` 是将 `datas` 和 `methods` 分开来；
    
     *  `Containers`和 `Algorithms`可各自闭门造车﹐其间以`Iterator`连通即可·
     *  `Algorithms`通过`Iterators`确定操作范围﹐也通过`Iterators`取用 `Container`元素。
 *  `OOP(Object-Oriented Programming)`，企图将 `datas` 和 `methods` 关联在一起。

C++标准模板库`Standard Template` 最重要的六大部件(`Components`)：**容器**、**算法**、**仿函数**、**迭代器**、**适配器**、**分配器**

*  **容器**(`Containers`)是`class template`
 *  **算法**(`Algorithms`)是`function template` （其内最终涉及元素本身的操作，无非就是比大小！）
 *  迭代器(`Iterators`)是`class template`
 *  仿函数(`Functors`)是`class template`
 *  适配器(`Adapters`)是`class template`
 *  分配器(`Allocators`)是`class template`

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

## 迭代器 ##

前面说到迭代器中必须要有5种关联类型：`pointer`、`reference`、`iterator_category`(迭代器类型，比如说随机存取)、`value_type`(值存放类型)、`difference_type`(容器两个元素之间的距离类型)。

### iterator\_category ###

也有五种迭代器类型：**随机存取迭代器**（`array`、`vector`、`deque`）、**双向迭代器**（`list`、`红黑树容器`）、**单向迭代器**（`forward_list`，`hash类容器`）、**输入迭代器**（`istream迭代器`），**输出迭代器**（`ostream迭代器`）。

![在这里插入图片描述][72d873dc2eed4b8aaef51be2e2026f23.jpeg]  
既然是`tag`，为什么要用有继承关系的`class`来实现呢？

*  方便迭代器类型作为参数进行传递，如果是整数的是不方便的；还有一个原因，有些算法的实现没有实现特定类型的迭代器类别，就可以用继承关系去找父迭代器类别。

![在这里插入图片描述][c105ad16a5c44d9d9013a4a5feba2103.jpeg]  
**iterator\_category对算法的影响**

以这个`distance`函数为例，会根据迭代器的类别来调用不同的具体实现函数，

*  一个是只包含一个减法操作的语句，
 *  一个是包含一个`while`循环的语句，可想而知，当真实距离很大时，有`while`循环的具体实现函数效率会非常低下。

使用萃取机`iterator_traits`，虽然只有两种，但是这几种类型都是继承关系`is a` 父类`input_iterator_tag`，如果没有重载，最终都会落到`input_iterator_tag`。

![在这里插入图片描述][3794aec49e62417fa8b3683f65af7847.jpeg]

看一个特别能体现C++注重效率的体现：  
`copy`实现，到最终的实现细节，经过了很多判断，这些判断是为了找到最高效率的实现，就是判断迭代器的分类。

![在这里插入图片描述][ec59a614f06a49219126b29c745193f7.jpeg]  
![在这里插入图片描述][879119ef847b48cca54d3bc46b9c4326.jpeg]

## 算法 ##

`Algorithms`看不见`Containers`，对其一无所知；所以，它所需要的一切信息都必须从`Iterators`取得，而`Iterators`（由`Containers`供应）必须能够回答`Algorithm`的所有提问，才能搭配该`Algorithm`的所有操作。

template<typename Iterator>
    Algorithm(Iterator it1, Iterator it2){
        
    	...
    }
    
    template<typename Iterator, typename Cmp>//Cmp为传入的一个准则，比如比大小准则
    Algorithm(Iterator it1, Iterator it2, Cmp comp){
        
    	...
    }

### accumulate ###

template<class InputInterator, class T>
    T accumulate(InputIterator first, InputIterator last, T init){
        ...}
    
    //另外一个版本为：
    template<class InputInterator, class T, class BinaryOperation>
    T accumulate(InputIterator first, InputIterator last, T init， BinaryOperation binary_op){
        ...}

上面这个`binary_op`指明是一个二元操作数的函数，可以是**仿函数**（实质上是一个类），也可以是**函数**，只要是能够在该算法的**函数体内通过小括号调用**就行！！！！

*  也就是能够这么用：`binary_op(a, b)`;
 *  就算是在算法（函数）里面，也能够使用仿函数，但是传入的是仿函数的对象实例，而如果要传入函数的话，就传函数名就可以了。

int init = 100;
    int nums[] = {
        10,20,30};
    accumulate(nums, nums+3, init);//不指定具体怎么操作，默认为加法，输出160
    accumulate(nums, nums+3, init, minus<int>()); //这minus时减法的意思，所以输出为40

### for\_each ###

*  对容器区间内的元素做同样的事情。

template<class InputIterator, class Function>
    Function for_each(InputIterator first, InputIterator last, Function f){
        ...}

### replace ###

**1、 replace**

*  将容器区间内的元素进行替换，如果元素值等于`old_value`就把它替换为`new_value`.

template<class ForwardIterator, class T>
    void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value){
        ...}

**2、replace\_if**

*  在算法中看到 `if` ，就代表你要给他一个条件。
 *  `Predicate`为一个条件，判断式子（传回`真`或`假`），如果符合条件就进行替换

template<class ForwardIterator, class Predicate, class T>
    void replace_copy(ForwardIterator first, ForwardIterator last,  Predicate pred, const T& new_value){
        ...}

**3、replace\_copy**

*  范围内所有等同于`old_value`的都以`new_value`放置新的区间中，不符合原值的也放入新的区间

template<class InputIterator, class OutputIterator, class T>
    OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value)
    {
        ...}

### count ###

容器不带成员函数`count()`:

array, vector, list, forward_list, deque

容器带有成员函数`count()`（`红黑树`、`hash`容器中有自己的`count`）：

set /multiset
    map / multimap
    unordered_set / unordered_multiset
    unordered_map / unordered_multimap

**1、count**

*  区间内有和`value`相等的元素`count` \+ `1`。

template<class InputIterator, class T>
    typename iterator_traits<InputIterator>::difference_type
    count(InputIterator first, InputIterator last, const T& value){
        ...}

**2、count\_if**

*  区间内有符合`pred`条件的 `count` \+ `1`

template<class InputIterator, class Predicate>
    typename iterator_traits<InputIterator>::difference_type
    count_if(InputIterator first, InputIterator last, Predicate pred){
        ...}

### find ###

容器不带成员函数`find()`:

array, vector, list, forward_list, deque

容器带有成员函数`find()`（`红黑树`、`hash`容器中有自己的`find`）：

set /multiset
    map / multimap
    unordered_set / unordered_multiset
    unordered_map / unordered_multimap

**1、find**

*  循序查找，返回第一个和`value`相等的迭代器

template<class InputIterator, class T>
    InputIterator find(InputIterator first, InputIterator last, const T& value){
        ...}

**1、find\_if**

*  循序查找，查找符合条件的第一个元素的迭代器

template<class InputIterator, class Predicate>
    InputIterator find_if(InputIterator first, InputIterator last, Predicate pred){
        ...}

### sort ###

*  `sort`要求`RandomAccessIterator`

容器不带成员函数`sort()`:

array, vector, deque
    
    //已经排序，遍历自然形成sorted状态
    set /multiset
    map / multimap
    unordered_set / unordered_multiset
    unordered_map / unordered_multimap

容器带有成员函数`sort()`：下面这两种容器都不能 " `跳` "

list, forward_list

**sort**

*  默认从小到大排序，也可以指定自己的比较函数，可以是仿函数，可以是函数，仿函数必须传入该仿函数的实例。

sort(InputIterator first, InputIterator last, Function f)

### binary\_search ###

*  一定是在已排序状态下
 *  源码中就是调用`lower_bound`

template<class ForwardIterator, class T>
    bool binary_search(ForwardIterator first, ForwardIterator last, const T& value){
        ...}

![在这里插入图片描述][9e741f27cfe94a14a14523fef2ab484b.jpeg]

lower_bound(ForwardIterator first, ForwardIterator last, T target)
    upper_bound(ForwardIterator first, ForwardIterator last, T target)

`lower_bound`二分查找的一个版本，如果找到对应的值，则返回指向其中第一个元素的迭代器，如果不存在，则返回最适合安插这个`target`的点的迭代器 ，也就是说它返回迭代器指向第一个不小于`target`的元素，返回的是不破坏排序得以安插`target`的第一个适当位置。

## 仿函数 functors(六大部件中最简单的一种！) ##

*  只为算法而服务！
 *  `class`模仿函数，必须要重载小括号`()`。

有三大类，大该至少共有24个仿函数：

*  **算术类**（ `+` 、`-` 、`*` 、`/` 等）；
 *  **逻辑运算类**（`&&`、 `||` 等）；
 *  **相对关系类**（返回 `bool` ）。

**算术类：（Arithmetic）**

template<class T>
    struct plus : public binary_function<T, T, T>{
        
    	T operator()(const T& x, const T& y) const{
        
    		return x + y;
    	}
    };
    
    template<class T>
    struct minus : public binary_function<T, T, T>{
        
    	T operator()(const T& x, const T& y) const{
        
    		return x - y;
    	}
    };
    
    ...

**逻辑运算类：（Logical）**

template<class T>
    struct logical_and : public binary_function<T, T, bool>{
        
    	bool operator()(const T& x, const T& y) const{
        
    		return x && y;
    	}
    };
    
    ...

**相对关系类：（Relational）**

template<class T>
    struct equal_to : public binary_function<T, T, bool>{
        
    	bool operator()(const T& x, const T& y) const{
        
    		return x == y;
    	}
    };
    
    template<class T>
    struct less : public binary_function<T, T, bool>{
        
    	bool operator()(const T& x, const T& y) const{
        
    		return x < y;
    	}
    };
    
    ...

使用例子：

//using explicitly default comparison(operator <):
    sort(myvec.begin(), myvec.end(), less<int>());

为什么要把它们设计成**仿函数**呢？

*  因为要**传入算法**！要把它们作为**参数**！

上面的列举的几个都继承`binary_function`，说明有两个操作数，为什么要让仿函数继承这些类呢？

*  首先，继承他们，**不会增加**仿函数的内存大小；
 *  其次，继承了他们，会有了`first_argument_type`等的`typedef`，后续可以根据这个类型进行一些修改。
 *  以及**仿函数（`functors`）的可适配(`adaptable`)条件**：STL规定每个`Adaptable Function`都应挑选适当地继承`unary_fucntion`、`binary_function`等类，才能**融入**到STL中，才能**回答**`适配器`的问题 (就像`Traits`机要回答迭代器的问题一样)。

`unary_fucntion`和`binary_function`的定义：

//一个操作数(例如 对一个值取反)
    template<class Arg, class Result>
    struct unary_fucntion{
        //理论上大小为0，（sizeof为1）
    	typedef Arg argument_type;
    	typedef Result result_type;
    }
    
    //两个操作数
    template<class Arg1, class Arg2, class Result>
    struct bianry_fucntion{
        //理论上大小为0，（sizeof为1）
    	typedef Arg1 first_argument_type;
    	typedef Arg2 second_argument_type;
    	typedef Result result_type;
    }

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

> 觉得有帮助的话，点个赞呗（^ - ^）！

[1_C]: https://blog.csdn.net/weixin_43412762/article/details/129735013
[2_C]: https://blog.csdn.net/weixin_43412762/article/details/129789972
[1]: https://blog.csdn.net/weixin_43412762/article/details/129883667
[2]: https://blog.csdn.net/weixin_43412762/article/details/130112331
[3_]: https://blog.csdn.net/weixin_43412762/article/details/130232183
[4]: https://blog.csdn.net/weixin_43412762/article/details/130392743
[900a0ab3fcd74fbc89556eda9c4c2285.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/38b8dbdbea6d454f8979eda0f204b55c.png
[72d873dc2eed4b8aaef51be2e2026f23.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/6606af9a31ec40eaaa8a95927df5bf26.png
[c105ad16a5c44d9d9013a4a5feba2103.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/fbe870a95aa148b9b6671ca3b45f624b.png
[3794aec49e62417fa8b3683f65af7847.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/9cd4ced5233647698c1de8ba550419ef.png
[ec59a614f06a49219126b29c745193f7.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/33addf99abf74b7b88e130021a6035a1.png
[879119ef847b48cca54d3bc46b9c4326.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/57ccbc7a0f1944389453655e35d66d4b.png
[9e741f27cfe94a14a14523fef2ab484b.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/71c259718a994fc096945277c82fc773.png