template <class T>

struct list_node{

	list_node* prev; 

	list_node* next;

	T data; 

};

struct _List_node_base {

  _List_node_base* _M_next;     // 后继

  _List_node_base* _M_prev;     // 前驱

};

/* 节点 */

template <class _Tp>

struct _List_node : public _List_node_base {

  _Tp _M_data;                 //  数据

};

template <class _Tp, class _Alloc>

class _List_base 

{

public:

  typedef _Alloc allocator_type;									// 空间配置器类型 allocator_type

  allocator_type get_allocator() const { return allocator_type(); }    

  _List_base(const allocator_type&) {								//  构造函数

    _M_node = _M_get_node();

    _M_node->_M_next = _M_node;

    _M_node->_M_prev = _M_node;

  }

  ~_List_base() {

    clear();

    _M_put_node(_M_node);

  }

  void clear();

protected:

  typedef simple_alloc<_List_node<_Tp>, _Alloc> _Alloc_type;

  _List_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }

  void _M_put_node(_List_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); } 

protected:

  _List_node<_Tp>* _M_node;

};

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >

class list : protected _List_base<_Tp, _Alloc> {

  // requirements:

  __STL_CLASS_REQUIRES(_Tp, _Assignable);

  typedef _List_base<_Tp, _Alloc> _Base;

protected:

  typedef void* _Void_pointer;

public:      

  typedef _Tp value_type;                              //  数据类型 : value_type

  typedef value_type* pointer;                         //  指针 : pointer

  typedef const value_type* const_pointer;             //  常量指针 : const_pointer

  typedef value_type& reference;                       //  引用 : reference

  typedef const value_type& const_reference;           //  

  typedef _List_node<_Tp> _Node;

  typedef size_t size_type;

  typedef ptrdiff_t difference_type;

  typedef typename _Base::allocator_type allocator_type;

  allocator_type get_allocator() const { return _Base::get_allocator(); }

public:

  typedef _List_iterator<_Tp,_Tp&,_Tp*>             iterator;

  typedef _List_iterator<_Tp,const _Tp&,const _Tp*> 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:

#ifdef __STL_HAS_NAMESPACES

  using _Base::_M_node;

  using _Base::_M_put_node;

  using _Base::_M_get_node;

#endif /* __STL_HAS_NAMESPACES */

protected:

  _Node* _M_create_node(const _Tp& __x)

  {

    _Node* __p = _M_get_node();

    __STL_TRY {

      _Construct(&__p->_M_data, __x);

    }

    __STL_UNWIND(_M_put_node(__p));

    return __p;

  }

  _Node* _M_create_node()

  {

    _Node* __p = _M_get_node();

    __STL_TRY {

      _Construct(&__p->_M_data);

    }

    __STL_UNWIND(_M_put_node(__p));

    return __p;

  }

public:

  explicit list(const allocator_type& __a = allocator_type()) : _Base(__a) {}

  iterator begin()             { return (_Node*)(_M_node->_M_next); }

  const_iterator begin() const { return (_Node*)(_M_node->_M_next); }

  iterator end()             { return _M_node; }

  const_iterator end() const { return _M_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 */

  bool empty() const { return _M_node->_M_next == _M_node; }

  size_type size() const {

    size_type __result = 0;

    distance(begin(), end(), __result);

    return __result;

  }

  size_type max_size() const { return size_type(-1); }

  reference front() { return *begin(); }

  const_reference front() const { return *begin(); }

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

  const_reference back() const { return *(--end()); }

  /* 交换 swap */

  void swap(list<_Tp, _Alloc>& __x) { __STD::swap(_M_node, __x._M_node); }

  /* 插入 insert */

  iterator insert(iterator __position, const _Tp& __x) {

    _Node* __tmp = _M_create_node(__x);

    __tmp->_M_next = __position._M_node;

    __tmp->_M_prev = __position._M_node->_M_prev;

    __position._M_node->_M_prev->_M_next = __tmp;

    __position._M_node->_M_prev = __tmp;

    return __tmp;

  }

  iterator insert(iterator __position) { return insert(__position, _Tp()); }

#ifdef __STL_MEMBER_TEMPLATES

  // Check whether it's an integral type.  If so, it's not an iterator.

  template<class _Integer>

  void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,

                          __true_type) {

    _M_fill_insert(__pos, (size_type) __n, (_Tp) __x);

  }

  template <class _InputIterator>

  void _M_insert_dispatch(iterator __pos,

                          _InputIterator __first, _InputIterator __last,

                          __false_type);

  template <class _InputIterator>

  void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {

    typedef typename _Is_integer<_InputIterator>::_Integral _Integral;

    _M_insert_dispatch(__pos, __first, __last, _Integral());

  }

#else /* __STL_MEMBER_TEMPLATES */

  void insert(iterator __position, const _Tp* __first, const _Tp* __last);

  void insert(iterator __position,

              const_iterator __first, const_iterator __last);

#endif /* __STL_MEMBER_TEMPLATES */

  void insert(iterator __pos, size_type __n, const _Tp& __x)

