STL list ——part 1

list结构

STL list是一个环形双向链表 ，结点结构如下：

template<class T>
struct __list_node
{
typedef void* void_pointer;
void_pointer prev;//其实可以设为__list_node<T>*
void_pointer next;
T data;
};

迭代器

list是一个双向链表,其迭代器可以向前移、向后移,因此迭代器类型为bidirectional_iterator_tag

// 没有继承 std::iterator
template<class T, class Ref, class Ptr>  
struct __list_iterator {   
  typedef __list_iterator<T, T&, T*>             iterator;  
  typedef __list_iterator<T, const T&, const T*> const_iterator;  
  typedef __list_iterator<T, Ref, Ptr>           self;  
  
  //为了支持STL型别标准，自己定义5个类别  
  typedef bidirectional_iterator_tag iterator_category; 
  typedef T value_type;           
  typedef Ptr pointer;          
  typedef Ref reference;             
  typedef ptrdiff_t difference_type;

  typedef __list_node<T>* link_type;  
  typedef size_t size_type;   
  
  link_type node;  // 指向list的结点指针 
  
  //构造函数  
  __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; }      
  
#ifndef __SGI_STL_NO_ARROW_OPERATOR    
  pointer operator->() const { return &(operator*()); }  
#endif /* __SGI_STL_NO_ARROW_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 定义

template <class T, class Alloc = alloc> // 默认为 alloc 为配置器  
class list {  
protected:  
  typedef void* void_pointer;  
  typedef __list_node<T> list_node;    
  typedef simple_alloc<list_node, Alloc> list_node_allocator;  
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 list_node* link_type;  
  typedef size_t size_type;  
  typedef ptrdiff_t difference_type;  
  
public:   
  typedef __list_iterator<T, T&, T*>             iterator;  
  typedef __list_iterator<T, const T&, const T*> const_iterator;  
  
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION  
  typedef reverse_iterator<const_iterator> const_reverse_iterator;  
  typedef reverse_iterator<iterator> reverse_iterator;  
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */  
  typedef reverse_bidirectional_iterator<const_iterator, value_type,  
  const_reference, difference_type>  
  const_reverse_iterator;  
  typedef reverse_bidirectional_iterator<iterator, value_type, reference,  
  difference_type>  
  reverse_iterator;   
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */  
  
protected:  
  //申请、释放结点 
  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();  
    __STL_TRY {  
      construct(&p->data, x);    
    }  
    __STL_UNWIND(put_node(p));  
    return p;  
  }   
  void destroy_node(link_type p) {  
    destroy(&p->data);       
    put_node(p);  
  }  
  
protected:  
    //初始化一个空链表，首尾相连  
  void empty_initialize() {   
    node = get_node();    
    node->next = node;     
    node->prev = node;  
  }  
  //初始化长为n的链表，值都为value  
  void fill_initialize(size_type n, const T& value) {  
    empty_initialize();  
    __STL_TRY {  
      insert(begin(), n, value);      //先初始化一个空链表在插入n个结点
    }  
    __STL_UNWIND(clear(); put_node(node));  
  }  
  
#ifdef __STL_MEMBER_TEMPLATES  
  //以迭代器区间初始化一个链表  
  template <class InputIterator>  
  void range_initialize(InputIterator first, InputIterator last) {  
    empty_initialize();  
    __STL_TRY {  
      insert(begin(), first, last);  //
    }  
    //commit or rollback  
    __STL_UNWIND(clear(); put_node(node));  
  }  
#else  /* __STL_MEMBER_TEMPLATES */  
  void range_initialize(const T* first, const T* last) {  
    empty_initialize();  
    __STL_TRY {  
      insert(begin(), first, last);  
    }  
    __STL_UNWIND(clear(); put_node(node));  
  }  
  void range_initialize(const_iterator first, const_iterator last) {  
    empty_initialize();  
    __STL_TRY {  
      insert(begin(), first, last);  
    }  
    __STL_UNWIND(clear(); put_node(node));  
  }  
#endif /* __STL_MEMBER_TEMPLATES */  
  
protected:   
  link_type node; //头结点  
  
public:  
  ...
};

list元素操作

构造函数

list() { empty_initialize(); // 默认构造函数，空链表。

//构造长为n的链表
list(size_type n, const T& value) { fill_initialize(n, value); } 

list(int n, const T& value) { fill_initialize(n, value); }  

list(long n, const T& value) { fill_initialize(n, value); } 

explicit list(size_type n) { fill_initialize(n, T()); }

//迭代器区间构造list   
template <class InputIterator>  
list(InputIterator first, InputIterator last){range_initialize(first, last);}

//拷贝构造list
list(const list<T, Alloc>& x){range_initialize(x.begin(), x.end());}  

push、pop、erase、insert、clear、remove、unique

  void push_front(const T& x) 
  { 
  	insert(begin(), x); 
  }  
  void push_back(const T& x)
  { 
   	insert(end(), x); 
  }  
  void pop_front()
  { 
  	erase(begin()); 
  }  
  void pop_back()
  {   
    iterator tmp = end();  
    erase(--tmp);  
  }  
  iterator insert(iterator position, const T& x) //在postition所指位置之前插入一个结点
  {  
    link_type tmp = create_node(x); // 申请一个结点并用x初始化   
    tmp->next = position.node;  
    tmp->prev = position.node->prev;  
    //prev和next指针都是void*，所以需要指针类型转换  
    (link_type(position.node->prev))->next = tmp;  
    position.node->prev = tmp;  
    return tmp;  
  }   
  iterator erase(iterator position)  //移除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);  
  }   
template <class T, class Alloc>   
void list<T, Alloc>::clear()    // 清除所有结点 
{  
  link_type cur = (link_type) node->next; // begin()  
  while (cur != node) {   //遍历结点
    link_type tmp = cur;  
    cur = (link_type) cur->next;  
    destroy_node(tmp);    
  }  
  // 恢复头结点状态
  node->next = node;  
  node->prev = node;  
} 	  
template <class T, class Alloc>  
void list<T, Alloc>::remove(const T& value) // 将数值为value的结点移除
{  
  iterator first = begin();  
  iterator last = end();  
  while (first != last) {    
    iterator next = first;  
    ++next;  
    if (*first == value) erase(first);  // 移除  
    first = next;  
  }  
}  
template <class T, class Alloc>  
void list<T, Alloc>::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;    //调整范围
  }  
 }

size_type size() const 
{  
    size_type result = 0;  
    distance(begin(), end(), result);  // 在<stl_iterator.h>定义，result是引用传递  
    return result;  
  }