所谓序列式容器，指容器中的数据都是可序的，即元素集合呈线性关系排列，但未必是有序的（符合某比较关系）。
C++语言本身提供了一个序列式容器array,但是它不可以动态扩展。
STL另外提供了vector,list,deque,stack,queue,priority-queue等序列式容器。
stack,queue，缺省由deque改装而成，被归为配接器。
vector，可以理解为动态数组。它的数组安排和操作方式与array非常相似。array是静态空间，而vector是动态空间，随元素的加入，内部会自行扩充空间。
对于array，如果空间不够用了，一些复杂的工作，得我们自己来安排。首先，申请一块新空间，然后将数据一一搬过去，最后把原空间释放。
而对于vector，这些工作它自动就完成了，完成的工作也是这样的。
template<class T, class Alloc = alloc>
class vector
{
public:
.......
.......
///一些类型定义,具体请参阅STL源码
protected:
iterator start; //目前使用空间的头部位置
iterator finish; //目前使用空间的尾部位置
iterator end_of_storage; //目前可用空间的尾部位置
public:
iterator begin();
iterator end();
size_type size();
size_type capacity();
bool empty() const;
reference operator[](size_type n);
vector();
vector(size_type n ,const T&value);
vector(int n,const T&value);
vector(long n,const T&value);
explicit vector(size_type n); //explicit 构造函数不能在隐式转换中使用
~vector();
reference front();
reference back();
void push_back(const T&x);
void pop_back();
iterator erase(iterator pos);
void resize(size_type newsize,const T& x);
void resize(size_type newsize);
void clear();
};template<class T, class Alloc = alloc>
class vector
{
public:
typedef T value_type;
typedef value_type* iterator; //即 T*,一个普通的指针
...
..
};
template<class T, class Alloc = alloc>
class vector
{
protected:
iterator start; //目前使用空间的头部位置
iterator finish; //目前使用空间的尾部位置
iterator end_of_storage; //目前可用空间的尾部位置
};
iterator begin(){return start;}
iterator end(){return finash;}
size_type size()const
{
return size_type(end()-begin());
}
size_type capacity()const
{
return end_of_storage-begin();
}相对于vector的连续线性空间，list就显得复杂太多，它的好处是每次插入或者删除就会配置或者释放一个元素空间。
它对于空间的运用绝对精准，一点也不多余。而且对于指定位置元素的插入或移除，list都是常数时间。
对于链表，list本身，和list节点时不同的结构，需要分开设计。
这是list的节点结构,很显然，它是一个双向链表
template<class T>
struct _list_node
{
typedef void* void_pointer;
void_pointer prev; //也可以设为 _list_node<T>*
void_pointer next;
T data;
};由于list是双向链表，迭代器应为 BidirectionIterators
这样的话，必须定义一个类，重载++,--等等即可。
template <class T,class Ref,class Ptr>
struct _list_iterator
{
typedef _list_iterator<T,T&,T*> iterator;
typedef _list_iterator<T,Ref,Ptr> self;
typedef _list_node<T>* link_type;
//其他定义不列出
link_type node; //迭代器内部当然需要一个指针了，指向list节点
self& operator++()
{
node = (link_type)((*node).next);
return *this;
}
self operator ++(int)
{
self tmp = *this;
++ *this;
return tmp;
}
self& operator--()
{
node = (link_type)((*node).prev);
return *this;
}
self operator --(int)
{
self tmp = *this;
-- *this;
return tmp;
}
/////其他操作不列出
};
template <class T,class Alloc=alloc>
class list
{
protected:
typedef _list_node<T> list_node;
public:
typedef list_node* link_type;
protected:
link_type node; //list是一个环，一个指针就可表示整个链表
};
node指针指向刻意置于尾端的一个空白节点，这样整个list就符合ST对于“前闭后开”区间的要求。
此时，首尾迭代器就定义为。
iterator begin()
{
return (link_type)((*node).next);
}
iterator end()
{
return node ;
}当试图在尾端和首端插入时就是常量时间了。
list是一个双向链表，而slist则是一个单向链表。主要差别在于，前者的迭代器是双向的Bidirectional Iterator,后者则是Forward Iterator。
为此，slist的功能受到了一些限制，不过，单向链表所耗用的空间更小，某些操作更快。
根据STL习惯，插入操作会将新元素放在指定位置之前。而作为一个单向链表，slist没有任何方便的办法可以回到前一个位置，因此，必须从头开始找起。这显得很耗时。
为此slist特别提供了insert_after()和erase_after()供灵活使用。
template <class T>
struct _slist_node_base
{
_slist_node_base* next;
};
template <class T>
struct _slist_node:public _slist_node_base
{
T data;
};注意到，此时，只有一个next指针。
struct _slist_iterator_base
{
typedef forward_iterator_tag iterator_categort; //单向的
_slist_iterator_base *node;
void incr(){node = node->next};
...
...
};
template <class T, class Ref,class Ptr>
struct _slist_iterator : public _slist_iterator_base
{
...
...
typedef _slist_iterator<T,Ref,Ptr> self;
self& operator ++()
{
incr();
return *this;
}
self& operator ++(int)
{
self tmp = *this;
incr();
return tmp;
}
//没有实现operatpr --
//
};
template <class T,class Alloc = alloc>
class slist
{
private:
typedef _slist_node<T,T&,T*> iterator;
typedef _slist_node<T> slist_node;
typedef _slist_node_base slist_node_base;
...
list_node_base head; //这里是一个实物，不是指针。 没有数据域
iterator begin(){return iterator((slist_node*)head.next);}
iterator end(){return iterator(0);}
....
}
相较于vector是单向开口的连续线性空间，deque则是一个双向开口的线性空间。
虽然模型图如此，但实际上，STL deque的结构远比这复杂。
它是动态地以分段连续空间组合而成。随时可以增加一段新的空间并连接起来。
虽然deque也提供Random Access Iterator，但是，它的迭代器并不是普通指针，这都是由于deque特殊的结构造成的。
这影响了deque各个函数的性能。例如deque的排序操作，为了最高效率， 可将deque西安完成复制到一个vector身上，将vector排序后，再复制回来。
deque是由一段一段的定量连续空间构成。一旦有必要在deque的前端或尾端增加新空间，便要配置一段定量的连续空间，串接在整个deuqe的头部或者尾部。
deque的最大任务，便是在这些分段的定量连续空间上， 维护其整体连续的假象，并提供随机存取的接口。
为此，deque采用一段所谓的map（不是STL中的map）作为主控。这里所谓的map是一小块连续的空间，每个元素都是一个指针，指向另一段连续空间，称为缓冲区。
缓冲区才是存放数据的地方。
template <class T,class Alloc = alloc,size_t BufSize=0>
class deque
{
public:
typedef T value_type;
typedef T* pointer;
protected:
typedef pointer* map_pointer;
map_pointer map; //指向map,其内部每个元素都是一个指针。
size_type map_size; //mao 可容纳的指针
};
deque是分段连续空间。维持其“整体连续”假象的任务，就交由迭代器来实现。具体就在于operator++和operator--两个子运算上。
template <class T,clas Ref,class Ptr,size_t BufSize=0>
struct _deque_iterator
{
typedef _deque_iterator<T,T&,T*,BufSize> iterator;
...
typedef random_access_iterator_tag iterator_category;
...
T* cur; //此迭代器所指的缓冲区的当前元素
T* first;//此迭代器所指的缓冲区的头部元素
T* last; //此迭代器所指的缓冲区的尾部元素
map_pointer node ;//指向中控器
};
实现代码为：
void set_node(map_pointer new_node)
{
node = new_node;
first = *new_node;
last = first+ difference_type(buffer_size());
}
self& operator ++()
{
cur ++ ;
if(cur == last) //如果满了，就切换到下一缓冲区
{
set_node(node+1);
cur = first;
}
return *this;
}
self& operator--()
{
if(cur == first) //已经是缓冲区的头部
{
set_node(node-1);
cur = last;
}
--cur;
return *this;
}
self& operator +=(difference_type n) //随机存储
{
difference_type offset = n+ (cur-first);
if(offset >=0 && offset < difference_type(buffer_size()))
{
//目标位置在同一缓冲区
cur += n; //直接调用普通指针的随机存取
}
else
{
difference_type node_offset = offset > 0? offset / difference_type(buffer_size())
: - difference_type((-offset -1)/buffer_size()) -1;
set_node(node + node_offset); //切换到正确的缓冲区
cur = first + (offset - node_offset*difference_type(buffer_size());
}
}
stack,queue，虽然不符合标准容器的配置，但也是一种非常常用的“容器”。
stack是一种先进先出的数据结构(FIFO)。它只有一个出口。
只允许从顶端插入，移除元素。不支持遍历行为。
template <class T,class Sequence=deque<T>>
class stack
{
//__STL_NULL_TMPL_ARGS展开会变成<> 为了实现 bound friend templates
//也就是说，class template的某个具体实现与其friend function template的某个具体实现有一对一的关系
friend bool operator == __STL_NULL_TMPL_ARGS(const stack&,const stack&);
friend bool operator < __STL_NULL_TMPL_ARGS(const stack&,const stack&);
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c; //底层容器
public:
bool empty(){return c.empty()};
size_type size()const{return c.size();}
reference top(){return c.back();}
void push(const value_type&x){c.push_back(x);}
void pop(){c.pop_back();}
};
bool operator == __STL_NULL_TMPL_ARGS(const stack<T,Sequence>&,const stack<T,Sequence>&)
{
return x.c == y.c;
}
bool operator < __STL_NULL_TMPL_ARGS(const stack<T,Sequence>&,const stack<T,Sequence>&)
{
return x.c < y .c;
}
某些时候，也是可以实用list作为底层容器。
stack<int ,list<int>> istack
queue是一种先进先出的数据结构。它有两个开口。
queue运行在尾部增加元素，在首部取出元素。
和stack一样，不支持随机访问，也不能遍历。
template <class T,class Sequence=deque<T>>
class queue
{
//__STL_NULL_TMPL_ARGS展开会变成<> 为了实现 bound friend templates
//也就是说，class template的某个具体实现与其friend function template的某个具体实现有一对一的关系
friend bool operator == __STL_NULL_TMPL_ARGS(const queue&,const queue&);
friend bool operator < __STL_NULL_TMPL_ARGS(const queue&,const queue&);
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c; //底层容器
public:
bool empty(){return c.empty()};
size_type size()const{return c.size();}
reference front(){return c.front();}
reference back(){return c.back();}
void push(const value_type&x){c.push_back(x);}
void pop(){c.pop_front();}
};
bool operator == __STL_NULL_TMPL_ARGS(const queue<T,Sequence>&,const queue<T,Sequence>&)
{
return x.c == y.c;
}
bool operator < __STL_NULL_TMPL_ARGS(const queue<T,Sequence>&,const queue<T,Sequence>&)
{
return x.c < y .c;
}
某些时候，也是可以实用list作为底层容器。
queue<int ,list<int>> iqueue
STL采用了一种非常聪明的方式来构造heap——完全二叉树。
完全二叉树整棵树内都没有任何节点漏洞，这带来了极大的好处。可以使用vector来存储节点。假如使用一个小技巧，将vector的0号元素保留，那么当树中某个节点位于i处时，其左子节点为2*i,右孩子为2*i+1,父节点为i/2.
通过这么简单的位置规则，vector可是轻易实现完全二叉树。
这种以vector/array来表示tree 的方法，称为隐式表述法。
这样，一个vector，再加上一组heap算法来插入、删除元素，取极值等，就完成了一个heap。
template <class T,class Sequence=vector<T>
class Compare = less<typename Sequence::value_type>>
class priority_queue
{
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c; //底层容器
Compare comp; //元素大小比较规则
public:
template <class InputIterator>
priority_queue(InputIterator first,InputIterator last,const Compare& x)
:c(first,last),comp(x)
{
make_heap(c.begin(),c.end(),comp);
}
template <class InputIterator>
priority_queue(InputIterator first,InputIterator last):c(first,last)
{
make_heap(c.begin(),c.end(),comp);
}
void push(const value_type& x)
{
__STL_TRY
{
c.push_back(x); //先将元素推入末端，再重排heap
push_heap(c.begin(),c.end(),comp);
}
__STL_UNWIND(c.clear());
}
void pop()
{
__STL_TRY
{
//重排heap,再使用pop_back取的弹出的元素
push_heap(c.begin(),c.end(),comp);
c.pop_back();
}
__STL_UNWIND(c.clear());
}
};原文：http://blog.csdn.net/xutengaaa/article/details/23020791