    { _M_fill_insert(__pos, __n, __x); }

  void _M_fill_insert(iterator __pos, size_type __n, const _Tp& __x); 

  void push_front(const _Tp& __x) { insert(begin(), __x); }

  void push_front() {insert(begin());}

  void push_back(const _Tp& __x) { insert(end(), __x); }

  void push_back() {insert(end());}

  iterator erase(iterator __position) {

    _List_node_base* __next_node = __position._M_node->_M_next;

    _List_node_base* __prev_node = __position._M_node->_M_prev;

    _Node* __n = (_Node*) __position._M_node;

    __prev_node->_M_next = __next_node;

    __next_node->_M_prev = __prev_node;

    _Destroy(&__n->_M_data);

    _M_put_node(__n);

    return iterator((_Node*) __next_node);

  }

  iterator erase(iterator __first, iterator __last);

  void clear() { _Base::clear(); }

  void resize(size_type __new_size, const _Tp& __x);

  void resize(size_type __new_size) { this->resize(__new_size, _Tp()); }

  void pop_front() { erase(begin()); }

  void pop_back() { 

    iterator __tmp = end();

    erase(--__tmp);

  }

  list(size_type __n, const _Tp& __value,

       const allocator_type& __a = allocator_type())

    : _Base(__a)

    { insert(begin(), __n, __value); }

  explicit list(size_type __n)

    : _Base(allocator_type())

    { insert(begin(), __n, _Tp()); }

#ifdef __STL_MEMBER_TEMPLATES

  // We don't need any dispatching tricks here, because insert does all of

  // that anyway.  

  template <class _InputIterator>

  list(_InputIterator __first, _InputIterator __last,

       const allocator_type& __a = allocator_type())

    : _Base(__a)

    { insert(begin(), __first, __last); }

#else /* __STL_MEMBER_TEMPLATES */

  list(const _Tp* __first, const _Tp* __last,

       const allocator_type& __a = allocator_type())

    : _Base(__a)

    { this->insert(begin(), __first, __last); }

  list(const_iterator __first, const_iterator __last,

       const allocator_type& __a = allocator_type())

    : _Base(__a)

    { this->insert(begin(), __first, __last); }

#endif /* __STL_MEMBER_TEMPLATES */

  list(const list<_Tp, _Alloc>& __x) : _Base(__x.get_allocator())

    { insert(begin(), __x.begin(), __x.end()); }

  ~list() { }

  list<_Tp, _Alloc>& operator=(const list<_Tp, _Alloc>& __x);

public:

  // assign(), a generalized assignment member function.  Two

  // versions: one that takes a count, and one that takes a range.

  // The range version is a member template, so we dispatch on whether

  // or not the type is an integer.

  void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }

  void _M_fill_assign(size_type __n, const _Tp& __val);

#ifdef __STL_MEMBER_TEMPLATES

  template <class _InputIterator>

  void assign(_InputIterator __first, _InputIterator __last) {

    typedef typename _Is_integer<_InputIterator>::_Integral _Integral;

    _M_assign_dispatch(__first, __last, _Integral());

  }

  template <class _Integer>

  void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)

    { _M_fill_assign((size_type) __n, (_Tp) __val); }

  template <class _InputIterator>

  void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,

                          __false_type);

#endif /* __STL_MEMBER_TEMPLATES */

protected:

  void transfer(iterator __position, iterator __first, iterator __last) {

    if (__position != __last) {

      // Remove [first, last) from its old position.

      __last._M_node->_M_prev->_M_next     = __position._M_node;

      __first._M_node->_M_prev->_M_next    = __last._M_node;

      __position._M_node->_M_prev->_M_next = __first._M_node; 

      // Splice [first, last) into its new position.

      _List_node_base* __tmp      = __position._M_node->_M_prev;

      __position._M_node->_M_prev = __last._M_node->_M_prev;

      __last._M_node->_M_prev     = __first._M_node->_M_prev; 

      __first._M_node->_M_prev    = __tmp;

    }

  }

public:

  void splice(iterator __position, list& __x) {

    if (!__x.empty()) 

      this->transfer(__position, __x.begin(), __x.end());

  }

  void splice(iterator __position, list&, iterator __i) {

    iterator __j = __i;

    ++__j;

    if (__position == __i || __position == __j) return;

    this->transfer(__position, __i, __j);

  }

  void splice(iterator __position, list&, iterator __first, iterator __last) {

    if (__first != __last) 

      this->transfer(__position, __first, __last);

  }

  void remove(const _Tp& __value);

  void unique();

  void merge(list& __x);

  void reverse();

  void sort();

#ifdef __STL_MEMBER_TEMPLATES

  template <class _Predicate> void remove_if(_Predicate);

  template <class _BinaryPredicate> void unique(_BinaryPredicate);

  template <class _StrictWeakOrdering> void merge(list&, _StrictWeakOrdering);

  template <class _StrictWeakOrdering> void sort(_StrictWeakOrdering);

#endif /* __STL_MEMBER_TEMPLATES */

};