STL 源码剖析读书笔记三：序列式容器之 vector、list

1. STL 中的容器

容器，置物之所也。STL 容器即是将运用最广的一些数据结构实现出来。如下图所示：

上图以内缩方式来表达基层和衍生层的关系。所谓衍生，并非派生关系，而是内含关系。例如 heap 内含一个 vector，priority-queue 内含一个 heap、stack、queue都内含一个 deque，set/map/multimap/multiset 都内含一个 RB-tree，hash_x 都内含一个 hashtable。

2. 序列式容器之 vector

所谓序列式容器，其中的元素都可序，但未必有序。

vector 的数据安排以及操作方式，与 array 非常相似。两者唯一的差别在于空间的运用灵活性。array 是静态空间，一旦配置了就不能改变，要换个更大（或小）的，就由客户端自己来：先配置一块新空间，然后将元素从旧址复制到新址，再把原来的空间释还给系统。vector 是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。

vector 实现的关键在于其对大小的控制以及重新配置时数据移动的效率。

2.1 vector 的定义

vector 的定义如下：

class vector {
public:
  typedef T value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type* iterator;
  typedef const value_type* const_iterator;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;

#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_iterator<const_iterator, value_type, const_reference, 
                           difference_type>  const_reverse_iterator;
  typedef reverse_iterator<iterator, value_type, reference, difference_type>
          reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
protected:
  typedef simple_alloc<value_type, Alloc> data_allocator; // SGI STL 空间配置器接口
  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; }
  const_iterator begin() const { return start; }
  iterator end() { return finish; }
  const_iterator end() const { return finish; }
  reverse_iterator rbegin() { return reverse_iterator(end()); }
  const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
  reverse_iterator rend() { return reverse_iterator(begin()); }
  const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }

  // size、max_size、capacity、empty
  size_type size() const { return size_type(end() - begin()); }
  size_type max_size() const { return size_type(-) / sizeof(T); }
  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); }
  const_reference operator[](size_type n) const { return *(begin() + n); }


  // 构造函数，大都调用 fill_initialize
  vector() : start(), finish(), end_of_storage() {}
  vector(size_type n, 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_type n) { fill_initialize(n, T()); }

  vector(const vector<T, Alloc>& x) {
    start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());
    finish = start + (x.end() - x.begin());
    end_of_storage = finish;
  }
#ifdef __STL_MEMBER_TEMPLATES
  template <class InputIterator>
  vector(InputIterator first, InputIterator last) :
    start(), finish(), end_of_storage()
  {
    range_initialize(first, last, iterator_category(first));
  }
#else /* __STL_MEMBER_TEMPLATES */
  vector(const_iterator first, const_iterator last) {
    size_type n = ;
    distance(first, last, n);
    start = allocate_and_copy(n, first, last);
    finish = start + n;
    end_of_storage = finish;
  }
#endif /* __STL_MEMBER_TEMPLATES */

  // 析构函数
  ~vector() { 
    destroy(start, finish);
    deallocate();
  }
  vector<T, Alloc>& operator=(const vector<T, Alloc>& x);
  void reserve(size_type n) {
    if (capacity() < n) {
      const size_type old_size = size();
      iterator tmp = allocate_and_copy(n, start, finish);
      destroy(start, finish);
      deallocate();
      start = tmp;
      finish = tmp + old_size;
      end_of_storage = start + n;
    }
  }

  // 首尾元素
  reference front() { return *begin(); }
  const_reference front() const { return *begin(); }
  reference back() { return *(end() - ); }
  const_reference back() const { return *(end() - ); }
  void push_back(const T& x) {
    if (finish != end_of_storage) {
      construct(finish, x);
      ++finish;
    }
    else
      insert_aux(end(), x);
  }
  void swap(vector<T, Alloc>& x) {
    __STD::swap(start, x.start);
    __STD::swap(finish, x.finish);
    __STD::swap(end_of_storage, x.end_of_storage);
  }

  // 插入操作
  iterator insert(iterator position, const T& x) {
    size_type n = position - begin();
    if (finish != end_of_storage && position == end()) {
      construct(finish, x);
      ++finish;
    }
    else
      insert_aux(position, x);
    return begin() + n;
  }
  iterator insert(iterator position) { return insert(position, T()); }
