STL序列容器vector,deque,list

vector 表示一段连续的内存块每个元素被顺序存储在这段内存中,是一个在堆上建立的一维数组，因为在堆上，所以对其进行erase( ), resieze()等操作；还有一点就是，vector不用担心越界当空间不够用的时候，系统会自动按照一定的比例（对capacity( )大小）进行扩充。 vector最大的优点莫过于是检索（用operator[ ]）速度在这三个容器中是最快的，还有就是在vector序列末尾添加(push_back( ))或者删除(pop_back( ))对象效率高，但是在任意位置而不是在vector末尾插人元素则效率很低 ，因为它需要把待插入元素右边的每个元素都拷贝一遍。类似地删除任意一个而不是vector 的最后一个元素效率同样很低。因为在删除元素右边的每个元素都必须被复制一遍这种代价对于大型的复杂的类对象来说尤其大。其它的操作的效率都谈不上很NB，原因就在于当内存不够用的时候要执行重新分配内存，拷贝对象到新存储区，销毁old对象，释放内存等操 作，如果对象很多的话，这种操作代价是相当高的。为了减少这种代价，使用vector最理想的情况就是事先知道所要装入的对象数目，用成员函式 reserve( )预定下来；

 

        deque（double-ended-queue），是由多段连续内存块构成，同时存在一个映射表对这些内存块进行管理【貌似在OS课程上讲过】。同理该容器也有索引操作operator[ ]，效率没vector高。但是，双端队列几乎不存在上述的操作，自然在同等条件下效率好多了。另外，deque比vector多了push_front( ) & pop_front( )操作，灵活性更大。

        list的本质是一个双向链表，说到链表，它的高效率首先表现是插入，删除元素，进行排序等等需要移动大量元素的操作。显然链表没有检索操作operator[ ], 也就是说不能对链表进行随机访问，而只能从头至尾地遍历，这是它的一个缺陷。list有不同于前两者的某些成员方法，如合并list的方法splice( ), 排序sort( ),交换list 的方法swap( )等等。

 

下面是选择顺序容器类型的一些准则 :

如果我们需要随机访问一个容器则vector要比list好得多 。

如果我们已知要存储元素的个数则vector 又是一个比list好的选择。  

如果我们需要的不只是在容器两端插入和删除元素则list显然要比vector好  

除非我们需要在容器首部插入和删除元素否则vector要比deque好