C++ STL 容器底层实现

一、关键词

I：容器

1、顺序容器：底层是链表和数组
    array(数组)、vector(可变数组)、deque(双端队列)
    forward_list(单向链表)、list(双向链表)
2、关联容器：底层是红黑树
    set(集合)、mulitset(可重复元素的集合)
    map(字典)、multimap(可重复键值的字典)
3、无序关联容器（哈希表）
    unordered_set(无序集)、unordered_multiset(可重复元素的无序集)
    unordered_map(无序字典)、unordered_multimap(可重复的无序字典)

II:容器适配器

stack(堆栈)、queue(队列)、priority_queue(优先级队列)

二：知识点

补充知识1：

逻辑结构：线性、图状、树、集合
存储结构：顺序、链式、索引、散列(hash)

补充知识2

关联容器底层是红黑树即二叉搜索树。红黑树满足如下规则：

    I：每个节点不是红色就是黑色；
    II：根节点(第一个节点)必为黑色；
    III：红色节点的子节点不能为红色；
    IV：任一节点至树尾端(null)的任何路径包含的黑色节点数必须相同。

注意：当新插入的节点不满足上述规则是，则需要调整颜色并旋转树形，使其仍保持上述性质的平衡二叉搜索树。红黑树是有二叉树发展而来：二叉树->二叉查找树->二叉平衡树->红黑树,所以继承了平衡二叉树的左边所有节点比根节点小，右边所有节点比根大。

1、array(数组)在头文件中，声明时确定容器大小。在声明时指定类型T与数组大小N，即array<int,5>。数组实现。

 性能：查找：array任意位置为O(1)。
      插入：末端O(1)，其他位置O(n)
      删除：末端O(1),其他位置O(n)

2、vector(可变数组)在头文件中，动态数组，其中元素连续存储在一个内存中，但vector的内存大小是可变的--在初始分配的内存填满元素后再添加元素使，vector的alloter,会重新分配内存空间，一般是原来的2倍，各家调教不同，然后整体拷贝旧元素到新的内存空间中，这个步骤是运行期间自动完成的。指定类型即可，如vector,也可是自定的结构体等等。

 性能：查找：vector任意位置为O(1)。
      插入：末端O(1)，其他位置O(n)
      删除：末端O(1),其他位置O(n)

3、deque(双端队列)，特点是只在头尾两端进行操作。头文件为,即deque,T为类型。deque是双端队列，其底层实现是用一系列连续的固定大小的数组进行组合，给人以“我”是连续的内存空间的感觉，与vector相比，在数据量大的情况下更占优势。由中控器与缓冲器实现，中控器中的每个元素指向一段内存空间，所指向的内存空间即为缓冲器，缓冲器是用来存储数据的。需维护两个迭代器start和finish，分别指向第一个元素缓冲器的第一个元素和最后缓冲器的最后一个元素，此外俩个迭代器都指向中控器。

 性能：查找：--
      插入：头尾O(1)
      删除：头尾O(1)

4、forward_list(单向链表)，数据只能进行单向访问，其头文件<forward_list>,即forward_list,需指定T存储类型。

 性能：查找：O(n)
      插入：头O(1)，平均O(n)
      删除：头O(1),平均O(n)

5、list(双向链表),使用时包含头文件，环形双向链表，具有prev和next指针以及数据域data，分贝指向当前节点的前一个和后一个节点。链表的第一个node不存储数据，它的begin是从第二个node算起，链表最大的特点是大小可变切存储非连续，包含指针造成空间浪费。

     性能：查找：O(n)
      插入：O(1)
      删除：O(1)

6、 set(集合)底层数据结构为红黑树，头文件为，另外可提供compare函数，有默认比较函数，默认是升序。唯一键。

7、multiset(可重复元素的集合)底层红黑树，头文件为，与set类似，但其可以包含相同的键。

8、map(字典)底层数据结构为红黑树,字典中的键值具有唯一性。头文件为

9、multimap(可重复键值的字典)底层红黑树，头文件

三、实际运用

//***