第四章 序列式容器（sequence containers）

1.容器的概观与分类2.vector

3.list

4.deque 5.stack

6.queue 7.heap(隐私表述,implicit representation)

8.priority_queue

9.slist

研究数据的特定排列方式，以利于搜寻或排序或其它特殊目的，称为数据结构(DataStructures)。任何特定的数据 结构都是为了实现某种特定的算法。STL容器即是将运用最广的一些数据结构实现出来（如下图所示)。未来，在每五年召开一次的C++标准委员会的会议中，STL容器 的数董还有可能增加。常用的数据结构不外乎array(数组）、list(链表）、tree(树）、stack (堆栈）、queue(队列）、hashtable (散列表）、set(集合）、map(映射表）…等等。根据“数据在容器中的排列＇特性，这些数据结构分为序列式(sequence)和关联式(associative)两种。本章探讨序列式容器，下一章探讨关联式容器。容器是大多数人对STL的第一印象，这说明了容器的好用与受欢迎。容器也是许多人对STL的唯一印象，这说明了还有多少人利器(STL)在手而未能善用。

上图表示的SGI STL的各种容器（本图以内缩方式来表达基层与衍生层的关系。这里所谓的衍生， 并非派生(inheritance)关系，而是内含(containment)关 系。例如heap内含一个vector, priority-queue内含一个heap、stack和queue都含 一个deque , set/map/multiset/multimap都内含 一 个RB-tree , hast_x都内含 一个 hash tabl。

1.1 序列式容器(sequential containers)

所谓序列式容器，其中的元素都可序(ordered), 但未必有序(sorted)。C++语言本身提供了一个序列式容器array,STL另外再提供vector,list, deque, stack,queue,priority-queue等等序列式容器。其中stack和queue由于只是将deque改头换面而成，技术上被归类为一种配接器(adapter),。

2.1 vector概述

vector的数据安排以及操作方式，与array非常相似。两者的唯一差别在于空间的运用的灵活性。

array是静态空间，一旦配置了就不能改变：要换个大（或小）一点的房子，可以，一切琐细得由客户端自己来：首先配置一块新空间，然后将元素从旧址一一搬往新址，再把原来的空间释还给系统。vector是动态空间，随着 元素的加入，它的内部机制会自行扩充空间以容纳新元素。因此，vector的运用对 于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必因为害怕空间不足而 一开始就要求一个大块头array了，我们可以安心使用vector。vector的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率。一旦vector旧有空间满载，如果客户端每新增一个元素，vector内部只是扩 充一个元素的空间，实为不智，因为所谓扩充空间（不论多大），一如稍早所说，是＂配置新空间／数据移动／释还旧空间”的大工程，时间成本很高，应该加人某种未雨绸缪的考虑。

2.2 vector定义摘要

下面是vector定义的源代码。虽然STL规定，欲使用vector者必须
先包括,但SGI STL将vector实现于更底层的,

template
class vector{
public:
    typedef T  value_type;
    typedef value_type* pointer;//vector的迭代器是普通指针
    typedef value_type*  iterator;
    typedef value_type&  reference;
    typedef size_t   size_type;
    typedef ptrdiff_t  difference_type;
    
    
protected:
    //以下，simple_alloc是SGI STL的空间配置器
    typedef simple_allocdata_allocator;
    
    iterator start; //表示目前使用空间的头
    iterator finish; //表示目前使用空间的尾
    iterator end_of_storage; //表示目前可用空间的尾

void insert_aux(iterator position, const T& x);

void deallocate() { 
    
    if(start)
        data_allocator::deallocate(start,end_of_storage-start);
}
void fill_initialize(size_type n, const T& value) {
    start = allocate_and_fill(n,value);
    finish = start+n;
    end_of_storage = finish;
}

public:
iterator begin() {return start; } 
iterator end() { return finish; } 
size_type size() const { return size_type(end() - begin()); } 

size_type capacity()const{
return size_type(end_of_storage - begin());} 

bool empty() const { return begin() == end();} 
reference operator[] (size_type n) { return *(begin() + n);} 
vector() : start(O), finish(O), end_of_storage (0) {} 
vector(size_typen, const T& value) {fill_initialize(n, value);}
vector(int n,const T& value) { fill_initialize(n, value); }
vector(long n,const T& value){fill_initialize(n,value);}
explicit vector(size_typen, n){fill_initialize(n,T());}


~vector(){
    destroy(start,finish);//全局函数
    deallocate();//vector 的一个member function
}
reference front(){return *begin();}//第一个元素
reference back(){return *(end()-1);}//最后一个元素
void push_back(const T& x){
    if(finish ！=end_of_storage){    
    construct(finish,x);//全局函数
    ++finish;
    }
    else
        insert_aux(end(),x);//vector的一个member function
} 

void pop_back(){
    --finish();
    destroy(finish);//全局函数
}

iterator erase(iterator position){//清除某位置上的元素
  if(position+ 1 != end()){
      copy(position+1, finish, position);//后续元素往前移动
      --finish;
      destroy(finish);
      return position;
  }
  
void resize(size_type new_size,const T& x){
      if(new_size 
2.3 vector的迭代器
 
vector维护的是一个连续线性空间，所以不论其元素型别为何，普通指针都可以作为vector的迭代器而满足所有必要条件，因为vector迭代器所需要的操作行为，如operator*,operator->,operator++,operator–,operator+,operator-, operator+=,operator-=, 普通指针天生就具备。vector支持随机存取，而普通指 针正有着这样的能力。所以，vector提供的是RandomAccess Iterators。
 
template 
class vector{
public:
typedef T  value_type;
typedef value_type* iterator;//vector的迭代器是普通指针
...
};
 
根据上述定义，如果客户端写出这样的代码:
 
vector::iterator ivite;//ivite的型别其实就是int*
vector::iterator svite;//svite的型别其实就是Shape*。
 
2.4 vector的数据结构
 
vector所采用的数据结构非常简单：线性连续空间。它以两个迭代器start和finish分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器 end_of_storage指向整块连续空间（含备用空间）的尾端：
 
template 
class vector{
..
protected:
iterator start;//表示目前使用空间的头
iterator finish;//表示目前使用空间的尾
iterator end_of_storag;//表示目前可用空间的尾
...
}
 
为了降低空间配置时的速度成本，vector实际配置的大小可能比客户端需求量更大一些，以备将来可能的扩充。这便是容量(capacity)的观念。
 2.换句话说， 一个vector的容量永远大于或等于其大小。一旦容量等于大小，便是满载，下次再有新增元素，整个vector就得另觅居所，如下图所下：
 
 
运用start，finish,end_of_storage三个迭代器，便可轻易地提供首尾 标示、大小、容量、空容器判断、注标（［］）运算子、最前端元素值、最后端元 素值…等机能：
 
template 
class vector{
public:
iterator begin() {return start; } 
iterator end () { return finish; } 
size_type size() const { return size_type(end() - begin()); } 
size_type capacity()const{
return size_type(end_of_storage - begin());} 

bool empty () const { return begin () == end () ; } 
reference operator[] (size_type n) { return *(begin() + n);
...
};
 
2.5 vector的构造与内存管理：constructor, push_back
 
千头万绪该如何说起？以客户端程序代码为引导，观察其所得结果并实证源代 码，是一个良好的学习路径。下面是一个小小的测试程序，我的观察重点在构造的 方式、元素的添加，以及大小、容量的变化：
 
#include
#include
#include
using namespace std;

int main()
{
    int i;
    vector iv(2,9);
    cout<<"size="< 
注意，所谓动态增加大小，并不是在原空间之后接续新空间（因为无法保证原 空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大空间，然 后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此， 对vector的任何操作， 一且引起空间重新配置，指向原vector的所有迭代器就都失效了。 这是程序员易犯的一个错误， 务需小心。
 
2.6 vector的元素操作： pop_back, erase, clear, insert
 
vector所提供的元素操作很多， 无法在有限篇幅中 一一讲解 :其实也没有这种必要。 为搭配先前对空间配置的讨论，挑选数个相关函数作为解说对象。这些函数也出现在先前的测试程序中。
 
void pop_back()
{
    --finish;//尾部标记往前移一格，表示将放弃尾端元素
    destroy(finish);//全局函数
}

//清除[first,last]中所有元素
iterator erase(iterator first,iterator last){
    iterator i = copy(last,finish,first);//全局函数
    destroy(i,finish);
    finish=finish-(last-first);
    return first;
}

//清除某个位置上元素
iterator erase(iterator position){
    if(position+1 !=end())
        copy(position + 1,finish,position);//全局函数
    --finish();
    destroy(finish);//全局函数
    return position;
}

void clear(){erase(begin(),end());}
 
局部区间的清除操作：
 
 
//从 position开始， 插入n个元素， 元素初值为x 
template  
void vector::insert(iterator position,size_Type n,const T& x)
{
    if(n !=0){//当 n !=0 才进行以下所有操作
        if(size_type(end_of_storage-finish)>=0){
             //备用空间大于等于"新增元素个数"
            T x_copy = x;
            //以下计算插入点之后的现有元素个数
            const size_type elems_after = finish - position;
            iterator old_finish = finish;
            if(elems_after>0){
                //“插入点之后的现有元素个数”大于“新增元素个数"            
                uninitialized_copy(finish-n,finish,finish);
                finish+=n;//将vector尾部标记后移
                copy_backward(position,old_finish-n,old_finish);
                fill(position,position+n,x_copy);//从插入点开始天然新值
            }
            else{
                //“插入点之后的现有元素个数”小于等于“新增元素个数”
                uninitialized_fill_n(finish,n-elems_after,x_copy);
                finish +=n-elems_after;
                uninitialized_copy(position,old_finish,finish);
                finish +=elems_after;
                fill(position,old_finish,x_copy);
            }
        }
        else{
            //备用空间小于 “新增元素个数” （那就必须配置额外的内存）
            //首先决定新长度： 旧长度的两倍， 或旧长度＋新增元素个数
            const size_type old_size = size();
            const size_type len = old_size + max(old_size,n);
            //以下配置新的vector空间
            iterator new_start = data_allocator::allocate(len);
            iterator new_finish = new_start;
            __STL_TRY{
                //以下首先将旧vector的插入点之前的元素复制到新空间
                new_finish = uninitialized_copy(start,position,new_start);
               //以下再将新增元素(初值皆为n)填入新空间
                new_finish = uninitialized_copy(new_finish,n,x);
                //以下再将旧vector的插入点之后的元素复制到新空间
                new_finish = uninitialized_copy(position, finish, new_finish);
            }
            
# idef __STL_USE_EXCEPTIONS
            catch(...){
                destroy(new_start,new_finish);
                data_allocator::deallocate(new_start,len);
                throw;
            }
            
#endif
            //以下清除并释放旧的vector
            destroy(start,finish);
            deallocate();
            //以下调整水位
            start = new_start;
            finish = new_finish;
            end_of_storage = new_start + len;
        }
    }
}
 
在插入完成后，新节点将位于哨兵迭代器（上面之position，标示出插入点）所指之节点前方-这是STL对于“插入操作”的标准规范，如下图展示insert（position,n,x）的操作：
 

 
 
 
3.list 
3.1 list概述
 
相较于vector的连续线性空间，list就显得复杂许多，它的好处是每次插入或删除一个元素，就配置或释放一个元素空间。list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素移除，list永远是常数时间。list和vector是两个最常被使用的容器。什么时机下最适合使用哪一种容 器，必须视元素的多寡、元素的构造复杂度（有无non-trivialcopy constructor, non-trivial copy assignmen operator)、元素存取行为的特性而定。
 
3.2 list的节点(node)
 
每一个设计过list的人都知道，list本身和list的节点是不同的结构，需要分开设计。以下是STLlist的节点(node)结构：
 
template
struct  __lsit_node{
typedef void* void_pointer;
void_pointer prev;//型别为void* ,其实可设为__list_node*
void_pointer next;
T data;
}
 
显然这是双链表。
 
 3.3 list的迭代器
 
 
list不再能够像vector一样以普通指针作为迭代器，因为其节点不保证在储存空间存在。
  
list迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取等操作。
  
所谓“list迭代器正确的递增、递减、取值、成员取用”操作是指，递增时指向下一个节点，递减时指向上一个节点，取值时取得的是节点的数据值，成员取用时取用的是节点得的成员。
 list的结点与list的迭代器：
 
 
 
由于STL list是一个双向链表(doublelinked-list) , 迭代器必须具备前移、 后移的能力，所以list提供的是Bidirectional Iterators。
 
lsit有个重要性质：插入操作（insert）和接合操作（splice）都不会造成原有的list迭代器失效。这在vector是不成立的，因为vector定位插入操作可能造成记忆体 重新配置，导致原有的迭代器全部失效。甚至list的元素删除操作，也只有“指向被删除元素”的哪个迭代器失效，其它迭代器不受如何影响。
 
下面是lsit迭代器的设计：
 
template 
struct __list_iterator{
    typedef __list_iterator iterator;
    typedef __list_iterator self;
    
    typedef bidirectional_iterator_tag iterator_category;
    typedef T value_type;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef __list_node* link_type;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    
link_type node;//迭代器内部当然要有一个普通指针，指向list的节点

//constructor
__list_iterator(link_type x):nodc(x.node){}
__list_iterator(){}
__list_iterator(const iterator& x):nodc(x.node){}

bool operator==(const self& x)const{return node == x.node;}
bool operator!=(const self& x)const{return node !=x.node;}

//以下对迭代器取值(dereferene),取的是节点的数据值
reference operator*()const{return (*node).data;}

//以下是迭代器的成员存取(member access)运算的标准做法
pointer operator->()const {return &(operator *());}

//对迭代器加1，就是前进一个节点
self& operator++(){
    node = (link_type)((*node).next);
    return *this;
}

self operator++(int){
    self tmp = *this;
    ++*this;
    return tmp;
}

//对迭代器递减1，就是后退一个节点
self& operator--(){
    node = (link_type)((*node).prev);
    return *this;
}

self operator--(int){
    self tmp = *this;
    --*this;
    return tmp;
}
 
3.4 list的数据结构
 
SGI list不仅是一个双向链表，而且还是一个环状双向链表。所以它只需要 一个指针，便可以完整表现整个链表：
 
template //缺省使用alloc为配置器

class list{
protected:
typedef list_node* link_type;
public:
typedef __list_node list_node;
protected:
link_type node;//只要一个指针，便可表示整个环状双向链表
...
}
 
如果让指针node指向刻意置于尾端的一个空白节点，node便能符合STL 对千“前闭后开“区间的要求，成为last迭代器，如下图所示。这么一来， 以下几个函数便都可以轻易完成：
 
iterator begin() { return (link_type) ((*node) .next); }
 iterator end() { return node; } 
 bool empty() const { return node->next == node; 
 size_type size() const { 
size_type result = O; 
distance(begin(), end(), result); //全局函数
return result;
}
//取头节点的内容（元素值）
reference front() { return *begin () ; } 
//取尾部节点的内容（元素值）
reference back() { return *(--end()); }
 
list示意图。是环状链表只需一个标记，即可完全表示整个链表。只要刻意在环状链表的尾端加上一个空白节点，便符合STL规范之"前闭后开“区间。
 
 
3.5 list的构造与内存管理：constructor,push_back,insert
 
以客户端程序代码为引导，观察其所得结果并实证源代码，是个良好的学习路径。下面是一个测试程序，我的观察重点在构造的方式以及大小的变化：
 
#include
#include
#include
using namespace std;

int main()
{
    int i;
    list ilist;
    cout<<"size="< 
由于此时最后一个缓冲区仍有4个备用元素空间，所以不会引起缓冲区的再配置，此时的deque状态如下图所示：
 延续上图的状态，将每个元素重新设值，并在尾部新增3个元素：
 
 下面是push_back()函数内容：
 
public:			//push_* and pop_*
void  push_back(const value_type& t){
if(finish.cur !=finish.last - 1){
//最后缓冲区尚有一个以上的备用空间
construct(finish.cur,t);//直接在备用空间上构造元素
++finish.cur;
}
else //最后缓冲区已无（或只剩一个）元素备用空间
push_back_aux(t);
}
 
现在，如果再新增一个新元素于尾端：
 
ideq.push_back(3);
 
由于尾端只剩一个元素备用空间，于是push_back()调用push_back_aux(), 先配置一整块新的缓冲区，再设妥新元素内容，然后更改迭代器finish的状态：
 
//只有当finish.cur==finish.last-1时才会被调用
//也就是说，只有当最后一个缓冲区只剩个备用元素空间时才会被调用
template  
void deque::push_back_aux(const value_type& t){
value_type t_copy = t; 
reserve_map_at_back();//若符合某种条件则必须重换一个map
*(finish.node +1) = allocate_node();//配置一个新节点（缓冲区）
__STL_TRY{
construct(finish.cur,t_copy);//针对标的元素设值
finish.set_node(finish.node+1);//改变finish，令其指向新节点
finish.cur = finish.first;//设定finish的状态
}
__STL_UNWIND(deallocate_node(*(finish.node+1)));
}

 
现在，deque的状态如图所示：
 

 延续上图的状态，在尾端再加一个元素，于是引发新缓冲区的配置，同时也导致迭代器finish的状态改变，map大小为8（初始值），目前用了4个节点。
 
下面在deque的前端插入一个新元素：
 ideq.push_front(99);
 push_front()函数操作如下：
 
public:			//push_* and pop_*
void push_front(const,value_type& t){
if(start.cur !=start.first){
if(start.cur!= start.first){//第一个缓冲区尚有备用空间
construct(strart.cur -1,t);//直接在备用空间上构造元素
--start.cur;//调整第一级缓冲区的使用状态
}
else//第一缓冲区已无备用空间
push_front_aux(t);
}
 
由于目前状态下，第一缓冲区并无备用空间，所以调用push_front_aux():
 
//只有当start.cur== start.first时才会被调用
//也就是说， 只有当第一个缓冲区没有任何备用元素时才会被调用
template  
void deque: :push_front_aux(const value_type& t)
{
value_type t_copy = t;
reserve_map at_front();//若符合某种条件则必须重换一个map
*(start.node-1) = alloc_node();//配置一个新节点
__STL_TRY{
start.set_node(start.node - l);//改变start,令其指向新节点
 start.cur = start.last-1;//设定start的状态
  construct(start. cur, t_copy) ; //针对的元素设值
  }
catch(...){
// "commit or rollback" 语意： 若非全部成功， 就一个不留
start.set_node(start .node + 1); 
start.cur = start.first; 
deallocate_node(* (start.node - 1)); 
throw; 
}
}
 
该函数一开始即调用reserve_map_at_front(), 后者用来判断是否需要扩
 充map, 如有需要就付诸行动。目前不需要重新整治map, 所以后继流程便配置了 块新缓冲区，并直接将节点安置千现有的map上，然后设定新元素，改变迭代器Start的状态， 如下图所示：
 延续上图的状态，在最前端加上一个元素。引发新缓冲区的配置，同时也导致迭代器start状态改变。map大小为8(初始值），目前用掉5个节点。
 
 接下来范例程序又在deque的最前端插入两个新元素：
 
ideq.push_front(98); 
ideq.push_front (97);
 
这一次，由千第一缓冲区有备用空间，push_front() 可以直接在备用空间上 构造新元素，如下图所示：
 延续上图的状态，在最前端再加两个元素。由于第一缓冲区尚有备用
 空间，因此，直接取用备用空间来构造新元素即可。
 
 上面的图是连环图解，充分展示了deque容器的空间运用策略。这时，什么时候map需要重新整治？这个问题判断由reserve_map_at_back() 和reserve_map_at_front() 进行操作则由reallocate_map()执行：
 
void reserve_map_at_back(size_type nodes_to_add=1){
if(nodes_to_add+1>map_size-(finish.node-map))
//如果map尾端的节点备用空间不足
//符合以上条件则必须重换一个map（配置更大的，拷贝原来的，释放原来的）

reallocate_map(nodes_to_add,false);
}

void reserve_map_front(size_type nodes_to_add=1){
if(nodes_to_add>start.node-map)
//如果map前端的节点备用空间不足
//符合以上条件则必须重换一个map（配置更大的，拷贝原来的，释放原来的）
reallocate_map(nodes_to_add,true);
}
template  
void deque::reallocate_map(size_type nodes_to_add,bool add_at_front){
size_type old_num_nodes = finish.node -start.node+ 1; 
size_type new_num_nodes = old_num_nodes + nodes_to_add; 
map_pointer new_nstart; 
if (map_aize > 2 * new_num_nodes) { 
new_nstart =map + (map_size - new_num_nodes) / 2 
+ (add_at_front ? nodes_to_add : 0);
 if (new_nstart < start.node) 
copy(start.node, finish.node + 1, new_nstart); 
else 
copy_backward(start.node,finish.node+1,new_nstart+old_num_nodes);
}
else{
size_type new_map_size = map_size + max(map_size,node_to_add)+2;
//配置一块空间，准备给新map使用
map_pointer new_map = map_allocator::allocate(new_map_size);
new_nstart = new_map+(new_map_size-new_num_nodes)/2 +(add_at_front ? nodes_to_add:0);
//把原map内容拷贝过来
copy(start.node,finish.node +1,new_size);
//释放原map
map_allocator::deallocate(map,map_size);
//设定新map的起始地址与大小
map = new_map;
map_size = new_map_size;
}
//重新设定迭代器start和finish
start.set_node(new_nstart);
finish.set_node(new_nstart +old_num_nodes - 1);
{
 
4.6 deque的元素操作 pop_back, pop_front, clear, erase, insert
 
deque所提供的元素操作很多，无法一一讲解，下面介绍能够member function。
 前述测试程序曾经以泛型算法find()寻找deque的某个元素：
 
deque::iterator itr;
itr = find(ideq.begin(),ideq.end(),99);
 
当find()操作完成时，迭代器itr 状态如下图所示。下面这两个操作输出相同的结果，印证我们对deque迭代器的认识。
 
cout<<*itr< 

 延续上图的状态，以find()寻找数值为99的元素。此函数将传回一个迭代器，指向第一个符合条件的元素。注意，该迭代器的四个字段都必须有正确的设定。
 前面展示过push_back()和push_front()的实现内容，现在例举对应的pop_back()和pop_front()为例。所谓pop是将元素拿掉。无论从deque的最前端或最尾端取元素，都需要考虑某种条件下将缓冲区释放掉：
 
void pop_back()
{
    if(finish.cur !=finish.first){
        //最后缓冲区有一个(或更多）元素
        --finish.cur;//调整指针，相当于排除了最后元素
        destroy(finish.cur);//将最后元素析构
    }
    else
        //最后缓冲区没有任何元素
        pop_back_aux();//这里将进行缓冲区的释放工作
}

//只有当finish.cur==finish.first时才会被调用
template 
void deque::pop_back_aux(){
    deallocate_node(finish.first);//释放最后一个缓冲区
    finish.set_node(finish.node-1);//调整finish的状态，使指向上一个缓冲区的最后一个元素
    finish.cur = finish.last-1;
    destroy(finish.cur);//将该元素析构
}

void pop_front()
{
    if(start.cur !=start.last-1){
        //第一缓冲区有一个（或更多）元素
        destroy(start.cur);//将第一元素析构
        ++start.cur;//调整指针，相当于排除了第一元素
    }
    else
        //将第一缓冲区仅有一个元素
        pop_front_aux();//这里将进行缓冲区的释放工作
}

//只有当start.cur == start.last-1时才会被调用
template 
void deque::pop_front_aux(){
    destroy(start.cur);//将第一缓冲区的第一个元素析构
    deallocate_node(start.first);//释放第一缓冲区
    start.set_node(start.node+1);//调整start的状态，使指向下一个缓冲区的第一个元素
    start.cur = start.first;
}
 
下面这个例子是clear(),用来清除整个deque。请注意，deque的最初状态（无任何元素时）保有一个缓冲区，因此，clear()完成之后回复初始状态，也一样要保留一个缓冲区：
 
//注意，最后需要保留一个缓冲区，这是deque的策略，也是deque的初始状态
template 
void deque::clear(){
//以下针对头尾以外的每一个缓冲区（它们一定都是饱满的）
for (map_pointer node = start.node + 1; node < finish.node; ++node) {
//将缓冲区内的所有元素析构。注意，调用的是destroy()第二版本，
destroy(*node, *node+ buffer_size()); 
//释放缓冲区内存
data_allocator::deallocate(*node, buffer_size()); 
}

if(start.node !=finish.node){//至少有头尾两个缓冲区
destroy(start.cur,start.last) ;//将头缓冲区的目前所有元素析构 
destroy{finish.first,finish.cur); //将尾缓冲区的目前所有元素析构
//以下释放尾缓冲区。 注意， 头缓冲区保留
data_allocator::deallocate(finish.first, buffer_size()); 
}
else//只有一个缓冲区
destroy(start.cur,finish.cur);//将此唯一缓冲区内的所有元素析构
//注意，并不释放缓冲区空间，这唯一的缓冲区将保留
finish = start;//t调整状态
}
 
下面这个例子是erase(),用来清除某个元素：
 
//清除pos所指的元素，pos为清除点
iterator erase(iterator pos){
iterator next = pos;
++next;
difference_type index = pos - start;//清楚点之前的元素个数
if(index < (size()>>1)){//如果清除点之前的元素比较少
copy_backward(start,pos,next);//就移动清除点之前的元素
pop_front();//移动完毕，最前一个元素冗余，去除之
}
else{//清除点之后的元素比较少
copy(next,finish,pos);//就移动清除点之后的元素
pop_back();//移动完毕，最后一个元素冗余，去除之
}
return start + index;
}
 
下面例子是erase，用来清除[first,last)区间内的所有元素：
 
template 
deque::iterator 
deque::erase(iterator first, iterator last) {
if(first == start && last == finish){//如果清除区间就是整个deque
clear();
return finsh;
}
else
{
difference_typen = last-firs;//	清除区间的长度
difference_type elems_before = first-tart;//清除区间前方的元素个数
if(elems_before<(size()-n)/2){//如果前方的元素比较少
copy_backward(start,first,last);//向后移动前方元素（覆盖清除区间）
iterator new_start = start + n;//标记deque的新起点
destroy(start,new_start);//移动完毕，将冗余的元素析构

//以下将冗余的缓冲区释放
for(map_pointer cur= start.node;cur< new_start.node;++cur) 
data_allocator::deallocate(*cur, buffer_size()); 
start=new_start; //设定deque的新起点
}
else{//如果清除区间后方的元素比较少
copy(last, finish, first); //向前移动后方元素（覆盖清除区间）
iterator new_finish = finish -n;//标记deque的新尾点
destroy (new_finish, finish); //移动完毕,将冗余的元素析构

//以下将冗余的缓冲区释放
for (map_pointer cur= new_finish.node + l; cur<= finish.node; ++cur) 
data_allocator::deallocate(*cur, buffer_size()); 
finish = new_finish; //设定deque的新尾点
}
return start +elem_before;
}
}
 
本节要说明的最后一个例子是inser。deque为这个功能提供了许多版本，
 最基础最重要的是以下版本，允许在某个点（之前）插入个元素，并设定其
 值。
 
//在posi巨on处插入一个元素，其值为x
iterator insert(iterator position,const value_type& x){
if(position.cur == start.cur){//如果插入点是deque最前端 ，交给push_front去做
push_front(x);
return start;
}
else if(position.cur == finish.cur){//如果插入点是deque最尾端，交给push_back去做
push_back(x);
iterator tmp=finish;
--tmp;
return tmp;
}
else{
return insert_aux(position,x);//交给insert_aux去做
}
}

template  
typename deque::iterator 
deque::insert aux(iterator pos, const value_type& x) {
difference_type index= pos-start; //插入点之前的元素个数 
value_type x_copy = x; 
if (index < s1.ze() / 2) {//如果插入点之前的元素比较少
push_front(front());//在最前端加入与第一元素同值的元素
 iterator frontl = start; //以下标示记号，然后进行元素移动
 ++front1; 
iterator front2 = frontl; 
++front2;
pos = start+index; 
iterator pos1 = pos; 
++pos1; 
copy(front2, pos1, front1);//元素移动
}
else{//插入点之后的元素比较少
push_back(back(}); //在最尾端加入与最后元素同值的元素
iteator back1 = finish; //以下标示记号，然后进行元素移动
--back1; 
iterator back2 = back1;
--back2;
pos = start + index;
copy_backward(pos,back2,back1);//元素移动
}
*pos = x_copy();//在插入点上设定新值
return pos;
} 
 
5.stack 
5.1 stack 概述
 
stack是一种先进后出(FirstIn Last Out, FILO)的数据结构。它只有一个出口，形式如下图所示。stack允许新增元素、移除元素、取得最顶端元素。但除了最顶端外，没有任何其它方法可以存取stack的其它元素。换言之，stack 不允许有遍历行为。将元素推入stack的操作称为push,将元素推出stack的操作称为pop。
 

 5.2 stack定义完整列表
 
以某种既有容器作为底部结构，将其接口改变，使之符合“先进后出”的特性，形成一个stack，是容易的。deque是双向开口的数据结构，若以deque为底部结构并封闭其头端开口，便轻而易举地形成一个stack。因此，SGL STL便以deuqe作为缺省情况下的stack底部结构，stack的实现因而非常简单。
 
由于stack系以底部容器完成其所有工作，而具有这种“修改某物接口，形成另一种风貌”之性质者，称为adapter（配接器），因此，STL stack往往
 不被归类为container(容器）,而被归类为container adapter。
 
template  >
class stack{
//以下的_STL_NULL_TMPL_ARGS会开展为＜＞，
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:
//以下完全利用Sequence c的操作,完成stack的操作
bool empty()const{return c.empty();} 
size_type size()const { return c.size();} 
reference top(){ return c.back ();} 
const_reference top() const { return c.back();} 
//deque是两头可进出，stack是末端进,末端出（所以后进者先出）。
 void push(const value_type& x) { c.push_back(x);}
 void pop() { c.pop_back(); } 
};
template  
bool operator== (const stack& x, const stack& y) 
{
return x.c == y.c;
}
template  
bool operator< (const stack& x, const stack& y) 
{
return x.c < y.c;
}
 
5.3 stack没有迭代器
 
stack所有元素的进出都必须符合 “先进后出＂ 的条件， 只有stack顶端的 元素， 才有机会被外界取用。 stack不提供走访功能， 也不提供迭代器。
 
5.4 以list作为stack的底层容器
 
除了deque之外， list也是双向开口的数据结构。 上述stack源代码中使 用的底层容器的函数有empty, size, back, push_back, pop_back, 凡此种种， list都具备。 因此， 若以list为底部结构并封闭其头端开口， 一样能够轻易形成一个stack。 下面是做法示范。
 
#include
#include
#include
#include
using namespace std;

int main(){
stack>istack;
istack.push(1);
istack.push(3);
 istack.push(S); 
 istack.push(7);
 
cout< 
6.queue 
6.1 queue概述
 
queue是一种先进先出(First In First Out, FIFO)的数据结构。它有两个出 口，形式如下图所示。queue允许新增元素、移除元素、从最底端加入元素、 取得最顶端元素。但除了最底端可以加入、最顶端可以取出外，没有任何其它方法可以存取queue的其它元素。换言之，queue不允许有遍历行为。将元素推入queu的操作称为push,将元素推出queue的操作为pop。
 
 
6.2 queue定义完整列表
 
以某种既有容器为底部结构，将其接口改变，使其符合先进先出＂的特性， 形成一个queue,是很容易做到的。deque是双向开口的数据结构，若以deque为 底部结构并封闭其底端的出口和前端的入口，便轻而易举地形成了一个queue。因此，SGI STL便以deque作为缺省情况下的queue底部结构，queue的实现因 而非常简单。由于queue系以底部容器完成其所有工作，而具有这种“修改某物接口，形 成另一种风貌”之性质者，称为adapter(配接器），因此，STLqueue往往不被归类为container(容器），而被归类为container adapter。
 
template >
 class queue{ 
//以下的_STL_NULL_TMPL_ARGS会开展为＜＞
friend bool operator==_STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
friend bool operator< _STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
 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: 
//以下完全利用Sequencec的操作，完成queue的操作
bool empty () const{return c.empty(); } 
size_type  size() const { returnbc.size(); } 
reference front() { returnbc.front(); } 
const_reference front() const { return c.front();}
reference back() { return c.back(); } 
const_reference back() const{return c.back();} 
// deque是两头可进出，queue是末端进、前端出（所以先进者先出）
void push(const value_type& x) { c.push_back(x);} 
void pop(){ c.pop_front(); } 
};
template 
bool operator== (const queue& x, cons t queue& y) 
{
return x.c == y.c;
}
template  
bool operator< (const queue& x, const queue& y)
{
return x.c 
6.3 queue没有迭代器
 
queue所有元素的进出都必须符合 “先进先出 ＂ 的条件， 只有queue顶端的 元素， 才有机会被外界取用。 queue不提供遍历功能， 也不提供迭代器。
 
6.4 以list作为 queue的底层容器
 
除了deque之外，list也是双向开口的数据结构。上述queue源代码中使用 的底层容器的函数有empty, size, back, push_back, pop_back, 凡此种种， list都具备。 因此，若以list为底部结构并封闭其头端开口， 一样能够轻易形成一个queue。 下面是做法示范。
 
#include  
#include  
#include  
using namespace std;
int main(}
{
queue >iqueue;
iqueue.push(1);
iqueue.push(3); 
iqueue.push(5); 
iqueue.push(7);

cout<< iqueue.size()<< endl;//4 
cout << iqueue. front()<< endl;//1

iqueue.pop(); cout << iqueue.front() << endl;//3
 iqueue.pop(); cout << iqueue.front()<< endl;//5 
 iqueue.pop(); cout << iqueue.front() << endl; //7
 cout << iqueue.size() << endl; // 1
 }
 
7.heap(隐私表述,implicit representation) 
7.1 heap概述
 
heap并不归属于STL容器组件，扮演priority queue 的助手。priority queue允许用户以任何次序将任何元素推入容器内，但取出时一定是从优先权最高（也就是数值最高）的元素开始取。binary max heap正是具有这样的特性，适合作为priority queue的底层机制。前面使用的list作为priority queue的底层机制，元素插入操作可享常数时间。但是要找到list中的极值，却需要对整个list 进行线性扫描。也可以改变做法，让元素插入前先经过排序这一关，使得list 的元素值总是由小到大（或由大到小），但这么一来，收之东隅却失之桑榆：虽然取得极值以及元素删除操作达到最高效率，可元素的插入却只有线性表现。其它的做法是以binary search tree (如后面的RB-tree)作为priority queue的底层机制。这么一来，元素的插入和极值的取得就有O(logN)的表现。但小题大做，一来binary search tree的输人需要足够的随机性， 二来binaryvsearch tree并不容易实现。priority queue的复杂度，最好介于 queue和binar ysearch tree之间，才算适得其所。binary heap便是这种条件的选择。所谓binar yheap就是一种complete binary tree (完全二叉树） 也就是说， 整棵binary tree除了最底层的叶节点(s)之外，是填满的，而最底层的叶节点(s)由左至右又不得有空隙。下图所示的是一个complete binary tree。
 
一个完全二叉数及其array表达式：
 
 
complete binary tree整棵树内没有任何节点漏洞，这带来一个极大的好处：我们可以利用array来储存所有节点。假设动用一个小技巧3,将array的#0元素保留（或设为无限大值或无限小值），那么当complete binary tree中的某个节点位于array的li处时，其左子节点必位于array的2i处，其右子节点必位于array的 2i+1处，其父节点必位于"i/2"处（此处的"!’'权且代表高斯符号，取其整数）。通过这么简单的位置规则，array可以轻易实现出complete binary tree。这种以 array表述tree的方式，我们称为隐式表述法(implicit representation)。
 
这么一来，我们需要的工具很简单了：一个array和一组heap算法（用来插入元素、删除元素、取极值，将某一个整组数据排列成一个heap）。array的缺点是无法动态改变大小，而heap却需要这项功能，因此，以vector代替array是更好的选择。
 
根据元素排列方式，heap可分为max-heap和而min-heap两种。前者每个节点的键值(key)都大于或等于其子节点键值，后者的每个节点键值(key)都小于或等千其子节点键值。max-heap的最大值在根节点，并总是位于底层array 或vector的起头处；min-heap的最小值在根节点，亦总是位于底层array或 vector的起头处。STL供应的是max-heap,因此，以下我说heap时指的是max-heap。
 
7.2 heap算法
 
①.push_heap算法
 
下图所示的是push_heap算法的实际操演情况。为了满足complete binary
 tree的条件，新加入的元素一定要放在最下一层作为叶节点，并填补在由左至右的第一个空格，也就是把新元素插入在底层vector的end()处。
 

 新元素是否适合于其现有位置呢？为满足max-heap的条件（每个节点的键值都大于或等于其子节点键值)，我们执行一个所谓的percolate up（上溯）程序：将新节点拿来与其父节点比较，如果其键值（key）比父节点大，就父子对换位置。如果一直上溯，直到不需要对换或根节点为止。
 
下面便是push_heap算法的实现细节。 该函数接受两个迭代器， 用来表现一 个heap底部容器(vector)的头尾， 并且新元素已经插入到底部容器的最尾端。 如果不符合这两个条件，push_heap的执行结果未可预期。
 
template 
inline void push_heap(RandomAccessiterator first,RandomAccessiterator last){
//注意， 此函数被调用时， 新元素应己置于底部容器的最尾端 
_push_heap_aux(first, last, distance_type(first),
value_type(first));
}

template  inline void __push_heap_aux(RandomAccessiterator first, RandomAccessiterator last, Distance*, T*) {
 __push_heap(first, Distance((last - first)- 1), Distance(O), 
T(*(last-1))); 
//以上系根据implicit representation heap的结构特性:新值必置于底部 
//容器的最尾端， 此即第一个洞号:(last-first)-1 
}
//以下这组push_back()不允许指定 ”大小比较标准
template  void __push_heap(RandomAccessiterator first, Distance holeindex,Distance topIndex,Tbvalue){
Distance parent = (holeindex - 1)/2;//找出父节点
while (holeindex >topindex && *(first + parent) < value) { 
//当尚未到达顶端， 且父节点小于新值（于是不符合heap的次序特性）
//由于以上使用operator<,可知STL heap是一种max-heap(大者为父）
*(first+holeIndex) = *(first + parent);//令洞值为父值
holeIndex = parent;// percolate up:调整洞号，向上提升至父节点
parent = (holeIndex-1)/2;//新洞的父节点
}//持续至顶端，或满足heap的次序特性为止
*(first + holeindex) = value; //令洞值为新值， 完成插入操作
}
 
②.pop_heap算法
 
下图所示的是pop_heap算法的实际操演情况。既然身为max-heap,最大
 值必然在根节点。pop操作取走根节点（其实是移至底部容器vector的最后一个元素）之后，为了满足complete binary tree的条件，必须将最下一层最右边的叶节点拿掉，现在我们的任务是为这个被拿掉的节点找个适当的位置。为满足max-heap的条件（每个节点的键值都大于或等于其子节点键值），我们执行一个所谓的percolate down (下溯）程序：将根节点（最大值被取走后，形成一个“洞”）填入上述哪个失去生存空间的叶子节点值。再将它拿来和其两个子节点比较键值（key）,并与较大节点对调位置。如此一直下放，直到这个“洞”的键值大于左右两个子节点或直到下放至叶子节点为止。
 
 
下面便是pop_heap算法的实现细节。该函数接受两个迭代器，用来表现一 个heap底部容器(vector)的头尾。如果不符合这个条件，pop_heap的执行结 果未可预期。
 
template 
inline void pop_heap(RandomAccessIterator first,RandomAccessIterator last) { 
_pop_heap_aux(first, last, value_type(first)); 
}
tempalte
inline void __pop_heap(RandomAccessiterator first, RandomAccessiterator last,RandomAccessiterator result,T value,Distance*){
*result = *first;//设定尾值为首值，于是尾值即为欲求结果，可由客户端稍后再以底层容器之pop_back()取出尾值
_adjust_heap(first, Distance(O), Distance(last -first),value};
//以上欲重新调整heap,洞号为0(亦即树根处），欲调整值为value(原尾值）
}

//以下这个__adjust_heap()不允许指定"大小比较标准”
template 
void __djust_heap(RandomAccessiterator first, Distance holeindex,Distance len,T value){
Distance topindex = holeindex; 
Distance secondChild = 2 * holeindex + 2; //洞节点之右子节点
while (secondChild < len) { 
//比较洞节点之左右两个子值，然后以secondChild代表较大子节点
if (*(first+ secondChild) <*(first+ (secondChild -1))) 
secondChild--; 
// Percolate down: 令较大子值为洞值，再令洞号下移至较大子节点处 *
(first+ holeindex) =*(first+ secondChild); 
holeindex = secondChild; 
//找出新洞节点的右子节点
secondChild = 2*(secondChild+1);
}
if(secondChild == len){//没有右子节点，只有左子节点
//Percolate down:令左子值为洞值，再令洞号下移至左子节点处。
*(first + holeIndex) = *(first +(seconedChild -1));
holeIndex = secondeChild - 1;
}
//将欲调整值填入目前的洞号内。注意，此时肯定满足次序特性
//依侯捷之见，下面直接改为*(first+holeindex) = value; 应该可以
__push_heap(first,holeIndex,topIndex,value);
}

 
注意，pop_heap之后，最大元素只是被置放于底部容器的最尾端，尚未被取走。如果要取其值，可使用底部容器(vector)所提供的back()操作函数。如果 要移除它，可使用底部容器(vector)所提供的pop_back()操作函数。
 
③. sort_heap 算法
 
既然每次pop_heap可获得heap中键值最大的元素，如果持续对整个heap
 做pop_heap操作，每次将操作范围从后向前缩减个元素（因为pop_heap会把键值最大的元素放在底部容器的最尾端），当整个程序执行完毕时，我们便有一个递增序列。下图所示的是sort_heap的实际操演情况。
 
下面是sort_heap算法的实现细节。该函数接受两个迭代器，用来表现个
 heap底部容器(vector)的头尾。如果不符合这个条件，sort_heap的执行结果
 未可预期，注意，排序过后，原来的heap就不再是一个合法的heap了。
 
//以下这个sort_heap()不允许指定“大小比较标准” 
template
void sort_heap(RandomAccessIterator first, RandomAccessIterator last){
//以下，每执行一次pop_heap() , 极值（在STLheap中为极大值）即被放在尾端。
 //扣除尾端再执行一次pop—heap(),次极值又被放在新尾端。一直下去，最后即得 //排序结果
 while(last-first>1)
 pop_heap(first,last--);//每执行pop_heap()一次，操作范围即退缩一格
 }
 
 
sort_heap算法：不断对heap进行pop操作，便可达到排序效果
 
 

 ④. make_heap算法
 
这个算法用来将一段现有的数据转化为一个heap。 其主要依据就是前面提 到的complete binary tree的隐式表述(implicit representation) 。
 
//将[first,last)排列为一个heap
template  
inline void make_heap(RandomAccessiterator first,RandomAccessiterator last){
__make_heap(first, last, value_type(first), distance_type(first));
}
//以下这组make_heap ()不允许指定 ”大小比较标准”
template  void _make_heap(RandomAccessIterator first, RandomAccessIterator  last,T*,Distance*){
if (last-first< 2) return;//如果长度为0或1, 不必重新排列
Distance len = last - first;
//找出第一个需要重排的子树头部， 以parent标示出。 由于任何叶节点都不需执行 
// perlocate down, 所以有以下计算. parent命名不佳， 名为holeIndex更好
Distance parent = (len - 2)/2; 
while (true) { 
//重排parent为首的子树，len是为了让__adjust_heap()判断操作范围
__adjust_heap(first,parent,len,T(*(first+parent)));
if(parent == 0)return;//走完根节点，就结束
parent--;//（即将重排之子树的）头部向前一个节点
}
}
 
7.3 heap没有迭代器
 heap的所有元素都必须遵循特别的（complete binary tree）排列规则，所以heap不提供遍历功能，也不提供迭代器。
 
7.4 heap测试实例
 
#include
#include
#include
using namespace std;

int main()
{
    {
        //test heap(底层以vector完成）
        int ia[9] = {0,1,2,3,4,8,9,3,5};
        vectorivec(ia,ia+9);
        
        make_heap(ivec.begin(),ivec.end());
        for(int i=0;i 
8.priority_queue 
8.1 priority_queue概述
 
 
priority_queue 是一个拥有权值观念的 queue, 它允许加入新元素、 移除旧元素、 审视元素值等功能。 由于这是一个 queue, 所以只允许在底端加入元素， 并从顶端取出元素，除此之外别无其它存取元素的途径。
  
priority_queue带有权值观念，其内的元素并非依照被推入的次序排列，而是自动依照元素的权值排列（通常权值以实值表示）。 权值最高者， 排在最前面。
  
缺省情况下 priority_queue 系利用 一个 max-heap 完成， 后者是一个以 vector 表现的 complete binary tree。 max-heap 可以满足 priority_queue 所需要的 ＂依权值高低自动递增排序” 的特性。
 
 
 
8.2 priority_queue定义完整列表
 
由于 priority_queue 完全以底部容器为根据再加上 heap 处理规则， 所
 以其实现非常简单。缺省情况下是以 vector 为底部容器。queue 以底部容器完成其所有工作。 具有这种 “修改某物接口， 形成另一种风貌” 之性质者，称为 adapter (配接器）。因此， STL priori ty_queue 往往不被归类为 container (容器）， 而被归类为 container adapter。
 
template ,class Compare = less >
class priority_quene{
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_typee size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c;//底层容器
Compare comp;//元素大小比较标准
public:
priority_queue():c() {} 
explicit priority_queue(const Compare& x) : c(),comp(x) {}

//以下用到的make_heap () , push_heap () , pop_heap ()都是泛型算法
//注意， 任一个构造函数都立刻于底层容器内产生一 个implicit representation heap
template  
priority_queue(Input Iterator first, Inputiterator last, const Compare& x) 
: c(first, last), comp(x) { make_heap(c.begin(), c.end(), comp); } 
template 
priority_queue(Inputiterator first, Inputlterator last):c(first,last){make_heap(c.begin(),c.end(),comp);}

bool empty()const{return c.empty();]
size_type size()const{return c.size();}
const_reference top() const{return c.front();}
void push(const value_type& x){
__STL_TRY{
// push_heap是泛型算法， 先利用底层容器的push_back ()将新元素
//推入末端， 再重排heap。  
c.push_back(x);
push_heap(c.begin(), c.end(), comp); // push_heap是泛型算法
}
__STL_UNWID(c.clear());
}
void pop(){
__STL_TRY{
// pop_heap是泛型算法，从heap内取出一个元素。它并不是真正将元素 
//弹出，而是重排heap,然后再以底层容器的pop_back()取得被弹出
//的元素。
pop_heap(c.begin(), c.end(), comp); 
c.pop_back();
}
__STL_UNWIND(c.clear());
}
};
 
8.3 priority_queue没有迭代器
 
priority_queue的所有元素，进出都有一定的规则，只有queue顶端的元素（权值最高者），才有机会被外界取用。priority_queue不提供遍历功能，也不提供迭代器。
 
8.4 priority_queue测试实例
 
#incude
#include
#include
using namespace std;
int main(){
{
//test priority queue...
int ia[9] = {0,1,2,3,4,8,9,3,5};
priority_queueipq(ia,ia+9);
cout<<"size="< 
9.slist 
9.1 slist概述
 
STL list是个双向链表(double linked list)。SGI STL另提供了一个单向链表(single linked list) , 名为slist。 这个容器并不在标准规格之内， 不过多做些剖析， 多看多学些实现技巧也不错。slist和list的主要差别在于，前者的迭代器属于单向的Forward Iterator,
 后者的迭代器属于双向的Bidirectional Iterator。 为此，slist的功能自然也就受到许多限制。不过，单向链表所耗用的空间更小，某些操作更快，不失为另一种选择。list和list共同具有的个相同特色是， 它们的插入(insert)、 移除 (erase)、 接合(splice)等操作并不会造成原有的迭代器失效（当然啦， 指向被 移除元素的那个迭代器， 在移除操作发生之后肯定是会失效的）。根据STL的习惯，插入操作会将新元素插入于指定位置之前，而非之后。然而作为个单向链表，slist没有任何方便的办法可以回头定出前个置，因此它必须从头找起。换句话说，除了slist起点处附近的区域之外，在其它位置 上采用insert或erase操作函数，都属不智之举。这便 是slist相较于list之下的大缺点。为此， slist特别提供了insert_after()和erase_after ()供灵活运用． 基于同样的（效率）考虑，slist不提供push_back()，只提供push_front()。因此slist的元素次序会和元素插入进来的次序相反。
 
9.2 slist的节点
 
slist节点和其迭代器的设计，架构上比lsit复杂许多，运用继承关系，因此在型别转换上有复杂的表现。这种设计方式在第5章RB-tree将再一次出现。下图概述了slist节点和其迭代器的设计结构：
 
 
//单向链表的节点基本结构
struct  __slist_node_base
{
	__slist_node_base* next;
};
//单向链表的节点结构
tenpalte
struct __slist_node:public __slist_node_base
{
T date;
};
//全局函数:已知某一节点，插入新节点于其后
inline __slist_node_base* __slist_make_link(
	__slist_node_base* prev_node;
	__slist_node_base* new_node;
	{
	//令new节点的下一个点为prev节点的下一节点
	new_node->next = prev_node->next; 
	prev_node->next = new_node; //令prev节点的下一节点指向new节点
	return new_node; 
	}
	//全局函数：单向链表的大小（元素个数）
	inline size_t __slist_size(__slist_node_base* node){
	size_t result = 0;
	for(;node !=0;node = node->next)
	++result;//一个一个累计
	return result;
	}
 
9.3 slist的迭代器
 
slisst迭代器如下图：
 
 
//单向链表的迭代器结构：
 
struct __slist_iterator_base
{
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef forward_iterator_tag iterator_category;//注意，单向

__slist_node_base* node;//指向节点基本结构

__slist_iterator_base(__slist_node_base* x):node(x){}
void incr(){node = node->next;}//前进一个节点

bool operator==(const __slist_iterator_base& x)const{
return node==x.node;
}
bool operator !=(const __slist_iterator_base& x)const{
return node !=x.node;
}
};
//单向链表的迭代器结构
template
struct __slist_iterator:public __slist_iterator_base
{
	typedef T value_type;
	typedef Ptr pointer;
	typedef Ref reference;
	typedef __slist_nodelist_node;

__slist iterator(list_node* x):slist_iterator_base(x) {}
//调用slist::end()时会造成_slist_iterator(O), 于是调用上述函数
__list_iterator() : _slist_iterator_base(O) {} 
__list_iterator(const iterator x):__slist_iterator_base(0){}
reference operator*() const return ((list_node*) node)->data; } pointer operator->() const { return &(operator*()); } 
self& operator++() 
{
incr();//前进一个节点
return *this;
}
self operator++(int)
{
incr();//前进一个节点
return tmp;
}
//没有实现operator--,因为这是一个forward iteator
};
 
注意，比较两个slist迭代器是否等同时（例如我们常在循环中比较某个迭
 代器是否等同于slist.end()),由__slist_iterator并未对operator==
 施重载，所以会调用__slist_iterator_base::operator==。根据其中之定义，
 我们知道，两个slist迭代器是否等同，视其_slist_node_base*node是否
 等同而定。
 
9.4 slist的数据结构
 
template 
class slist
{ 
public: 
typedef T value_type; 
typedef value_type* pointer;
typedef const value_type*const__pointer; 
typedef value_type& reference; 
typedef const value_type& const_reference; 
typedef size_t size_type; 
typedef ptrdiff_tdifference_type;
typedef _slist_iterator iterator; 
typedef _slist_iterator const_iterator;
private:
typedef _slist_nodelist_node;
typedef_slist_node_base list_node_base;
typedef_slist_iterator_base iterator_base;
typedef simple_alloc list_node_allocator;
static list_node* create_node(constvalue_type&x) { 
list_node* node = list_node_allocator::llocate();//配置空间
__STL_TRY{
construct(&node->data,x);//构造元素
node->next = 0;
}
_STL_UNWIND(list_node_allocator::deallocate(node)); 
return node;
}
static void
private:
list_node_base head;//头部。注意，它本身指针，是实物

public:
silst(){head.next = 0;}
~slist(){clear();}
public:
iterator begin() { return iterator((list_node*)head.next); }
iterator end() { return iterator(O); } 
size type size() const { return _slist_size(head.next);}
 bool empty() const { return head.next == O; } 
//两个slist互换： 只要将head交换互指即可
void swap(slist& L) 
{
list_node_base* tmp = head.next;
head.next = L.head.next;
L.head.next = tmp;
}
public:
//取头部元素
reference front() { return ((list_node*) head.next}->data; } 
//从头部插人元素（新元素成为slist的第一个元素）
void push_front (const value_type& x) { 
__slist_make_link(&head,create_node(x));
}
//注意，没有push_back()

//从头部取走元素（删除之）。修改head
void pop_front(){
list_node* node = (list_node*) head.next;
 head.next = node->next; 
destroy_node (node) ;
}
...
};
 
9.5 slist的元素操作
 
#include
#include
#include
using namespace std;
int main()
{
    int i;
    slist islist;
    cout<<"size="<