STL容器的基本结构

引言

容器被用来存储数据结构的数据，依据数据结构的不同特点，容器对于数据的组织形式也不同，大致可分为以下三种：

• 线性结构容器（Sequence Containers）
  • 线性结构的容器是指在内存中的存储空间是连续编址的（如：vector、array等），或是逻辑上是连续的（如：list）。数据中的元素存在一对一的关系。

• 关联容器（Associative Containers）
  • 在上面的线性容器中，元素之间必然会存在着一个直接前驱或直接后继，但是对与半线性的数据结构来说，我们必须加以某种约定才能使得其间的元素有着某种联系，这也就是半关联容器的特点。如：Set/Multitset或Map/MultiMap。
• 不定序容器（Unordered Containers）
  • 对于不定序容器来说，他们的数据之间的关联没有了线性以及关联性的特点，如Unordered Set/Multiset或Unordered Map/Multimap

他们之间的联系如下图所示：

Sequence Containers

Array

Array在内存中是一片连续编址的空间，需要在定义时即指定其大小，一旦定义后便不可再更改其大小。

由于其存储的特殊性，我们可以快速地通过下标访问到其中的某个元素。可以任意更改其中的元素，但是不能对其进行扩容。

vector

和Array的固定大小相比，vector显得更加地有弹性，可以根据数据规模对容器大小进行动态调整。

其底层是通过对数组进行封装而实现的，当容器空间不足以容纳新插入的数据时，其内部会调用扩容机制，按照原先大小的两倍申请一片新的空间，然后将数据复制到新的空间中，并释放原先的空间，从而达到扩容的目的。

由于其在内存中的位置是连续的，所以也可以通过下标的方式快速访问元素。

Deque

deque相当于一个双向的队列，两端可进可出，它的前面以及后面都可以进行扩充。对他的操作也只能在两端进行。

List

List实现的是一个双向链表，每一个元素在内存中都是独立存在的，由一根指向直接前驱以及一根指向直接后继的指针联系起来。本质为一个双向环状链表。

Forward-List

与双向链表不同，Forward-List中仅存在一根指针指向当前节点的下一个节点，在空间上较双向链表有所节省。其缺点是对数据的访问只能从头开始依次向下进行。

Associative Containers

Set/Multiset

Set/Multiset在实现上采用的是红黑树，这种结构的优点是便于快速查找。需要注意的是，Set中的数据是不允许重复的，Multiset中的数据是可以重复的。

Map/Multimap

Map/Multimap与Set/Multiset在实现上基本相同，唯一的区别在于Map/Multimap在数据的存储方式采用的是key-value的形式，可以通过key来检索对应的value。而在Set/Multiset中key即是value。

Unordered Containers

Unordered Set/Multiset

对于Unordered类型的数据来说，其底层采用了 HashTable的方式进行存储，通过huncfunc()函数来计算出一个特征值，然后将数据放到该特征值后面。但是对于huncfunc()来说，计算出来的值会产生碰撞，所以在每个bucket后面采用链表的方式来进行数据存储。

Unordered Map/Multimap

与Unordered Set/Multiset基本相同，唯一区别在于其是key-value形式。