二、C++、STL标准模板库和泛型编程 ——关联式容器（侯捷）

￡神魔★判官ぃ 2024-03-23 11:15 118阅读 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标准模板库和泛型编程——关联式容器 （侯捷） ####

*  关联式容器
 *   *  rb\_tree 容器
     *   *  set、multiset 容器
         *  map、multimap容器
     *  hashtable 容器

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

## 关联式容器 ##

关联式容器，通过`key`来找值，查找速度非常快，可以看成是小型数据库。

关联容器：`set`、`multiset`、`map`、`multimap`，实现是使用 红黑树（高度平衡二叉树）

*  `set`的`key`既是`key`也是`value`。

![在这里插入图片描述][cffe1998dfb14bde9d999a78251e4a20.jpeg]  
`C++11`中有`Unordered`容器，但他也属于关联容器，实现使用`hash table`做的

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

### rb\_tree 容器 ###

`Red-Black tree`（红黑树）是**平衡二叉搜索树**（`balanced binary search tree`）中常被使用的一种。平衡二叉搜索树的特征：排列规则有利`search` 和`insert`，并保持适度平衡——无任何节点太深。

![在这里插入图片描述][46547711f22e464a916f91c57a52f049.png]

`rb_tree` 提供“遍历”操作及`iterators`.

*  按正常规则（`++ite`）遍历。便能获得**排序状态**（`sorted`）。

我们不应使用`rb_tree`的`iterators`改变元素值（因为元素有其严谨排序规则）。编程层面（`programming leve`）并未阻止此事。

*  如此设计是正确的，因为`rb_tree`即将为`set`和`map`服务（作为其底层支持）；
 *  而`map`允许元素的`data`被改变，只有元素的`key`才是不可以改变的。
 *  `rb_tree`提供两个`insertion`操作：`insert_unique()`和`insert_equal()`。前者表示节点的`key`一定是在整个`tree`中独一无二，否则安插失败(对红黑树没有任何影响)；后者表示节点的`key`可以重复。

使用红黑树，有5个模板参数：

![在这里插入图片描述][7407340d521d460daa821f8ec0d44c9a.jpeg]  
红黑树和双向链表都有一个不用的节点，双向链表是`end`后面的节点，红黑树是头节点。

第三个模板参数是指定如何取出`key`:

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

#### set、multiset 容器 ####

`set`/`multiset`以`rb_tree`为底层结构，因此有【**元素自动排序**】特性。

*  排序的依据是`key`，而`set`/`multiset`元素的`value`和`key`合一：`value`就是`key`。
 *  `set`/`multiset`提供“遍历”操作及`iterators`；按正常规则（`++ite`)遍历，便能获得排序状态（`sorted`）。
 *  我们无法使用`set`/`multiset`的`iterators`改变元素值（因为`key`有其严谨的排序规则）。`set`/`multiset`的`iterators`是其底部的`RB_tree`的`const-iterator`，就是为了禁止user对元素赋值。
 *  `set`元素的`key`必须独一无二，因此其`insert()`用的是`rb_tree`的`insert_unique()`。
 *  `multiset`元素的`key`可以重复，因此其`insert()`用的是`rb_tree`的`insert_equal()`。

![在这里插入图片描述][9eee1b1198c2469487d58a823903e437.jpeg]  
![在这里插入图片描述][e8a6403413d94ea39f6d473512f4ddb4.jpeg]  
**multimap**

multiset<int> c;
    c.insert(2);//会放在该放置的位置，放进去就会被排序
    c.begin();
    c.end();
    c.size();
    c.max_size();
    c.find(target);//内置find，红黑树

#### map、multimap容器 ####

`map`/`multimap`以`rb_tree`为底层结构，因此有【**元素自动排序**】特性。