#ifdef __STL_MEMBER_TEMPLATES
  template <class InputIterator>
  void insert(iterator position, InputIterator first, InputIterator last) {
    range_insert(position, first, last, iterator_category(first));
  }
#else /* __STL_MEMBER_TEMPLATES */
  void insert(iterator position,
              const_iterator first, const_iterator last);
#endif /* __STL_MEMBER_TEMPLATES */

  void insert (iterator pos, size_type n, const T& x);
  void insert (iterator pos, int n, const T& x) {
    insert(pos, (size_type) n, x);
  }
  void insert (iterator pos, long n, const T& x) {
    insert(pos, (size_type) n, x);
  }

  // 删除最尾端元素
  void pop_back() {
    --finish;
    destroy(finish);
  }

  //清除某位置上的元素
  iterator erase(iterator position) {
    if (position +  != end())
      copy(position + , finish, position); // 后续元素往前移动
    --finish;
    destroy(finish);
    return position;
  }

  // 清除迭代器所指定的区间的元素
  iterator erase(iterator first, iterator last) {
    iterator i = copy(last, finish, first);
    destroy(i, finish);
    finish = finish - (last - first);
    return first;
  }

  // 重新设置 vector 大小，若设置值 new_size 大于当前 size，在尾端插入 x
  void resize(size_type new_size, const T& x) {
    if (new_size < size()) 
      erase(begin() + new_size, end());
    else
      insert(end(), new_size - size(), x);
  }
  void resize(size_type new_size) { resize(new_size, T()); }
  void clear() { erase(begin(), end()); }

protected:
  // 配置空间并填满内容，其中__STL_TRY、__STL_UNWIND 为异常相关的宏，在 stl_config.h 中定义
  iterator allocate_and_fill(size_type n, const T& x) {
    iterator result = data_allocator::allocate(n);
    __STL_TRY {
      uninitialized_fill_n(result, n, x);
      return result;
    }
    __STL_UNWIND(data_allocator::deallocate(result, n));
  }

#ifdef __STL_MEMBER_TEMPLATES
  template <class ForwardIterator>
  iterator allocate_and_copy(size_type n,
                             ForwardIterator first, ForwardIterator last) {
    iterator result = data_allocator::allocate(n);
    __STL_TRY {
      uninitialized_copy(first, last, result);
      return result;
    }
    __STL_UNWIND(data_allocator::deallocate(result, n));
  }
#else /* __STL_MEMBER_TEMPLATES */
  iterator allocate_and_copy(size_type n,
                             const_iterator first, const_iterator last) {
    iterator result = data_allocator::allocate(n);
    __STL_TRY {
      uninitialized_copy(first, last, result);
      return result;
    }
    __STL_UNWIND(data_allocator::deallocate(result, n));
  }
#endif /* __STL_MEMBER_TEMPLATES */


#ifdef __STL_MEMBER_TEMPLATES
  template <class InputIterator>
  void range_initialize(InputIterator first, InputIterator last,
                        input_iterator_tag) {
    for ( ; first != last; ++first)
      push_back(*first);
  }

  // This function is only called by the constructor.  We have to worry
  // about resource leaks, but not about maintaining invariants.
  template <class ForwardIterator>
  void range_initialize(ForwardIterator first, ForwardIterator last,
                        forward_iterator_tag) {
    size_type n = ;
    distance(first, last, n);
    start = allocate_and_copy(n, first, last);
    finish = start + n;
    end_of_storage = finish;
  }

  template <class InputIterator>
  void range_insert(iterator pos,
                    InputIterator first, InputIterator last,
                    input_iterator_tag);

  template <class ForwardIterator>
  void range_insert(iterator pos,
                    ForwardIterator first, ForwardIterator last,
                    forward_iterator_tag);

#endif /* __STL_MEMBER_TEMPLATES */
};
           

2.2 vector 的迭代器

vector 维护的是一个连续的线性空间，所以不论其元素型别如何，普通指针 都可以作为 vector 的迭代器而满足所有必要条件，因为 vector 迭代器所需要的操作行为，如 operator*，operator->，operator++， operator–， operator+，operator-，operator+=， operator-=，普通指针天生就具备。vector 支持随机存取，而普通指针正有这样的能力。所以，vector 提供的是 Random Access Iterators。

template <class T, class Alloc = alloc>
class vector
{
public:
    typedef T             value_type;
    typedef value_type*   iterator;
    ...
}
           

