转载自：C++STL的容器的底层实现详解

顺序容器

vector(向量容器）

特点

• 内存可2倍增长的动态数组
• 数据结构：线性连续空间
• 三个迭代器：start、finish、end_of_storage
• 在尾部插入和删除快，随即查找快。在前面或中间插入慢。
• capability：为降低空间配置时的速度成本，vector实际配置的大小可能比初始化所需要的大，以便将来的扩充。

动态增加大小，并不是在原空间之后接续新空间（因为无法保证之后尚有可供分配的空间），而是每次再分配原大小两倍的内存空间。因此，对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了。重新分配的空间为原来的两倍。

deque（双端队列)

特点

• 数据结构：一种双向开口的存储空间分段连续的数据结构，每段数据空间内部是连续的，而每段数据空间之间则不一定连续
  

deque与vector的最大差异 :
1.允许常数时间内对起首端进行元素的插入和删除。
2.deque没有所谓的容量概念，因为它是以分段连续空间组合而成，随时可以增加一段新的空间并连接起来。
deque的迭代器并不是普通指针，其底层实现非常复杂。因此，除非必要，应尽可能选用vector而非deque。对deque进行的排序操作，为了最高效率，可将deque先完整复制到一个vector上，然后vector排序后，再复制到deque。

上图deque有四部分数据空间，这些空间都是程序运行过程中在堆上动态分配的。

deque的中控器：
中控器（map）保存着一组指针，每个指针指向一段数据空间的起始位置，通过中控器可以找到所有的数据空间。如果中控器的数据空间满了，会重新申请一块更大的空间，并将中控器的所有指针拷贝到新空间中。

deque采用一块所谓的map（注意，不是STL的map容器）作为主控。这里所谓map是一小块连续空间，其中每个元素（此处称为一个节点，node）都是指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是deque的储存空间主体

deque的迭代器
deque是分段连续空间，维持其"整体连续"假象的任务，落在了迭代器的operator++ 和 operator-- 两个运算符重载身上。
deque的迭代器由四个属性组成，这四个属性是我们随机访问一个容器内元素的必要成分。

迭代器内部包含 4 个指针，它们各自的作用为：

• cur：指向当前正在遍历的元素；
• first：指向当前连续空间的首地址；
• last：指向当前连续空间的末尾地址；
• node：它是一个二级指针，用于指向 map 数组中存储的指向当前连续空间的指针。

借助这 4 个指针，deque 迭代器对随机访问迭代器支持的各种运算符进行了重载，能够对 deque 分段连续空间中存储的元素进行遍历。

1.start迭代器:绑定到第一个有效的map结点和该结点对应的缓冲区。
2.finish迭代器:绑定到最后一个有效的map结点和该结点对应的缓冲区。

deque的数据结构
deque除了维护一个指向map的指针外，也维护start、finish两个迭代器，分别指向第一缓冲区的第一个元素和最后缓冲区的最后一个元素（的下一位置）。此外，也必须记住目前的map大小，因为一旦map的所提供的空间不足，它将需要重新配置一个更大的空间，依然是经过三个步骤：配置更大的、拷贝原来的、释放原空间。

list

特点

• 有效利用空间
• 数据结构：环状双向链表
• 插入(insert)和接合(splice)操作都不会造成原来list的迭代器失效
• 删除（erase）操作仅仅使“指向被删除元素”的迭代器失效，其它迭代器不受影响
• 随机访问比较慢
• 任何位置元素的插入和删除，list是常数时间

使用场景：

1. 链表较长（单元数量很多）又无法提前知道数量，只能一个个 push_back，这时如果用 vector 效率受影响，因为 vector 增长过程中会不时的重新分配内存，每重新分配一次就要把 vector 中已有的数据都 copy 一遍。
2. 链表中按值保存一个自定义结构，结构中有资源指针（不是智能指针），虽然结构的析构函数会释放资源，但这时只能用 list，如果用 vector，出现 vector 重新分配内存后就会出错。如果实在想用 vector，可以给自定义结构写拷贝构造函数或在 vector 里保存结构的智能指针。
3. 链表中间位置频繁插入删除元素，用 list。

stack

栈是一种先进后出的数据结构。

底层实现：deque
在STL中栈的的默认容器是双端队列 deque，也可以使用 list 和vector 自定义队列，因为 list 和 vector 都提供了删除最后一个元素的操作（出栈）。

queue

队列queue是一种先进先出的数据结构，并且添加元素只能添加在尾部，删除元素只能删除首元素。

底层实现：deque
在STL中队列queue的默认容器是双端队列 deque，也可以使用 list 自定义队列，但是vector不行，因为vector不能提供删除第一个元素这个操作。

