STL源码剖析--读书笔记（3）

- 日理万妓 2021-11-11 05:04 323阅读 0赞

# 写在前面的话 #

前一篇博文介绍了**迭代器**，接下来介绍一下STL的大部头–**容器**。这一篇首先介绍**序列式容器**。

# 容器概览与分类 #

STL的容器是将运用最广的一些数据结构实现出来。众所周知，常用的数据结构不外乎 array, list, tree, stack, queue, hash table, set, map 等。根据数据在容器中的排列特性，这些数据结构分为序列式和关联式两种，因此容器也分为序列式容器和关联式容器。序列式容器有：array, vector, heap, priority-queue, list, slist, deque, stack, queue。关联式容器有：rb-tree, set, map, multiset, multimap, hashtable, hash-set, hash-map, hash-multiset, hash\_multimap。  
　　其中，heap是以vector为底层来实现的，priority-queue又是以heap为底层实现。而stack和queue都是以deque为原型通过配接器配接而来。关联式容器中的 set map multiset multimap 都是以 rb-tree 为底层实现, hash-set hash-map hash-multiset hash\_multimap又都是以 hashtable 为底层实现。  
　　需要注意的是，序列式容器都可序，但未必有序。接下来分别介绍各容器。

# vector #

## vector概述 ##

vector 的数据安排以及操作方式与 array 非常相似。两者唯一的差别在于空间的运用的灵活性。array 是静态空间，一旦配置了就不能改变，要换一个大（小）一点的空间，首先得配置一块新空间，然后从旧址一一搬往新址，再把原来的空间释放。vector 是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。因此使用 vector，我们再也不必因为害怕空间不足而一开始就要求一个大块头 array 了。

## vector的迭代器 ##

vector 维护的是一个连续的线性空间，所以不论其元素型别为何，普通指针都可以作为 vector 的迭代器而满足所有必要条件。因此 vector 的迭代器是普通指针。vector 支持随机存取，而普通指针也正有这样的能力，所以 vector 提供的是 random access iterators。

## vector的数据结构 ##

vector的数据结构比较简单，是线性连续空间。它内部维护有三个迭代器（指针）：start表示目前使用空间的头，finish表示目前使用空间的尾，end\_of\_storage表示目前可用空间的尾。  
　　当我们以push\_back()将新元素插入于vector尾端时，该函数首先检查是否还有备用空间，如果有就直接在备用空间上构造元素，并调整迭代器 finish，使 vector 变大。如果没有备用空间了，就扩充空间，即动态增加大小，这并不是在原空间之后接续新空间（因为无法保证原空间之后有可供配置的空间），而是以原大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此，对 vector 的任何操作，一旦引起空间重新配置，指向原 vector 的所有迭代器就都失效了。

# list #

## list概述 ##

list是一个链表，是由一个一个节点组成的，每一个节点结构内部有两个指针，分别指向前一个节点和后一个节点，还有一个数据域来存放节点数据。list的好处是每次插入或删除一个元素，就配置或释放一个元素空间。因此，list对空间的利用率很高，一点也不浪费。而且，对于任何位置的元素插入或元素移除，list永远是常数时间。

## list的迭代器 ##

list不再能够像vector一样以普通指针作为迭代器，因为其节点不保证在存储空间中连续存在。list迭代器必须有能力指向list的节点，并且有能力进行正确的递增、递减、取值、成员存取等操作。也就是说，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取用的是节点的成员。  
　　由于STL的list是一个双向链表。迭代器必须具备前移、后移的能力，所以list提供的是bidirectional iterators。list在插入和接合操作的时候都不会造成原有的list迭代器失效，在删除操作的时候只有指向被删元素的那个迭代器失效，其他迭代器不受任何影响。

## list的数据结构 ##

list不仅是一个双向链表，而且还是一个环状双向链表，所以它只需要一个指针，便可完整表现整个链表。如果让该指针（注意：此指针并非前面所说的节点内部的指针，这里的指针是指向每个节点的指针）指向刻意置于尾端的一个空白节点，便能符合STL对于“前闭后开”区间的要求，成为list迭代器。list作为双向链表，在头部和尾部都可以插入数据。

# deque #

## deque概述 ##

deque是一种双向开口的连续线性空间。所谓双向开口，意思就是可以在头尾两端分别做元素的插入和删除操作。deque和vector的不同主要有两点：（1）vector是单向开口的空间，虽然也能在头部插入元素，但是效率极差，而deque可以在常数时间内对头部进行插入或移除操作。（2）deque没有容量的概念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。而vector是因旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间。  
　　deque表面上看起来是连续空间，其实它内部是将一段一段连续空间通过中控器的操作接合起来，一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或尾端。deque的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，使人们使用起来感觉像是在操作一段连续空间。它还提供了随机存取接口，避免了“重新配置、复制、释放”的轮回，代价则是复杂的迭代器结构。  
　　deque采用一块所谓的map作为主控，这里的map其实是一小块连续空间，其中每个元素都是指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是deque的存储空间主体。通过看源码，可以发现map其实是一个指针，所指之物又是一个指针，指向另一块空间。

## deque的迭代器 ##

deque的迭代器首先必须能够指出缓冲区在哪里，其次它必须能够判断自己是否已经处于所在缓冲区的边缘，如果是，一旦前进或后退时就必须跳跃至下一个或上一个缓冲区。因此，deque的迭代器应该包括四个指针：cur指向该迭代器所指缓冲区中的当前元素，first指向该迭代器所指缓冲区的头部，last指向该迭代器所指缓冲区的尾部，node指向管控中心，用来找到迭代器所指的缓冲区。

## deque的数据结构 ##

deque除了维护一个先前说过的指向map的指针外，也维护start,finish两个迭代器，分别指向第一缓冲区的第一个元素和最后缓冲区的最后一个元素的下一位置。此外，它当然也必须记住目前的map大小。因为一旦map所提供的节点不足，就必须重新配置更大的一块map。

# stack和queue #

## stack ##

stack是一种先进后出的数据结构，它只有一个出口。stack允许新增元素、移除元素、取得顶端元素。但除了最顶端外，没有任何其他方法可以存取stack的其他元素。换言之，stack不允许有遍历行为。STL中以deque作为缺省情况下的stack底部结构。  
　　stack所有元素的进出都必须符合先进后出的条件，只有stack顶端的元素，才有机会被外界取用。stack不提供走访功能，也不提供迭代器。另外，除了deque外，list也可以作为stack的底部容器。

## queue ##

queue是一种先进先出的数据结构。他有两个出口，允许新增元素、移除元素、从最底端加入元素、取得最顶端的元素。但是除了最底端加入、最顶端取出外，没有其他任何办法可以存取queue的其他元素。即queue不允许有遍历行为，queue也没有迭代器。STL默认将deque作为queue的底部容器，当然list也可以作为queue的底部容器。