STL中list与其他顺序容器实现不同因此不支持一部分容器操作，注：forward_list 有自己特有的insert 和emplace,vetor和string不支持push_front和emplace_front

STL的list是一个双向链表，而且实现的是个环状双向链表，因此一个指针即可代表整个链表。

为了符合STL对于前闭后开的区间要求，node指针指向特意置于尾端的一个空白节点，以符合这个要求。

here is the source code

  
// list结点, 提供双向访问能力  
  
//  --------           --------           --------           --------  
//  | next |---------->| next |---------->| next |---------->| next |  
//  --------           --------           --------           --------  
//  | prev |<----------| prev |<----------| prev |<----------| prev |  
//  --------           --------           --------           --------  
//  | data |           | data |           | data |           | data |  
//  --------           --------           --------           --------  
  
  
template <class T>  
struct __list_node  
{  
    typedef void* void_pointer;  
    void_pointer next;  
    void_pointer prev;  
    T data;  
};  
  
// 至于为什么不使用默认参数, 这个是因为有一些编译器不能提供推导能力,  
// 而作者又不想维护两份代码, 故不使用默认参数  
template<class T, class Ref, class Ptr>  
struct __list_iterator  
{  
    typedef __list_iterator<T, T&, T*>             iterator;   // STL标准强制要求  
    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) {}  
  
    // 在STL算法中需要迭代器提供支持  
    bool operator==(const self& x) const { return node == x.node; }  
    bool operator!=(const self& x) const { return node != x.node; }  
  
    // 以下对迭代器取值（dereference）,取的是节点的数据值  
    reference operator*() const { return (*node).data; }  
  
    // 以下是迭代器的成员存取运算子的标准做法  
    pointer operator->() const { return &(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;  
    }  
};  
  
  
// list不仅是个双向链表, 而且还是一个环状双向链表  
  
//       end()              头结点             begin()  
//         ↓                  ↓                  ↓  
//      --------           --------           --------           --------  
// ---->| next |---------->| next |---------->| next |---------->| next |------  
// |    --------           --------           --------           --------     |  
// |  --| prev |<----------| prev |<----------| prev |<----------| prev |<--| |  
// |  | --------           --------           --------           --------   | |  
// |  | | data |           | data |           | data |           | data |   | |  
// |  | --------           --------           --------           --------   | |  
// |  |                                                                     | |  
// |  | --------           --------           --------           --------   | |  
// ---|-| next |<----------| next |<----------| next |<----------| next |<--|--  
//    | --------           --------           --------           --------   |  
//    ->| prev |---------->| prev |---------->| prev |---------->| prev |----  
//      --------           --------           --------           --------  
//      | data |           | data |           | data |           | data |  
//      --------           --------           --------           --------