stl源码剖析-序列式容器 之 list

较久以前学过数据结构，对链表的定义和行为结构有过了解，所以阅读源码学习stl定义的list容器的并不算吃力。

list与vector都是两个常用的容器，与vector不同，list不是连续线性空间的，list是一个双向链表。每次插入或者删除一个元素，将配置或者释放一个元素空间，因此，list对于空间的运用有着绝对的精准，不会造成浪费现象。而且对于任何位置的元素插入或者删除，其操作时间永远是常数时间。（缺点是不能进行随机的访问）

list节点

list链表本身和list节点是分开设计的，以下是list节点的结构

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

可以看出list节点是一个双向链表，next指向下一个节点，prev指向前一个节点

list的迭代器

学过数据结构就知道，链表的一个特点是其分配空间不必固定在一段连续的存储空间中，所以list不能像vector一样以普通指针作为迭代器，因为其节点不能保证在存储空间中连续存在。list迭代器必须有能力指向其list节点，并有能力进行正确的递增、递减、取值、成员存取等操作。

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

在vector中，对其进行插入操作有可能会使其满载并且溢出，这样vector便需要重新配置空间，这样原有的迭代器会全部失效。而list在进行插入和接合操作都不会造成原有的list迭代器失效，即便是其删除操作，也只有“指向被删除元素”的迭代器失效，其他迭代器不受影响。

template<class T,class Ref，class Ptr>
  struct _list_iterator{
      typedef _list_iterator<T,T&,T*> iterator;
      typedef _list_iterator<T,T&,T*> iterator;
  ?
      typedef bidirectional_iterator_tag iterator_category;
      typedef T value_type;
      typedef Ptr pointer;
      typedef Ref reference;
      typedef _list_node<T>* 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){}
      
      bool operator==(const self& x) const {return node==x.node;}
      bool operator!=(const self& x) const {return node!=x.node;}

      reference operator*() const {return (*node).data;}

      reference operator->() const {return &(operator*());}
      

      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;
      }
  }

list的数据结构

SGI list不仅是一个双向链表，而且是一个环状的双向链表。

template<class T,class Alloc = alloc> //缺省使用alloc为配置器
  class list{  
  protected :  
      typedef __list_node<T> list_node ;  
  public  :  
      typedef list_node* link_type ;  
  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 = 0;
    distance(begin(), end(), result);//SGI里面的distance函数作用就是遍历链表，十分影响性能
    return result;
}

reference front() { return *begin(); }
reference back() { return *(--end()); }

list的构造与内存管理

list的构造方式有很多，这里列出缺省情况下的构造函数

/ 默认allocator为alloc
template <class T, class Alloc = alloc>
class list
{
...
public:
    list() { empty_initialize(); }
protected: 
    // 专属空间配置器，配置单位为一个节点大小
    typedef simple_alloc<list_node, Alloc> list_node_allocator;

    // 建立空链表
    void empty_initialize()
    {
        node = get_node();
        node->next = node;
        node->prev = node;
    }

    // 配置一个节点，不进行构造
    link_type get_node() { return list_node_allocator::allocate(); }

    // 释放一个节点, 不进行析构
    void put_node(link_type p) { list_node_allocator::deallocate(p); }

    // 配置并构造一个节点
    link_type create_node(const T& x)
    {
        link_type p = get_node();
        construct(&p->data, x);
        return p;
    }

    // 析构并释放节点
    void destroy_node(link_type p)
    {
        destroy(&p->data);
        put_node(p);
    }
...
}

insetr()是一个重载函数，同样有很多种形式，其中最简单如下，首先配置并构造一个节点，然后在尾端进行适当指针操作插入新节点（push_back()和push_front插入新元素时都会调用insert()）

iterator insert(iterator position, const T& x)
{
    link_type tmp = create_node(x);   // 产生一个节点
    // 调整双向指针，使tmp插入
    tmp->next = position.node;
    tmp->prev = position.node->prev;
    (link_type(position.node->prev))->next = tmp;
    position.node->prev = tmp;
    return tmp;
}

list的元素操作

list的元素操作很多，无论是简单的插入删除清除还是迁移，大部分都不难，下面只列出部分常用的操作，有兴趣可以详细阅读《stl源码剖析》第四章关于list的内容，或者直接下载源码来研究

void push_front(const T&x){  
  insert(begin(),x);  
  }

 iterator erase(iterator position){  
      link_type next_node=link_type(position.node->next);  
      link_type prev_node=link_type(position.node->prev_nodext);  
      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 i=end();  
      erase(--i);  
  } 


//将某连续范围的元素迁移到某个特定位置之前。技术上讲很简单，节点直接的指针移动而已。
void transfer(iterator position, iterator first, iterator last) {  
      if (position != last) {  
        (*(link_type((*last.node).prev))).next = position.node; 
        (*(link_type((*first.node).prev))).next = last.node;      
        (*(link_type((*position.node).prev))).next = first.node;  
        link_type tmp = link_type((*position.node).prev);       
        (*position.node).prev = (*last.node).prev;               
        (*last.node).prev = (*first.node).prev;                  
        (*first.node).prev = tmp;                               
      }  
    }