余睿的博客

浮生若梦,别多会少,不如莫遇

0%

STL容器的基本结构

引言

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

  • 线性结构容器(Sequence Containers)
    • 线性结构的容器是指在内存中的存储空间是连续编址的(如:vectorarray等),或是逻辑上是连续的(如:list)。数据中的元素存在一对一的关系。
  • 关联容器(Associative Containers)
    • 在上面的线性容器中,元素之间必然会存在着一个直接前驱或直接后继,但是对与半线性的数据结构来说,我们必须加以某种约定才能使得其间的元素有着某种联系,这也就是半关联容器的特点。如:Set/MultitsetMap/MultiMap
  • 不定序容器(Unordered Containers)
    • 对于不定序容器来说,他们的数据之间的关联没有了线性以及关联性的特点,如Unordered Set/MultisetUnordered Map/Multimap

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

STL容器的基本结构

Sequence Containers

Array

Array

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

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

vector

vector

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

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

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

Deque

Deque

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

List

List

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

Forward-List

Forward-List

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

Associative Containers

Set/Multiset

Set/Multiset

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

Map/Multimap

Map/Multimap

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

Unordered Containers

Unordered Containers

Unordered Set/Multiset

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

Unordered Map/Multimap

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

欢迎关注我的其它发布渠道