二、C++、STL标准模板库和泛型编程——分配器、序列式容器（侯捷）

野性酷女 2024-03-24 12:27 42阅读 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标准模板库和泛型编程——分配器、序列式容器 （侯捷） ####

*  六大部件
 *  分配器allocators
 *  序列式容器
 *   *  array 容器
     *  vector 容器
     *  list 容器
     *  forward\_list 容器
     *  deque 容器
     *  queue 容器
     *  stack 容器

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

> **阶段学习**  
> 使用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]  
**使用例子：**

#include <iostream>
    #include <vector>
    #include <functional>
    
    using namespace std;//打开std这个命名空间
    
    int main()
    {
        
    	int ia[6] = {
         27, 210, 12, 47, 109, 83 };
    
    	//vector 为容器 ，allocator为分配器，可以不写
    	vector<int, allocator<int>> vi(ia, ia + 6);
    
    	//connt_if 为算法， vi.begin() 和 vi.end()为迭代器
    	cout << count_if(vi.begin(), vi.end(), 
    		not1(bind2nd(less<int>(),40)));
    	//not1 和 bind2nd 为仿函数适配器，less为仿函数
    
    	return 0;
    
    }

**容器分类**：**大致分为两种容器：序列容器，关联容器(key、value)**

*  序列容器：`array`、`vector`、`deque`、`list`、`forward-list`
 *  关联容器：`set`、`multiset`、`map`、`multimap`，实现是使用 红黑树（高度平衡二叉树）

![在这里插入图片描述][5a5b681aadb74a8187fbdc1696951aef.jpeg]

*  `C++11`中有`Unordered`容器，但他也属于关联容器，实现使用`hash table`做的

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

## 分配器allocators ##

*  容器需要一个东西来支持它对**内存的使用**，这个东西就是分配器，最好的情况下，我们不需要知道这个东西，所以需要一个**默认的分配器**。
 *  比如说`vector`的模版定义如下，会有一个默认的分配器`std::allocator<_Tp>`,如果不指定分配器，就会默认使用这一个

template<typename _Tp, typename _Alloc = std::allocator<_Tp>>
    class vector : protected _Vector_base<_Tp, _Alloc>

有以下**分配器**(不在标准库里面)：

array_allocator
    __mt_allocator //多线程
    debug_allocator
    __pool_allocator//内存池
    bitmap_allocator
    malloc_allocator
    new_allocator

一般不推荐**自己指定分配器**，如果自己指定了不好的分配器，会影响容器的性能！

**operator new & malloc**

C++层面用`operator new()` ，C 层面用`malloc()`

*  `allocator`只是以`::opreator new` 和 `::opreator delete` 完成 `allocate()` 和 `deallocate()`，没有任何特殊设计；
 *  `allocate()`会调用`malloc()`
 *  `deallocate()`调用`free()`  
    ![在这里插入图片描述][ef4975e7672042628c613ccdd8b9c604.jpeg]  
    我们需要的`size`是青色部分空间的大小，但是`malloc`会在青色部分外包裹其他东西。因此，会产生一些额外开销（如果要分配的区块小，那么额外开销就相对较大，不能忍受）。

16条链表，负责不同大小的内存分配。8字节对齐。每个内存块不会都带`cookie`。只会在链表的头尾有`cookie`。  
![在这里插入图片描述][d4617bbee77c4fc8b5e89dca79e722fb.jpeg]

下图以 缩排 形式表达 “ **基层和衍生层** ” 的关系：

*  这里所谓**衍生**，并非 **继承（inheritence）** 而是 **复合**（composition）

![9a7dd75482744bb4a0b230b4a4bdf72d.jpeg][]

[**操作符重载**][Link 1]：

*  当**运算符**出现在表达式中，并且其至少一个**操作数**具有**类类型**或**枚举类型**时，重载解析用于确定签名与以下内容匹配的所有函数中要调用的用户定义函数：

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

## 序列式容器 ##

### array 容器 ###

是C语言本来就有的东西，为什么要把他包装成容器？

*  因为要让他**有容器的行为，要有迭代器，才能配合算法**。
 *  **必须指定大小，不能拓展。**
 *  **没有构造函数，没有析构函数**！

