STL容器底层实现

引言

STL全程是Standard Template Library，也就是这个库通过C++ Template的方式实现的标准库。这里面包括容器、迭代器、仿函数、常用的基本算法等。 几乎所有的代码都采用了模板类或者模板函数，这相比传统的由函数和类组成的库来说提供了更好的代码重用机会。本文主要对日常开发中常用的容器进行总结。

vector

img

vector 的数据安排以及操作方式，与 array 非常相似。两者的唯一区别在于空间的运用的灵活性。array 是静态空间，一旦配置了就不能改变，vector 是动态数组。在堆上分配空间。vector 是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素（有保留内存，如果减少大小后内存也不会释放。如果新值>当前大小时才会再分配内存，这大大影响了 vector 的效率）。因此，vector 的运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必因为害怕空间不足而一开始要求一个大块的 array。

vector 动态增加大小，并不是在原空间之后持续新空间（因为无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大的空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此，对 vector 的任何操作，一旦引起空间重新配置，同时指向原vector 的所有迭代器就都失效了。

对最后元素操作最快（在后面添加删除最快），此时一般不需要移动内存。对中间和开始处进行添加删除元素操作需要移动内存。如果你的元素是结构或是类,那么移动的同时还会进行构造和析构操作，所以性能不高（最好将结构或类的指针放入 vector 中，而不是结构或类本身，这样可以避免移动时的构造与析构）。访问方面，对任何元素的访问都是 O(1)，也就是常数时间的。

总结：

vector 常用来保存需要经常进行随机访问的内容，并且不需要经常对中间元素进行添加删除操作。

STL源码剖析：

https://blog.csdn.net/weixin_40673608/article/details/87103742

list

相对于 vector 的连续空间，list 就显得复杂许多，它的好处是每次插入或删除一个元素，就配置或释放一个元素空间，元素也是在堆中。因此，list 对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素移除，永远是常数时间。STL 中的list 底层是一个双向链表，而且是一个环状双向链表。这个特点使得它的随即存取变的非常没有效率，因此它没有提供 [] 操作符的重载。

img

总结：

如果你喜欢经常添加删除大对象的话，那么请使用 list；

要保存的对象不大，构造与析构操作不复杂，那么可以使用 vector 代替。

list<指针> 完全是性能最低的做法，这种情况下还是使用 vector<指针> 好，因为指针没有构造与析构，也不占用很大内存

deque

deque 是一种双向开口的连续线性空间，元素也是在堆中。所谓双向开口，意思是可以在队尾两端分别做元素的插入和删除操作。deque 和 vector 的最大差异，一在于 deque 允许于常数时间内对起头端进行元素的插入或移除操作，二在于deque没有所谓容量观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接在一起。换句话说，像 vector 那样“因旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在 deque 是不会发生的。它的保存形式如下:

[堆1] --> [堆2] -->[堆3] --> ...

deque 是由一段一段的定量连续空间构成。一旦有必要在 deque 的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个 deque 的头端或尾端。deque 的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。避开了“重新配置，复制，释放”的轮回，代价则是复杂的迭代器架构。因为有分段连续线性空间，就必须有中央控制器，而为了维持整体连续的假象，数据结构的设计及迭代器前进后退等操作都颇为繁琐。

img

deque 采用一块所谓的 map 作为主控。这里的 map 是一小块连续空间，其中每个元素都是指针，指向另一段连续线性空间，称为缓冲区。缓冲区才是 deque 的存储空间主体。（ 底层数据结构为一个中央控制器和多个缓冲区）SGI STL 允许我们指定缓冲区大小，默认值 0 表示将使用 512 bytes 缓冲区。

支持[]操作符，也就是支持随即存取，可以在前面快速地添加删除元素，或是在后面快速地添加删除元素，然后还可以有比较高的随机访问速度和vector 的效率相差无几。deque 支持在两端的操作：push_back,push_front,pop_back,pop_front等，并且在两端操作上与 list 的效率也差不多。