根据定义，如果客户端写出这样的代码：

vector<int>::iterator ivite;
vector<Shape>::iterator svite;
           

则，ivite 型别就是 int*，svite 的型别就是 Shape*。

2.3 vector 的数据结构

vector 所采用的数据结构非常简单：连续线性空间。它以；两个迭代器 start 和 finish 分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器 end_of_storage 指向整块连续空间（含备用空间）的尾端：

template <class T, class Alloc = alloc>
class vector
{
...
protected:
  iterator start;               // 表示目前使用空间的头
  iterator finish;              // 表示目前使用空间的尾
  iterator end_of_storage;      // 表示目前可用空间的尾
}
           

为了降低空间配置时的速度成本，vector 实际配置的大小可能比客户端需求量更大一些，以备将来可能的扩充。这便是容量（capacity）的概念。

添加新元素时，如果超出当时的容量，则容量会扩充至两倍，如果两倍容量仍不足，就扩充至足够大的容量。上述容量的扩张必须经历“重新配置、元素移动、释放空间”等过程。

2.4 vector 的构造和相关操作

vector 缺省使用 alloc 作为空间配置器，并据此定义出 data_allocator，为的是更方便的以元素大小作为配置单位：

template <class T, class Alloc = alloc>
class vector {
...
protected:
  typedef simple_alloc<value_type, Alloc> data_allocator;
...
  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:
  vector(size_type n, const T& value) { fill_initialize(n, value); }

protected:
  iterator allocate_and_fill(size_type n, const T& x) {
    iterator result = data_allocator::allocate(n);
    __STL_TRY {
      uninitialized_fill_n(result, n, x);
      return result;
    }
    __STL_UNWIND(data_allocator::deallocate(result, n));
  }
           

构造函数调用 fill_initialize，fill_initialize调用 allocate_and_fill，allocate_and_fill 调用 uninitialized_fill_n，uninitialized_fill_n 会根据第一参数的型别特性，决定使用算法 fill_n() 或反复调用 construct() 来完成任务。

void push_back(const T& x) {
    if (finish != end_of_storage) {
      construct(finish, x);
      ++finish;
    }
    else
      insert_aux(end(), x);
  }
           

push_back：

push_back 插入元素 x，若还有备用空间，直接在备用空间上构造，并调整迭代器 finish。如果没有备用空间了，就扩充空间（重新配置、移动数据、释放原空间）：

template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
  // 还有备用空间
  if (finish != end_of_storage) {
    construct(finish, *(finish - ));
    // 调整 finish
    ++finish;
    T x_copy = x;
    // 与 copy 本质相同，只是从后面复制,可以避免区间有重叠时覆盖数据的问题
    copy_backward(position, finish - , finish - );
    *position = x_copy;
  }
  // 已无备用空间
  else {
    const size_type old_size = size();
    const size_type len = old_size !=  ?  * old_size : ;
    // 以上配置原则为：
    // 如果原大小为0，则配置1；
    // 如果原大小不为0，则配置为原来2倍，前半段用来放置数据，后半段准备用来放置新数据
    iterator new_start = data_allocator::allocate(len);
    iterator new_finish = new_start;
    __STL_TRY {
      // 将原 vector 拷贝至新 vector
      new_finish = uninitialized_copy(start, position, new_start);
      // 为新元素设定初值 x
      construct(new_finish, x);
      // 调整 new_finish
      ++new_finish;
      // 将安插点的原内容也拷贝过来
      new_finish = uninitialized_copy(position, finish, new_finish);
    }

#       ifdef  __STL_USE_EXCEPTIONS 
    catch(...) {
      destroy(new_start, new_finish); 
      data_allocator::deallocate(new_start, len);
      throw;
    }
#       endif /* __STL_USE_EXCEPTIONS */
    // 析构并释放原 vector
    destroy(begin(), end());
    deallocate();
    // 调整迭代器
    start = new_start;
    finish = new_finish;
    end_of_storage = new_start + len;
  }
}
           

注意：一旦对 vector 的操作引起空间重新配置，指向原 vector 的所有迭代器就全部失效。

pop_back：

void pop_back() {
    --finish;
    destroy(finish);
  }
           

insert：