![在这里插入图片描述][74220281da5345ae88e8d877b89e7d50.jpeg]

array<long, msize> c;
    c.size();
    c.front();
    c.back();
    c.data();//返回array的起点地址
    qsort(c.data(), msize, sizeof(long), compareLong); // 快速排序，指定地址，多少个元素，每个元素大小是多少，比较方法是怎样
    bsreach(&target, c.data(), msize, sizeof(long), compareLong); //二分查找，指定查找对象

### vector 容器 ###

**动态增长数组：**

*  容器容量按2倍增长，扩充的时候需要找到和当前容量两倍大的**连续的内存**才行！
 *  在进行增长的时候，会调用大量的构造函数。  
    有三个迭代器，所以`sizeof(vector)`的大小为12。

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

vector<int> c;
    c.push_back(1);
    c.size();
    c.capacity();
    c.front();
    c.back();
    c.data();//起始地址
    auto it = ::find(c.begin(), c.end(), target);//顺序查找

![在这里插入图片描述][6ce33a8f811b450cb318fa59a694bbbe.jpeg]

### list 容器 ###

*  **双向链表**：看源码，只有一个`protected`类型的数据`node`，这是一个`__list_node`结构的指针，这个结构中包含`list`节点的**值**，指向 **前一个节点** 和 **后一个节点** 的指针。

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

**上面这个图的设计有这么两个问题**：(针对这个两个问题，GNU4.9作出了改进！)

1.  `__list_node`中`prev`和`next`使用的是`void*`类型的指针，而不是一个确切的`__list_node`类型，传入的值会做一个类型转化；
2.  `iterator`的定义有三个模板参数，即`T`, `T&`, `T*`，这个显然是传一个 `T` 就够了，只要在模板类进行推导就行。

**一定要有5个typedef，也就是下图中括号行。这就牵扯到了迭代器的`Traits`设计。**

> 迭代器需要遵循的原则：迭代器是连接容器和算法的中间件，因此迭代器必须能够回答算法的一些提问，这样算法才能更好的对容器进行操作。这 **5种迭代器** 关联类型分别为：`iterator_category`(迭代器类型)、`value_type`(值存放类型)、`difference_type`(容器两个元素之间的距离类型)、`pointer`、`reference`【后两种很少用！】。

如果一个**迭代器**不是一个**类**

*  会引入`Traits`（特征、特性、特值）机作为中间层，接收类迭代器和指针迭代器，会做相应的工作（模板偏特化），得到指针的5种迭代器关联类型。

![在这里插入图片描述][8962fcfbddbe4ff8a9a00620718ba25d.jpeg]

*  还包含一个**迭代器**，这个迭代器就是一个`pointer like`，重载了一些操作符，包括：`前++`，`后++`，`->`，`*`。
    
     *  这些容器都会模拟 `int` 型的操作方法，所以 `list` **不允许** `后++两次`;
     *  因此，`后++`的重载是返回`self`类型，而不是`self&`。

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

### forward\_list 容器 ###

单向链表，只提供头插法，尾插效率太低，计算`size`效率太低，寻找`back`效率太低，不提供  
![在这里插入图片描述][c1d4f5ddfe4f4aa4bd3fd2ca24498a12.jpeg]

forward_list<int> c;
    c.push_front(); //头插
    c.max_size();
    c.front();
    //无c.back()
    //无c.size()

### deque 容器 ###

类似`vector`，两边都能扩充，**逻辑上是连续的**，但是 **物理上是分段连续的** 。

*  **连续是假象，分段是事实**；
 *  有一个`map`来存放这些段。
 *  当一个`buffer`使用完的之后，会有一个新的`buffer`，这个`buffer`的地址放在`map`中。
 *  这个`buffer`一次分配多大呢？这会影响到这个容器的效率～

![在这里插入图片描述][12eebea64e394ce894151ff6ea453d2d.jpeg]  
`map`会将这些分段的`node`给串起来；`node`指向在`map`的位置：

*  `first`和`last`指的是`node`的边界
 *  `cur`指向当前`node`的元素