在标准库中 vector 和 deque 提供几乎相同的接口，在结构上区别主要在于在组织内存上不一样，deque 是按页或块来分配存储器的，每页包含固定数目的元素；相反 vector 分配一段连续的内存，vector 只是在序列的尾段插入元素时才有效率，而 deque 的分页组织方式即使在容器的前端也可以提供常数时间的 insert 和 erase 操作，而且在体积增长方面也比 vector 更具有效率。

详细实现信息可以参考: http://c.biancheng.net/view/6908.html

如果deque中的map满了怎么办？

总结：

• vector 是可以快速地在最后添加删除元素，并可以快速地访问任意元素；
• list 是可以快速地在所有地方添加删除元素，但是只能快速地访问最开始与最后的元素；
• deque 在开始和最后添加元素都一样快，并提供了随机访问方法，像vector一样使用 [] 访问任意元素，但是随机访问速度比不上vector快，因为它要内部处理堆跳转。deque 也有保留空间。另外，由于 deque 不要求连续空间，所以可以保存的元素比 vector 更大。还有就是在前面和后面添加元素时都不需要移动其它块的元素，所以性能也很高。

因此在实际使用时，如何选择这三个容器中哪一个，一般应遵循下面的原则：

• 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用 vector；
• 如果你需要大量的插入和删除，而不关心随即存取，则应使用 list；
• 如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque。

stack

stack 是一种先进后出（First In Last Out , FILO）的数据结构。它只有一个出口，stack 允许新增元素，移除元素，取得最顶端元素。但除了最顶端外，没有任何其它方法可以存取stack的其它元素，stack不允许遍历行为。

img

以某种容器（ 一般用 list 或 deque 实现，封闭头部即可，不用 vector 的原因应该是容量大小有限制，扩容耗时）作为底部结构，将其接口改变，使之符合“先进后出”的特性，形成一个 stack，是很容易做到的。deque 是双向开口的数据结构，若以 deque 为底部结构并封闭其头端开口，便轻而易举地形成了一个stack。因此，SGI STL 便以 deque 作为缺省情况下的 stack 底部结构，由于 stack 系以底部容器完成其所有工作，而具有这种“修改某物接口，形成另一种风貌”之性质者，称为 adapter（配接器），因此，STL stack 往往不被归类为 container(容器)，而被归类为 container adapter。

queue

queue 是一种先进先出（First In First Out,FIFO）的数据结构。它有两个出口，queue 允许新增元素，移除元素，从最底端加入元素，取得最顶端元素。但除了最底端可以加入，最顶端可以取出外，没有任何其它方法可以存取 queue 的其它元素。

以某种容器 （ 一般用 list 或 deque 实现，封闭头部即可 ，不用 vector 的原因应该是容量大小有限制，扩容耗时 ）作为底部结构，将其接口改变，使之符合“先进先出”的特性，形成一个 queue，是很容易做到的。deque 是双向开口的数据结构，若以 deque 为底部结构并封闭其底部的出口和前端的入口，便轻而易举地形成了一个 queue。因此，SGI STL 便以 deque 作为缺省情况下的 queue 底部结构，由于 queue 系以底部容器完成其所有工作，而具有这种“修改某物接口，形成另一种风貌”之性质者，称为 adapter（配接器），因此，STL queue 往往不被归类为container(容器)，而被归类为 container adapter。

stack 和 queue 其实是适配器，而不叫容器，因为是对容器的再封装。

heap

heap 并不归属于 STL 容器组件，它是个幕后英雄，扮演 priority queue（优先队列）的助手。priority queue 允许用户以任何次序将任何元素推入容器中，但取出时一定按从优先权最高的元素开始取。按照元素的排列方式，heap 可分为 max-heap 和 min-heap 两种，前者每个节点的键值(key)都大于或等于其子节点键值，后者的每个节点键值(key)都小于或等于其子节点键值。因此， max-heap 的最大值在根节点，并总是位于底层array或vector的起头处；min-heap 的最小值在根节点，亦总是位于底层array或vector起头处。STL 供应的是 max-heap，用 C++ 实现。

