///STL list为双向循环链表

struct _List_node_base {
  _List_node_base* _M_next;
  _List_node_base* _M_prev;
};

template 
  
   
struct _List_node : public _List_node_base {
  _Tp _M_data;
};

struct _List_iterator_base {
  typedef size_t                     size_type;
  typedef ptrdiff_t                  difference_type;
  typedef bidirectional_iterator_tag iterator_category;   ///迭代器为双向迭代器

  _List_node_base* _M_node;   ///迭代器使用_List_node_base*标志其指向

  _List_iterator_base(_List_node_base* __x) : _M_node(__x) {}
  _List_iterator_base() {}

  void _M_incr() { _M_node = _M_node->_M_next; }
  void _M_decr() { _M_node = _M_node->_M_prev; }

  bool operator==(const _List_iterator_base& __x) const {
    return _M_node == __x._M_node;
  }
  bool operator!=(const _List_iterator_base& __x) const {
    return _M_node != __x._M_node;
  }
};

template
   
     struct _List_iterator : public _List_iterator_base { typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator; typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; typedef _List_iterator<_Tp,_Ref,_Ptr> _Self; typedef _Tp value_type; typedef _Ptr pointer; typedef _Ref reference; typedef _List_node<_Tp> _Node; ///实际指向的类型 _List_iterator(_Node* __x) : _List_iterator_base(__x) {} _List_iterator() {} _List_iterator(const iterator& __x) : _List_iterator_base(__x._M_node) {} reference operator*() const { ///该函数虽然可能修改结点的值,但因迭代器对象只保存 ///指向结点的指针,因此仍然声明为const return ((_Node*) _M_node)->_M_data; } pointer operator->() const { return &(operator*()); } _Self& operator++() { this->_M_incr(); return *this; } _Self operator++(int) { _Self __tmp = *this; this->_M_incr(); return __tmp; } _Self& operator--() { this->_M_decr(); return *this; } _Self operator--(int) { _Self __tmp = *this; this->_M_decr(); return __tmp; } }; inline bidirectional_iterator_tag iterator_category(const _List_iterator_base&) { return bidirectional_iterator_tag(); } template 
    
      inline _Tp* value_type(const _List_iterator<_Tp, _Ref, _Ptr>&) { return 0; } inline ptrdiff_t* distance_type(const _List_iterator_base&) { return 0; } template 
     
       class _List_base { public: typedef _Alloc allocator_type; allocator_type get_allocator() const { return allocator_type(); } _List_base(const allocator_type&) { ///唯一的构造函数,规定了list为空时的合法状态:头结点的前后指针均指向其自身 _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 
      
        void _List_base<_Tp,_Alloc>::clear() { ///由于结点的_M_next均为基类指针,而基类指针不能直接初始化或者赋值给 ///派生类指针,因此需要强制类型转化,已将_M_node->_M_next强制转化为其 ///实质类型的指针. _List_node<_Tp>* __cur = (_List_node<_Tp>*) (_M_node->_M_next); while (__cur != _M_node) { _List_node<_Tp>* __tmp = __cur; __cur = (_List_node<_Tp>*) (__cur->_M_next); _Destroy(&__tmp->_M_data); ///析构结点数据元素 _M_put_node(__tmp); ///归还结点内存 } ///使链表恢复合法状态 _M_node->_M_next = _M_node; _M_node->_M_prev = _M_node; } template 
       
         class list : protected _List_base<_Tp, _Alloc> { __STL_CLASS_REQUIRES(_Tp, _Assignable); typedef _List_base<_Tp, _Alloc> _Base; protected: typedef void* _Void_pointer; public: typedef _Tp 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<_Tp> _Node; typedef size_t size_type; typ