priority_queue

• 普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先出队的行为特征。
• 优先队列实现了类似堆的功能（其实底层就是用堆实现的）。
• STL默认使用 <操作符来确定对象之间的优先级关系（也就是从大到小排序，默认大根堆）
• 优先队列的底层是用堆实现的。 在优先队列中默认存放数据的容器是vector，在声明时也可以用deque(双向队列)
• 没有迭代器，不提供遍历功能

关联式容器

对于关联容器来说，不需要做内存拷贝和内存移动。

set

特点

• 数据结构：底层使用平衡的搜索树——红黑树实现
• set中的元素都是排序好的
• set中的元素都是唯一的，没有重复的
• 插入删除操作时仅仅需要指针操作节点即可完成，不涉及到内存移动和拷贝
• set中元素都是唯一的，而且默认情况下会对元素自动进行升序排列
• 支持集合的交(set_intersection),差(set_difference) 并(set_union)，对称差 (set_symmetric_difference) 等一些集合上的操作
  
  
• set内部元素也是以键值对的方式存储的，只不过它的键值与实值相同
• set中不允许存放两个实值相同的元素
• 迭代器是被定义成constiterator的，说明set的键值是不允许更改的，并且不允许通过迭代器进行修改set里面的值

为什么底层不用hash：
首先set，不像map那样是key-value对，它的key与value是相同的。关于set有两种说法，第一个是STL中的set，用的是红黑树；第二个是hash_set，底层用得是hash table。红黑树与hash table最大的不同是，红黑树是有序结构，而hash table不是。但不是说set就不能用hash，如果只是判断set中的元素是否存在，那么hash显然更合适，因为set 的访问操作时间复杂度是log(N)的，而使用hash底层实现的hash_set是近似O(1)的。然而，set应该更加被强调理解为“集合”，而集合所涉及的操作并、交、差等，即STL提供的如交集set_intersection()、并集set_union()、差集set_difference()和对称差集set_symmetric_difference()，都需要进行大量的比较工作，那么使用底层是有序结构的红黑树就十分恰当了，这也是其相对hash结构的优势所在。

multiset

允许键值重复。

hash_set

底层：hashtable
set有自动排序功能而hash_set没有。

map（key，value）

特点

• map中key的值是唯一的
• 数据结构：红黑树变体的平衡二叉树数据结构
• 提供基于key的快速检索能力
• 元素插入是按照排序规则插入的，不能指定位置插入
• 对于迭代器来说，可以修改实值，而不能修改key。
• 根据key值快速查找,查找的复杂度基本是log2n

map在进行插入的时候是不允许有重复的键值的，如果新插入的键值与原有的键值重复则插入无效，可以通过insert的返回的pair中第二个bool型变量来判断是否插入成功来判断是否成功插入.

pair<iterator, bool> insert(const value_type& x)

multimap

与 map 不同，multimap 可以包含重复键

hashtable

• 底层数组+链表实现，无论key还是value都不能为null，线程安全，实现线程安全的方式是在修改数据时锁住整个HashTable，效率低，ConcurrentHashMap做了相关优化
• 初始size为11，扩容：newsize = olesize*2+1
• 计算index的方法：index = (hash &0x7FFFFFFF) % tab.length

hash_map

底层：hashtable

• map的元素有自动排序功能而hash_map没有
• 底层数组+链表实现，可以存储null键和null值，线程不安全
• 初始size为16，扩容：newsize = oldsize*2，size一定为2的n次幂
• 扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入
• 插入元素后才判断该不该扩容，有可能无效扩容（插入后如果扩容，如果没有再次插入，就会产生无效扩容）
• 当Map中元素总数超过Entry数组的75%，触发扩容操作，为了减少链表长度，元素分配更均匀 计算index方法：index = hash& (tab.length – 1)
  

数组的特点是：寻址容易，插入和删除困难。

链表的特点是：寻址困难，插入和删除容易。

对于某个元素，我们通过哈希算法，根据元素特征计算元素在数组中的下标，从而将元素分配、插入到不同的链表中去。在查找时，我们同样通过元素特征找到正确的链表，再从链表中找出正确的元素。

unordered_map

无序

map、hash_map、unordered_map比较

1. 运行效率方面：unordered_map最高，hash_map其次，而map效率最低单提供了有序的序列。
2. 占用内存方面：hash_map内存占用最低，unordered_map其次(数量少时优于hash_map），而map占用最高。
3. 需要无序容器时候用unordered_map，有序容器时候用map。

无论从查找、插入上来说，unordered_map的效率都优于hash_map，更优于map；而空间复杂度方面，hash_map最低，unordered_map次之，map最大。