STL札记2（序列容器vector、list、deque）

序列式容器

容器，置物之所也。

按“数据在容器中排列的特性”，可以将基本的额数据结构类型划分为序列式与关联式。本文就序列式容器进行杂谈。

一、vector

我接触STL，就是从vector开始的，一开始写project只是拿来主义，当时只是知道它可以自动生长空间，（好像知道就这可以了^-^）。但是读完相关书籍后，对vector又有了新的认识，至少对它的构造以及管理更加清晰。

• 采用半开区间[  )

当然，对于STL的所有容器都是这样。这样方便编程。（深深的体会到细节的美丽，与平时我们所用的“哨兵”异曲同工）

• vector维护的是绝对的连续线性内存空间

两个相邻迭代器之间的距离是一个常数。（如同线性空间内指针一样）。

基于vector的适配器heap有些实现细节也得益于其绝对的连续线性内存空间。

• vector数据结构

template <class T, class Alloc = alloc>//使用标准的空间配置

class vector{

/*other*/

……

protected:

    iterator start;           //vector空间头

    iterator finish;          //目前正在使用的空间尾

    iterator end_of_storage;  //可用的空间尾

}

假设有vector<int> myVec,已经存储了数据2,4,5。下面看看数据结构内部是什么样的。

看完上图，我相信你已经对vector内部的数据结构有了很深的理解，还有size与capacity是两个不同的概念，判断一个vector是否为空只能用size的原因也就不言而喻。

• vector构造与内存管理

• 配置两倍的请求内存量

• 进行空间生长时，若原剩余空间量足够容纳再次请求大小，就一次性将数据压入，否则，进行两倍原大小的空间配置，如果此时在生长方向没有连续的可用内存，则会引起空间重新配置。进行移动数据，释放原空间等一系列操作，注意，此时指向原vector的迭代器全部失效，因为此时的空间已经搬新家了。

• 释放元素时，回收内存，当然不返回给OS，留给自己用。直至生命周期结束。

• vector常用操作以及注意事项

push_back：在finish后压入一个元素

pop_back：拿掉尾端元素

erase：清除指定元素

clear：清空vector空间所有元素，此时size()=0,而capacity()!=0

二、list

n  list相对于vector就显得节俭多了，对空间的运用绝对的精确，可谓一点也不浪费啊。

n  list每配置一个元素或删除一个元素，就会进行空间配置或释放（还给OS了）

n  list数据结构

list被设计为双链表结构(故list提供了双向迭代器，具备前移、后移的能力)。节点结构如下：

template<class T>

struct __list_node{

    typedef void* void_pointer;

    void_pointer prev;   /*双链表的前后指针*/

    void_pointer next;

T data;              //数据

};

• list构造与内存管理

再次强调：是绝对的精确，绝对的配置与释放元素所占用的空间。

• list常用操作以及注意事项

操作与双链表的操作类似。

push_front,pop_front:头插与头删除

push_back,pop_back:尾插与尾删除

unique:移除数值相同的连续元素。举个列子：假设现在list中的元素为2,3,4,5,5,5,6,7,7,8,9。经过unique操作后，list元素为：2,3,4,5,6,7,8,9

merge:归并排序

splice:接合操作，可以是同一个list内部，也可以是不同list之间。

sort:排序（注意此处使用的不是STL的sort（）算法）

clear:清空整个list

三、deque

n  deque是一种双向开口的连续线性空间（注意是：伪连续，而是分段线性）

n  对于deque，要理解它的中控器，有如下示意图：

中间的每一个迭代器（除去头和尾）都通过first和last将每一段线性空间给串起来，像串珠子一样，而中控器相当于管理者，他掌握者每一个“珠子”的位置以及使用情况。

了解了STL的序列容器，那么对后面的适配器stack、queue、heap、priority_queue都会很轻松的掌握。

                    少年，黑暗中继续前行！！