还会有一个`start`和`finish`的迭代器，保存双向队列的两端头元素。  
`map`不够大，也会二倍扩充。

![在这里插入图片描述][7ad98be186244152b0a59fefff821f48.jpeg]  
`deque`还需要指定`buffer_size`，也就是每一个`buffer`容纳的元素个数，默认是0，就会做相应的操作来存放默认数量的元素，但是肯定不会是让一个`buffer`存放0个元素的。迭代器类型用的是随机存取（也就是连续的）是`deque`类做的伪装。迭代器做了模拟连续空间的操作。

![在这里插入图片描述][33c8df79d1df4f829e656f3b119a080a.jpeg]

deque<int> c;
    c.push_back(1);
    c.pop_back();
    c.push_front(1);
    c.pop_front();
    c.max_size();
    c.front();
    c.back();

### queue 容器 ###

`queue`和`stack`没有自己的数据结构，是借用`deque`,是容器适配器，内涵一个`deque`，并封住某些功能。

*  不提供遍历操作, 所有不提供迭代器：

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

queue<int> c;
    c.push(1);
    c.pop();
    c.front();
    c.back();
    c.size();

### stack 容器 ###

`stack`是容器适配器, 内涵一个`deque`，并封住某些功能。  
![在这里插入图片描述][89503b0f86474b16b05cb9e7e4d18d76.jpeg]

stack<int> c;
    c.push(1);
    c.pop();
    c.top();
    c.size();

> 源码中`queue`和`stack`提供第二个模板参数来指定实现`stack`和`queue`的容器，可以使用`list`和`deque`；  
> 不能够使用`vector`、`set`、`map`实现，因为不允许任意放元素 ，转调用也不能调用不到正确的函数。

**注：个人学习笔记，如有不足，欢迎指正！**

[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/24/fc0dd344dde442aeb74e3961c589a546.png
[5a5b681aadb74a8187fbdc1696951aef.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/1ad352f750b54bfb8a7345f207ac7968.png
[a148ee53fa2445c3a1d5289876da8616.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/987af16c705f4ca78006b69b53e3dde2.png
[ef4975e7672042628c613ccdd8b9c604.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/4c869d1e22f64f59934145df55eb70c2.png
[d4617bbee77c4fc8b5e89dca79e722fb.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/8a3199aea3274a84ae2866bd3b2279ac.png
[9a7dd75482744bb4a0b230b4a4bdf72d.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/a907d028085f444d94cb270314c3c2a6.png
[Link 1]: https://en.cppreference.com/w/cpp/language/operators
[463ecee8317849bbbac0eb4fcbd70e6f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/38439d56be224295b75d3a6119209640.png
[74220281da5345ae88e8d877b89e7d50.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/76e810880a8443ee8070c7099b48599f.png
[c54613742106438aaa9fcf4d506b5d72.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/d69997a4992a4d37802d91d41f4ebb0d.png
[6ce33a8f811b450cb318fa59a694bbbe.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/2e1e4179b2ee414a8a5ce2f0ca5bf2f8.png
[b958818625e542569752e8eae275d3fc.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/eb96fb0e6391415eafb399cd0020e13e.png
[8962fcfbddbe4ff8a9a00620718ba25d.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/5e10bb31ee5849baa6efcc532aa7480f.png
[b18f8aa9b6d442ca8cba361cc682bd18.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/34c778702cf246f9a93515a8734aa8bb.png
[c1d4f5ddfe4f4aa4bd3fd2ca24498a12.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/854fcd955e084e29a1f3388aeca5477a.png
[12eebea64e394ce894151ff6ea453d2d.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/6844a04bce1645a181b505c6e5a77ccc.png
[7ad98be186244152b0a59fefff821f48.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/481f6eed81b74fb79649a89abf2cad60.png
[33c8df79d1df4f829e656f3b119a080a.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/035f978f9bec47c8b62b12f49ac235c3.png
[aff6c5d69cf542bc88011dfe9c75ec05.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/63487aee8d8a466dab8dca6d883b7347.png
[89503b0f86474b16b05cb9e7e4d18d76.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/580d7c322fb442559d10c69481d15ecf.png