STL

所谓序列式容器,其中的元素都可序,但未必有序,C++语言本身提供了一个序列式容器arry,STL再提供vector,list,deque,stack,queue,priority_queue等等序列式容器,其中stack和queue只是将deque改头换面,技术上被归类为一种配接器.
一 vector
vector的数据安排以及操作方式与arry十分相似,唯一的差别在于arry是静态的,一旦配置了就不能改变,vector是动态空间.
stl的erase和insert 的实现效率低得可怜,每erase一个元素,竟然要把后面所有的节点全部移动,O(n^2)的复杂度.
vector有个resize函数,原型是void resize( size_type new_size, const T&x ),这个函数为vector预留new_size个元素的空间,少则删除,多则在已有的容器后面插入值为x的元素,但这些元素并不算入这个容器的size.
vector的迭代器支持–,++,+,-,-=,+=,更支持随机访问(STL中支持随机访问的序列式容器只有vector和deque).
size_type capacity() const,这个函数返回在不申请新空间的前提下,当前可使用的空间.
为了降低空间配置时的速度成本,vector实际配置的大小可能会比客户端需求量更大一些,以备将来可能的扩充,即一个vector的容量永远大于等于其大小,一旦容量等于其大小,便是满载,下次再有新增的元素,整个vector得另觅居所,当增加新元素时,如果超过当时的容量,则容量会扩充至两倍,如果两倍容量仍不足,就扩张至足够大的容量,
当我们以push_back()将新元素插入vector尾端时,该函数首先检查是否还有备用空间,如果有就直接在备用空间上构造元素,并调整迭代器finish,使vector变大.如果没有备用空间了,就扩充空间(重新配置,移动数据,释放原空间)

vector支持的操作

iterator begin(),iterator end(),size_type size(),size_type capacity(),

bool empty(),reference operator[],vector(),vector( size_type n,const T& value )

vector(long n,const T& value),explicit vector( size_type n ),~vector(),reference front(),

reference back(), void push_back( const T& x ),void pop_back(),

iterator erase( iterator position ),void resize( size_type new_size,const T& x );

void resize( size_type new_size ),void clear();

二 list

相较于vector的连续线性空间,list就显得复杂许多,它的好处是每次插入或删除一个元素,就配置或释放一个元素空间,因此,list对于空间的运用有绝对的精准,一点也不浪费,而且对于任何位置的元素插入或元素移除,list永远是常数时间.

list的一个重要性质,插入操作和结合操作都不会造成list的迭代器失效,这在vector是不成立的,因为vector的插入操作,因为vector的插入操作可能会造成记忆体重新配置,导致原油的迭代器全部失效,甚至list的删除操作,也只有”指向被删除元素”的那个迭代器失效,其他迭代器不受任何影响.

list不仅是一个双向链表,而且是一个环状链表,他多加了一个空节点,所以我们只要一个指针便可遍历list,但是同时会遍历到这个空节点.

list支持的操作:

push_front,push_back,erase,pop_front,pop_back,clear,remove,unique,splice,merge,reverse,

sort

其中merge是将两个有序的链表合并,sort是list自己的sort,因为它不能随机访问,所以必须自己写,

三 deque

deque是最复杂的,deque是一种双向开口的连续线性空间,所谓双向开口,意思是可以在头尾两端分别做元素的插入和删除操作,当然vector也可以在头尾两端进行操作,但是效率奇差.

deque和vector的最大差异,一在于允许常数时间内对起头端进行元素的插入或移除操作,二在于deque没有所谓的容量,因为它是动态地以分段连续空间组合而成,随时可以增加一段新的空间并链接起来,换句话说,像vector那样因旧空间不足而重新配置一块更大的空间,然后复制元素,再释放空间,这样的事情在deque上面是不可能发生的.,因此deque也没必要提供所谓的空间保留功能.

对deque的排序操作,为了最高效率,可以将deque先完整地复制到一个vector,将vector排序后,再复制回deque.

deque采用一块所谓的map作为主控,这里所谓map是一段小块连续空间,其中每个元素都是指针,指向另外一段连续性空间,称为缓冲区,缓冲区才是deque的存储空间主体

deque支持的操作begin(),end(),operator[],front(),back(),size(),max_size(),empty(),push_back,push_front, pop_back,pop_front,clear,erase,insert.

deque与vector的共同点,都支持随机存取操作,也支持插入删除操作,但是vector的随机操作很快,而deque要经过一个map的映射.deque的首尾删除效率很高,众所周知vector的删除是要移动后面所有的元素的.但是deque中间删除元素也并不快,因为deque中间删除也要移动前面或者后面的元素,如果中间删除操作很多就要用list.

四stack

stack是一种container adapter而不是container,因为它是利用别的容器实现的,它的底层默认是deque,当然也可以是list,vector…其他容器,它不支持迭代器,不允许遍历

它支持的操作:

empty,sizeo,top,push,pop

如果这样定义stack<int,list<int> > T, 这样则是以list作为T底层容器.

五queue

不支持迭代器,不允许遍历行为,支持的操作,empty,size,front,back,push,pop它也默认以deque为底层容器,可以只用其他容器.

六heap

heap的底层容器是一个vector,它的内部实现就是一个堆,http://www.cnblogs.com/Lvsi/archive/2011/06/11/2078164.html,他支持make_heap,push_heap,pop_heap,sort_heap操作,但是push_heap容器中必须只有最后一个为排序,其他都是已经在堆中的,否则会出错.

七 priority_queue

priority_queue默认是用一个max-heap完成,他支持empty,size,top,push,pop操作,但是从heap内取出一个元素,它并不是真正地将元素弹出,而是重排heap,然后再以底层的pop_back取得弹出的元素

它不提供迭代器,不能被遍历.

八slist

slist是单向链表,他不能将元素插在某个元素之前,所以他只提供insert_after,erase_after,slist不提供push_back,他只提供push_front,他还提供swap(速度很快,O(1)),front,pop_front