工作准备06-STL容器

叁歲伎倆 2022-09-07 14:38 178阅读 0赞

# STL容器 #

## 序列式容器 ##

### 1.vector ###

\*\* vector内部\*\*  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70]  
vector较常使用的成员函数有：begin()、end()、size()、capacity()、empty()、operator\[\]、front()、back()…  
vector在进行两倍扩充的时候需要大量调用析构函数和构造函数，因为它要释放之前空间中申请的空间，并且需要重新开辟空间去存放新放入的元素。  
GUN4.9版本中vector容器的内部构造如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 1]  
可以看出vector迭代器占12个字节（内部有三个指针）。

### 2.array ###

TR1中的array内存模型：  
![在这里插入图片描述][1ab4020a346d4e0a80f55e97739b6cd6.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 2]

### 3.forward\_list ###

forward\_list是一个单向链表，在GUN4.9新加进来的：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 3]

### deque ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 4]  
如上图所示，deque分段连续。  
deque的控制中心是一个vector，所以其扩充是和vector扩充方式一样，两倍扩充。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 5]  
deque的迭代器大小有16个字节。  
deque本身有40个字节。  
deque成员函数insert()内部判断插入位置点离起始点和结束点哪个比较近，之后插入传入迭代器中的位置中。  
deque的迭代器++和–操作重载如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 6]  
GUN4.9中定义deque：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 7]

### stack和queue ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 8]  
stack和queue都是通过底层调用deque来实现自己的功能的。  
stack和queue不能遍历，也不提供iterator。  
stack和queue不仅可以使用deque作为底层也可以使用list作为底层使用，但是不能使用vector、set、map作为底层进行构造。

## 关联式容器 ##

关联式容器的查找和安插数据都很快，因为其底层实现决定了这些特性都很快。  
关联式容器底层有两种实现方式：rb-tree和hash table。

### rb-tree ###

rb tree是平衡二叉搜索树。  
GUN2.9版本rb tree实现：  
rb-tree有12个字节  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 9]  
GUN4.9版本实现：  
每个rb-tree有24个字节  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 10]

### set/multiset ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 11]  
set容器底部源码：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 12]  
因为set和multiset底层使用rb-tree来进行实现功能，所以我们可以称其为容器适配器（container adapter）。  
multiset容器气势上与set差不多，但是其底层的插入是使用insert\_equal()来实现的，所以其可以插入key值相同的元素。

### 容器map、multimap ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 13]  
map底层实现：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 14]  
map通过\[\]进行查询元素时，如果map里面存在这个索引值对应的元素，则返回这个元素的迭代器，如果map里面不存在此元素，则将此索引值按照一个元素值插入到map中。

### hashtable ###

一开始的时候是按照左上方的方式实现hashtable的，但是如果同一个链表下的元素过多的时候查找的时候速度会特别的慢，所以有了如下调整：在元素的个数大于等于篮子的个数的时候需要重新rehashing，大散散列表重新进行计算并排列元素，一般扩充篮子的数量是质数（这里起始是53（按照平台不同而不同），以后就是扩充到53倍数最近的一个质数，也就是右上角的个数，这些数字是在GUN2.9版本下）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 15]  
hashtable的底层实现为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 16]

### unordered ###

到了C++11之后hashtable容器改名为unordered，如：hash\_set、hash\_multiset、hash\_map、hash\_multimap------>unordered\_set、unordered\_multiset、unordered\_map、unordered\_multimap。  
下面测试是在GUN4.9版本下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 17]  
容器的内容就以上这么多了，以上截图都是侯捷老师网课的内容。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70]: /images/20220829/e1ef40bba98542f092904d25f14bfc2e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 1]: /images/20220829/74f04c3a6ae3490ca70a2b158003d31d.png
[1ab4020a346d4e0a80f55e97739b6cd6.png]: /images/20220829/a84f0c86c1304a3586ebb4113a2a947c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 2]: /images/20220829/027a13e6d87a4979ad2142e6bee2fda7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 3]: /images/20220829/3256ce7981b6458690ff1c82aad67d3f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 4]: /images/20220829/166fcfe4cdb44dd0b3d1b1316a50647a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 5]: /images/20220829/eb9b367157364e59a600bb460457e7b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 6]: /images/20220829/d378496613b04a85ae30851dd87559b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 7]: /images/20220829/da911b11e09c401583e7b6fc61c3b3bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 8]: /images/20220829/85b7c0c73ee64048ae2e4e8c473b1652.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 9]: /images/20220829/41ef3bb03f69449aa53300ce2be09aca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 10]: /images/20220829/530c57e5fcb04575aaad706036a53858.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 11]: /images/20220829/a8adbd2c386540f297430f1db909ec5c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 12]: /images/20220829/aa5f851b8f4c4664b6d9c6f1b6925cc3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 13]: /images/20220829/881087d7a6f34b0b88d0f0c57570eac2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 14]: /images/20220829/0302cebc4b594e62a85e45a72088c6bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 15]: /images/20220829/17b184adb8814c84a6cfd5d38d2d91aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 16]: /images/20220829/bc4913bea0e74676ac59fab0c9962b5a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 17]: /images/20220829/523345c8905a4845897bc64cb6255a11.png