*  排序的依据是`key`。
 *  `map`/`multimap`提供“遍历”操作及`iterators`；按正常规则（`++ite`)遍历，便能获得排序状态（`sorted`）。
 *  我们无法使用`map`/`multimap`的`iterators`改变元素的`key`（因为`key`有其严谨的排序规则）。但可以用它来改变元素的`data`。因此`map`/`multimap`内部自动将user指定的`key` `type`设定为`const`，如此便能禁止user对元素的`key`赋值。
 *  `map`元素的`key`必须独一无二，因此其`insert()`用的是`rb_tree`的`insert_unique()`。
 *  `multimap`元素的`key`可以重复，因此其`insert()`用的是`rb_tree`的`insert_equal()`。

![在这里插入图片描述][d37a4ab56a264541acc6fbd102a9a021.jpeg]  
![在这里插入图片描述][578e7dc5ff10482f888e178f9799ec25.jpeg]

`map`可以通过下标`[]`来插入:

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

### hashtable 容器 ###

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

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

使用`hash`表，碰撞冲突采用拉链表法.

如果`元素`的个数超过`bucket(篮子）`的个数，就会扩充`bucket`的个数，变为当前`bucket`大小的两倍附近的质数，然后每个元素`rehashing`，插入。这是一条经验法则。

需要指定6个模板参数！`ExtractKey` 是放入的 `Object` 的 `Key`，`EqualKey` 是比较函数，`sizeof(hashtable)=20`。  
![在这里插入图片描述][81b5301622ed400e818aa1e5d6320f21.jpeg]

使用 `hashtable` **最困难的事**决定使用什么`HashFcn`(`HashFcn`怎么设计没人教）。

具体写一个使用`hashtable`的例子：

![在这里插入图片描述][677eb9d914ed441d8ec10173f3239f4a.jpeg]  
![在这里插入图片描述][61d78ed899ef4afaa4228a875182ebd4.jpeg]

**标准库**没有提供现成C++的字符串即`hash<std::string>`，下面是C风格的字符串：

![在这里插入图片描述][b6ffdff167784ae0a4ba205036e026b6.jpeg]  
![在这里插入图片描述][a8ceb3b116ed4a0ab64f9ac4391575e9.jpeg]  
![在这里插入图片描述][aadd5448b2de4ef7879f31ba43320608.jpeg]

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

[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
[cffe1998dfb14bde9d999a78251e4a20.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/9c11d963b8234e148168f067d386f34f.png
[a148ee53fa2445c3a1d5289876da8616.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/877ecd3fc99c4ca39ffe677df3fdb950.png
[46547711f22e464a916f91c57a52f049.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/04df6872dcf94638ba23f59863e6a1f2.png
[7407340d521d460daa821f8ec0d44c9a.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/2464f65093e046d280a73a0ea480103e.png
[b8e237b4121149eabcc4fad70dd709c3.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/af22a06980d148159422181af076402e.png
[9eee1b1198c2469487d58a823903e437.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/db4eed3e8aa247dc86865327d7132d93.png
[e8a6403413d94ea39f6d473512f4ddb4.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/088f812477e842669d83e90db3b084d7.png
[d37a4ab56a264541acc6fbd102a9a021.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/308e0efbce294f85bfc23fd710981413.png
[578e7dc5ff10482f888e178f9799ec25.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/ca235c70c7384c45bca66d8d9b96e8d1.png
[683ad623e5b440f8b4348668f9d945fc.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/f4e4550a6fad44c5b13f42a2aa559db2.png
[81b5301622ed400e818aa1e5d6320f21.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/0615c4af0a3a47b2bcd13c9b9e646407.png
[677eb9d914ed441d8ec10173f3239f4a.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/ad68e4eff27748e9bd801c15c13debc3.png
[61d78ed899ef4afaa4228a875182ebd4.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/b30b55c66ba04beba9369626cf059a49.png
[b6ffdff167784ae0a4ba205036e026b6.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/3405b0aafcee406d9f31d5a984bb35fb.png
[a8ceb3b116ed4a0ab64f9ac4391575e9.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/2c4559f39255427d94fd82852d94f2bb.png
[aadd5448b2de4ef7879f31ba43320608.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/e88a45d1c9194f58b7626af2319db5fc.png