STL容器(vector、array、list、deque、set 、map 、stack、queue、priority_queue)的底层实现

STL数据结构整体介绍：

一、vector

1、底层数据结构： 数组
2、内存分配位置： 堆上
3、特点：

• 支持快速随机访问
• 扩容机制：vector 是动态数组，动态增加大小，并不是在原空间之后持续新空间（因为无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大的空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。

二、array

1、底层数据结构： 数组
2、内存分配位置： 栈上
3、特点：

• 定长数组，不支持动态扩容。

三、list

1、底层数据结构： 双向链表
2、内存分配位置： 堆上
3、特点：

• 支持快速增删，对于任何位置的元素插入或元素移除，永远是常数时间；

四、deque

1、底层数据结构： 是一种双向开口的连续线性空间，可以看作是list和vector的结合品(每个堆保存几个元素，然后堆和堆之间有指针连接)
2、内存分配位置： 堆上
3、特点：

• deque 采用一块所谓的 map 作为主控。这里的 map 是一小块连续空间，其中每个元素都是指针，指向另一段连续线性空间，称为缓冲区。缓冲区才是 deque 的存储空间主体。（ 底层数据结构为一个中央控制器和多个缓冲区）
• deque没有所谓容量观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接在一起。换句话说，像 vector 那样“因旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在 deque 是不会发生的。

五、set 和 multiset

1、底层数据结构： 红黑树/平衡二叉搜索树（RB-tree）
2、内存分配位置： 堆上
3、特点：

• 所有元素都会根据元素的键值自动被排序。
• set键值不可重复，multiset可重复。

六、map 和 multimap

1、底层数据结构： 红黑树/平衡二叉搜索树（RB-tree）
2、内存分配位置： 堆上
3、特点：

• 所有元素都会根据元素的键值自动被排序。
• map 的所有元素都是 pair，同时拥有实值（value）和键值（key）。
• map不允许两个元素拥有相同的键值，multimap允许。

七、unordered_map/ unordered_set/ unordered_multiset/ unordered_multimap

1、底层数据结构： 哈希表（哈希桶算法）
2、内存分配位置： 堆上
3、特点：

• 所有元素不会排序，但也与插入顺序不同，按hash值插入不同位置。

关联容器详见：关联容器底层数据结构：unordered_map/set基于hash表，不保证插入顺序；map/set基于红黑树，根据键自动排序

八、stack

1、底层数据结构： 一般用 list 或 deque 作为底部结构，封闭头部即可。不用 vector 的原因是容量大小有限制，扩容耗时。
2、内存分配位置： 堆上
3、特点：

• 符合“先进后出”。

九、queue

1、底层数据结构： 以 deque 为底部结构并封闭其底部的出口和前端的入口。
2、内存分配位置： 堆上
3、特点：

• 是一种先进先出（First In First Out,FIFO）的数据结构。

十、heap处理规则

1、底层数据结构： vector
2、内存分配位置： 堆上

十一、priority_queue

1、底层数据结构： 以vector为底层容器，再加上 heap 处理规则。
2、内存分配位置： 堆上
3、特点：

• priority_queue 是一个拥有权值观念的 queue。
• 其内的元素并非依照被推入的次序排列，而是自动依照元素的权值排列（通常权值以实值表示）。

vector、list、dequeue三者的选用原则：

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

参考资料：

1、C++ 学习笔记：STL 容器一些底层机制
2、C++ STL 几个容器的底层实现 收藏一下