1.概述

List使用一个doubly linked list（双向对列）来保存元素，相较于Vector的线性空间，List就显的复杂的多，它的好处是每次插入或删除一个元素，就配置或释放一个元素空间。对于任何位置的元素的插入或删除，List永远是常数时间。

2.list的节点

list本身和list节点是不同的结构，需要分开设计。以下是STL list的节点(node)结构：

template 
    
     struct __list_node{   typedef void* void_pointer;   void_pointer prev;   void_pointer next;   T data; }
    

3.list的迭代器

由于STL List是一个双向链表，迭代器必须具备前移、后移的能力，所以list提供的是Bidirectional Iterators

list 有一个重要的性质：插入操作（insert）和接合操作（splice）都不会造成原有list迭代器失效。这在vector是不成立的，因为vector的插入操作可能会造成空间的重新配置，导致原有迭代器的全部失效。甚至list的删除（erase）操作也只有“指向被删除元素”的那个迭代器失效，其他迭代器不收任何影响。

以下是list迭代器的设计：（只列出部分）

template
    
     struct __list_iterator{    typedef __list_iterator
     
       iterator;    typedef __list_iterator
      
        self;        typedef bidirectioanal_iterator_tag iterator_category;    typedef T value_type;    typedef Ptr pointer;    typedef Ref referrence;    typedef __list_node
       
        * link_type;    typedef size_t size_type;    typedef ptrdiff_t difference_type;        link_type node;        __list_iterator(link_type x):node(x);    __list_iterator(){}    __list_iterator(const iterator& x):node（x.node）{}        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;    } }
       
      
     
    

4.list的数据结构

SGI list 不仅是一个双向链表，而且还是一个环装双向链表。所以它只需要一个指针，便可以完整表现整个链表：

template 
    
     class list{protected:    typedef list_node
     
       node;public:    typedef list_node* link_type;protected:    link_type node;}iterator begin(){ return (link_type)((node*).next);}  //return link_type，使用iterator(link_type)构造函数返回一个iterator；iterator end(){return node;}bool empty() const {return node->next==node;}size_type size() const{    size_type result=0;   distance(begin(),end(),result);   return result; }  reference front() {return *begin()} reference back() {return *(--end())}
     
    

5.list的构造与内存管理

list缺省使用alloc作为空间配置器，并据此另外定义了一个list_node_allocator.

template 
    
     class list{protected:    typedef __list_node
     
       list_node;   typedef simple_alloc
      
        list_node_allocator; }
      
     
    

list_node_allocator(n)表示配置n个节点空间。以下四个函数分别用来配置、释放、构造、销毁一个节点：

protected:    //配置一个节点并传回    link_type get_node() {return list_node_allocator::allocate();}   //释放一个节点   void put_node(lingk_type p){ list_node_allocator::deallocate();}      //产生（配置并构造）一个节点，带有元素值   link_type create_node(const T& x){          link_type p=get_node();       construct(&p->data,x);       retrurn p;   }      //销毁（析构并释放）一个节点   void destroy_node(link_type p){           destory(&p->data);       put_data(p);    } public:    list(){ empty_initialize(); }protected:    void empty_initialize(){         node=get_node();       node_next=node;       node_prev=node;    }        void push_back(const T&) {insert(end(),x);}        iterator insert(iterator position,const T& x){        link_type tmp=create_node(x);//产生一个节点;       tmp->next=position.node;       tmp->prev=position.node->prev;       (link_type(psition.node->prev))->next=tmp;       postion.node->prev=tmp;       return tmp;    }

6.list的元素操作

void push_back(const T& x){insert(end(),x);}void psuh_pront(const T& x){insert(begin(),x);}//移除迭代器position所指节点iterator erase(iterator position){    link_type next_node=link_type(position.node->next);   link_type prev_node=link_type(position.node->prev);   prev_node->next=next_node;   next_node->prev=prev_node;   destroy_node(position.node);   return iterator(next_node);}//移除头结点void pop_front()    { erase(begin());}//移除尾节点void pop_back(){    iterator tmp=end();   erase(--tmp); } //清除所有节点（整个链表）template
    
     void list
     
      ::clear(){    link_type cur=(link_type)node->next;   while(cur!=node){       link_type tmp=cur;       cur=(link_type)cur->next;       destroy(tmp);   }   node->next=node;   node->prev=node;}//将数值为value的所有元素移除template 
      
       void list
       
        ::remove(const T& value){    iterator first=begin();   iterator last=end();   while(first!=last){           iterator next = first;       ++next;       if(*first==next) erase(first);       first=next;   } }//移除数值相同的连续元素template 
        
         void list
         
          ::unique(){ iterator first=begin(); iterator last=end(); if(first == last) return; iterator next=first; while(++next != last){ if(*first == *next) erase(next); else first=next; next=first; } }