template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {
  // 当 n != 0 才进行以下所有操作
  if (n != ) {
    // 备用空间大于等于新增元素个数
    if (size_type(end_of_storage - finish) >= n) {
      T x_copy = x;
      const size_type elems_after = finish - position;
      iterator old_finish = finish;
      // 针对插入点后现有元素与新增元素个数的数量采取不同的操作
      // 插入点后现有元素个数大于新增元素个数
      if (elems_after > n) {
        uninitialized_copy(finish - n, finish, finish);
        finish += n;
        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 {
      // 备用空间小于新增元素个数（必须配置额外的内存）
      // 首先决定新长度：旧长度的2倍，或者旧长度+新增元素个数
      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 {
        new_finish = uninitialized_copy(start, position, new_start);
        new_finish = uninitialized_fill_n(new_finish, n, x);
        new_finish = uninitialized_copy(position, finish, new_finish);
      }
#         ifdef  __STL_USE_EXCEPTIONS 
      catch(...) {
        // 如有异常发生，实现 commit or rollback 语义
        destroy(new_start, new_finish);
        data_allocator::deallocate(new_start, len);
        throw;
      }
#         endif /* __STL_USE_EXCEPTIONS */
      // 清除并释放旧的 vector
      destroy(start, finish);
      deallocate();
      // 调整迭代器
      start = new_start;
      finish = new_finish;
      end_of_storage = new_start + len;
    }
  }
}
           

erase：

iterator erase(iterator position) {
  if (position +  != end())
    copy(position + , finish, position);
  --finish;
  destroy(finish);
  return position;
}
iterator erase(iterator first, iterator last) {
  iterator i = copy(last, finish, first);
  destroy(i, finish);
  finish = finish - (last - first);
  return first;
}
           

resize 和 clear：

void resize(size_type new_size, const T& x) {
  if (new_size < size()) 
    erase(begin() + new_size, end());
  else
    insert(end(), new_size - size(), x);
}
void resize(size_type new_size) { resize(new_size, T()); }
void clear() { erase(begin(), end()); }
           

3. 序列式容器之 list

相对于 vector 的连续线性空间，list 就显得复杂许多，它的好处是每次插入或删除一个元素，就配置或释放一个元素的空间。因此，list 对于空间的运用绝对精准，一点也不浪费。而且对于任何位置的元素插入或删除，list 都是常数时间。

list 和 vector 是两个最常用的容器。在什么时机下选择哪一种容器，必须视元素的多寡、元素构造复杂度（有无 non-trivial copy construct，non-trivial copy assignmen operator）、元素存取行为的特性而定。

3.1 list 的节点、迭代器和数据结构

每一个设计过 list 的人都知道，list 本身和 list 的节点是不同的结构，需要分开设计。以下是 STL list 的节点结构：

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

list_node_allocator(n) 表示配置 n 个节点空间。以下四个函数：

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

list 提供许多构造函数，其中一个是默认构造函数，构造一个空的 list：

...
protected
  void empty_initialize() { 
    node = get_node();
    node->next = node;
    node->prev = node;
  }
public:
  list() { empty_initialize(); }
...
           

其他构造函数与 vector 类似，调用 fill_initialize：

void fill_initialize(size_type n, const T& value) {
  empty_initialize();
  __STL_TRY {
    insert(begin(), n, value);
  }
  __STL_UNWIND(clear(); put_node(node));
}
           

list 不再能够像 vector 一样以普通指针作为迭代器，因为其节点不保证在存储空间连续存在。list 的迭代器必须有能力指向 list 的节点，并有能力进行正确的递增、递减、取值、成员存取等操作。

由于 STL list 是一个双向链表，迭代器必须具备前移、后移的能力，所以 list 提供的迭代器是 Bidirectional Iterators。此外，list 的插入（insert）和接合 splice 都不会造成原有 list 迭代器失效，删除（erase）操作只会导致指向被删除的那个迭代器失效，其他迭代器不受影响。

以下是 list 迭代器的设计：

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;

  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 节点

  __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 */

  // 迭代器递增1，返回左值、右值
  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;
  }
};
           

3.2 list 的数据结构

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

template <class T, class 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;
...
protected:
  link_type node;
           

让指针 node 指向刻意置于尾端的一个空白节点，node 便能符合 STL 对于“前闭后开”区间的要求，成为 last 迭代器，如下函数便可轻易完成：