priority_queue

priority_queue 是一个拥有权值观念的 queue，它允许加入新元素，移除旧元素，审视元素值等功能。由于这是一个 queue，所以只允许在底端加入元素，并从顶端取出元素，除此之外别无其它存取元素的途径。priority_queue 带有权值观念，其内的元素并非依照被推入的次序排列，而是自动依照元素的权值排列（通常权值以实值表示）。权值最高者，排在最前面。缺省情况下 priority_queue 系利用一个 max-heap 完成，后者是一个以vector 表现的 complete binary tree.max-heap 可以满足 priority_queue 所需要的“依权值高低自动递减排序”的特性。

priority_queue 完全以底部容器（一般为vector为底层容器）作为根据，再加上 heap 处理规则，所以其实现非常简单。缺省情况下是以 vector 为底部容器。queue 以底部容器完成其所有工作。具有这种“修改某物接口，形成另一种风貌“”之性质者，称为 adapter(配接器)，因此，STL priority_queue 往往不被归类为 container(容器)，而被归类为 container adapter。

set 和 multiset 容器

set 的特性是，所有元素都会根据元素的键值自动被排序。set 的元素不像 map 那样可以同时拥有实值(value)和键值(key)，set 元素的键值就是实值，实值就是键值，set不允许两个元素有相同的值。set 底层是通过红黑树（RB-tree）来实现的，由于红黑树是一种平衡二叉搜索树，自动排序的效果很不错，所以标准的 STL 的 set 即以 RB-Tree 为底层机制。又由于 set 所开放的各种操作接口，RB-tree 也都提供了，所以几乎所有的 set 操作行为，都只有转调用 RB-tree 的操作行为而已。

multiset的特性以及用法和 set 完全相同，唯一的差别在于它允许键值重复，因此它的插入操作采用的是底层机制是 RB-tree 的 insert_equal() 而非 insert_unique()。

map 和 multimap 容器

map的特性是，所有元素都会根据元素的键值自动被排序。map 的所有元素都是 pair，同时拥有实值（value）和键值（key）。pair 的第一元素被视为键值，第二元素被视为实值。map不允许两个元素拥有相同的键值。由于 RB-tree 是一种平衡二叉搜索树，自动排序的效果很不错，所以标准的STL map 即以 RB-tree 为底层机制。又由于 map 所开放的各种操作接口，RB-tree 也都提供了，所以几乎所有的 map 操作行为，都只是转调 RB-tree 的操作行为。

multimap 的特性以及用法与 map 完全相同，唯一的差别在于它允许键值重复，因此它的插入操作采用的是底层机制 RB-tree 的 insert_equal() 而非 insert_unique。

unordered_set、unordered_map

hashtable作为unordered_set和unordered_map的底层数据结构，是隐藏起来的，正常不会直接用到它，但要理解好unordered_set和unordered_map，需要先理解好hashtable

hashtable的底层数据结构是vector，vector中的元素是链表

vector代表篮子，初始化大小为53（GNU的做法），存的是结点指针

元素放进来的时候，会经过一个hash函数，找到对应的篮子，然后连在篮子的后面

img

当放进去的元素的数量超过vector的长度的时候，就会执行rehashing：

vector的大小会先变大为2倍，但不一定是2倍，会变成2倍左右的一个素数

vector变大后，原先的每一个元素都需要重新用hash函数计算并放到对应的篮子里

img

如果还需要rehashing的话，vector的大小会按照以下增长，这些数字是已经先算好的，vector在扩充的时候，不会再花时间去计算，而是直接在下面抓取对应的大小

img