深入解析 STL：数据结构及其内部实现机制

时间：11-18 现代故事提交错误

大家好，深入解析 STL：数据结构及其内部实现机制相信很多的网友都不是很明白，包括也是一样，不过没有关系，接下来就来为大家分享关于深入解析 STL：数据结构及其内部实现机制和的一些知识点，大家可以关注收藏，免得下次来找不到哦，下面我们开始吧！

容器（Container） —— 各种基本数据结构适配器（Adapter） —— 可以改变容器、迭代器或函数对象接口的组件算法（Algorithm） —— 各种基本算法，如排序、搜索.等迭代器（Iterator） —— 连接容器和算法函数对象（function object）分配器（allocator）主要总结了前两类：容器和容器适配器~

一、Container（容器）

顺序容器

1. vector内部数据结构：连续存储，如数组。随机访问每个元素需要O(1) 时间。在末尾添加或删除元素需要O(1) 时间，在中间或开头添加或删除元素需要O(n) 时间。元素可以动态添加或减少，内存管理是自动完成的，但程序员可以使用reserve()成员函数来管理内存。当内存被重新分配时，向量的迭代器变得无效（它指向的元素在操作前后不再相同）。当向量中插入超过capacity() - size()个元素时，内存将被重新分配，所有迭代器将失效；否则，指向当前插入元素之后的任何元素的迭代器都将无效。

建议：使用 vector 时，用 reserve() 成员函数预先分配需要的内存空间，它既可以保护迭代器使之不会失效，又可以提高运行效率。2. deque内部数据结构：连续存储或分段连续存储，取决于实现（分段连续存储更常见）。随机访问每个元素需要O(1) 时间。首尾添加元素所需时间为O(1)，中间添加或删除元素所需时间为O(n)（连续存储时）或O(1)（连续分片存储时））。可以动态增加或减少元素，内存管理自动完成，不提供内存管理的成员函数。添加任何元素都会使双端队列的迭代器无效。删除双端队列中间的元素将使迭代器失效。当从双端队列的头部或尾部删除元素时，只有指向该元素的迭代器变得无效。3. list内部数据结构：双向环状链表。不能随机访问元素。可以双向移动。在开头、结尾以及中间任意位置添加或删除元素需要O(1) 时间。可以动态添加或减少元素，内存管理自动完成。添加任何元素不会使迭代器失效。当一个元素被删除时，除了指向当前被删除元素的迭代器之外，其他迭代器都不会失效。4. slist内部数据结构：单向链表。它不能双向移动，只能从前向后移动。其他属性与列表相同。

建议：尽量不要使用 slist 的 insert、erase、previous 等操作。因为这些操作需要向前遍历，但是 slist 不能直接向前遍历，所以它会从头开始向后搜索，所需时间与位于当前元素之前的元素个数成正比。虽然 slist 专门提供了 insert_after、earse_after 等函数进行优化。但若经常需要向前遍历，建议选用 list。

关联容器

1. set内部数据结构：红黑树。键和值是相等的。 key是唯一的（如果插入的key已经存在，则插入不会成功，但不会报错）。默认情况下，元素按升序排序。如果迭代器指向的元素被删除，则迭代器失效。添加或删除元素的任何其他操作不会使迭代器失效。2. multiset内部数据结构：红黑树（一般红黑树等搜索二叉树不允许有重复的key，但是在这里插入相同的key时，该key会放在相等key的右侧。无论后面怎么进行插入或者删除操作，后面添加的key总是被认为比前面的大，这样就实现了一个multiset，但是根据key进行查找的时候，我们要自己做相同key的处理）。按键可以重复。其他功能与设定相同。3. hash_set内部数据结构：哈希表（数组 + 链表）。与set相比，其中的元素不一定是排序的，而是根据使用的哈希函数进行调度，可以提供更快的搜索速度（当然与哈希函数有关）。其他功能与设定相同。4. hash_multiset内部数据结构：哈希表（数组 + 链表）。键可能不是唯一的。其他功能与hash_set相同。5. map内部数据结构：红黑树。关键是独一无二的。元素按其默认键升序排序。如果迭代器指向的元素被删除，则迭代器失效。添加或删除元素的任何其他操作不会使迭代器失效。6. multimap内部数据结构：红黑树。键可能不是唯一的。其他功能与地图相同。7. hash_map内部数据结构：哈希表（数组 + 链表）。与map相比，其中的元素不一定按照key值排序，而是根据使用的hash函数进行调度，可以提供更快的搜索速度（当然也和hash函数有关）。其他功能与地图相同。8. hash_multimap内部数据结构：哈希表（数组 + 链表）。键可能不是唯一的。其他功能与hash_map相同。建议：