// begin、end、rbegin、rend
iterator begin() { return (link_type)((*node).next); }
const_iterator begin() const { return (link_type)((*node).next); }
iterator end() { return node; }
const_iterator end() const { return node; }
reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } 

// empty、size、max_size
bool empty() const { return node->next == node; }
size_type size() const {
  size_type result = ;
  distance(begin(), end(), result);
  return result;
}
size_type max_size() const { return size_type(-); }

// front、back
reference front() { return *begin(); }
const_reference front() const { return *begin(); }
reference back() { return *(--end()); }
const_reference back() const { return *(--end()); }
           

3.3 list 的构造和相关操作

list 默认使用 alloc 作为空间配置器，并据此另外定义一个list list_node_allocator，为的是更方便地以节点大小配置单位：

template <class T, class Alloc = alloc>
class list {
protected:
...
  typedef __list_node<T> list_node;
  typedef simple_alloc<list_node, Alloc> list_node_allocator;
...
}
           

list 的常见操作主要包括：insert、push_front、push_back、erase、pop_front、pop_back、clear、remove、unique、splice、merge、sort 等。

// 在指定节点插入一个节点
iterator insert(iterator position, const T& x) {
  link_type tmp = create_node(x);
  tmp->next = position.node;
  tmp->prev = position.node->prev;
  (link_type(position.node->prev))->next = tmp;
  position.node->prev = tmp;
  return tmp;
}

// 插入一个节点，作为头节点
void push_front(const T& x) { insert(begin(), x); }

// 插入一个节点，作为尾节点
void push_back(const T& x) { insert(end(), x); }

// 删除指定节点
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 <class T, class Alloc> 
void list<T, Alloc>::clear() {
  link_type cur = (link_type) node->next;
  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) {
  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;
  }
}

// 将 [first,last) 内的所有元素移动到 position 之前，是一个非公开接口
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;
  }
}

// 接合操作：将某连续范围的元素从一个 list 移动到另一个（或者同一）list 的某个定点
// 为了提供各种接口弹性，list<T>::splice 有许多版本
void splice(iterator position, list& x) {
  if (!x.empty()) 
    transfer(position, x.begin(), x.end());
 }
void splice(iterator position, list&, iterator i) {
  iterator j = i;
  ++j;
  if (position == i || position == j) return;
  transfer(position, i, j);
}
void splice(iterator position, list&, iterator first, iterator last) {
  if (first != last) 
    transfer(position, first, last);
}

// 将 x 合并到 *this 上，两个 lists 的内容都必须先经过递增排序
template <class T, class Alloc>
void list<T, Alloc>::merge(list<T, Alloc>& x) {
  iterator first1 = begin();
  iterator last1 = end();
  iterator first2 = x.begin();
  iterator last2 = x.end();
  // 两个 list 都已是递增排序
  while (first1 != last1 && first2 != last2)
    if (*first2 < *first1) {
      iterator next = first2;
      transfer(first1, first2, ++next);
      first2 = next;
    }
    else
      ++first1;
  if (first2 != last2) transfer(last1, first2, last2);
}

// 翻转 list
template <class T, class Alloc>
void list<T, Alloc>::reverse() {
  // 若链表尾空或者只有一个节点，则不进行任何操作
  if (node->next == node || link_type(node->next)->next == node) return;
  iterator first = begin();
  ++first;
  while (first != end()) {
    iterator old = first;
    ++first;
    transfer(begin(), old, first);
  }
}

// list 不能使用 STL 的 sort 算法，必须使用自己的 sort，采用的是 quick sort
// 原因是 STL 算法 sort 只接受 RamdonAccessIterator
template <class T, class Alloc>
void list<T, Alloc>::sort() {
  // 若链表尾空或者只有一个节点，则不进行任何操作
  if (node->next == node || link_type(node->next)->next == node) return;
  list<T, Alloc> carry;
  list<T, Alloc> counter[];
  int fill = ;
  while (!empty()) {
    carry.splice(carry.begin(), *this, begin());
    int i = ;
    while(i < fill && !counter[i].empty()) {
      counter[i].merge(carry);
      carry.swap(counter[i++]);
    }
    carry.swap(counter[i]);         
    if (i == fill) ++fill;
  } 

  for (int i = ; i < fill; ++i) counter[i].merge(counter[i-]);
  swap(counter[fill-]);
}