//链表结点结构 template <class T> struct _list_node {typedef void *void_pointer;//指针类型为void *,其实可以设为_list_node<T>* void_pointer prev;void_pointer next;T data; };/* 迭代器有五种类型，Input Iterator,output Iterator,Forward Iterator只支持++，Biderectional Iterator支持++、--,Random Access Iterator支持 所有运算，效率最高 */ struct input_iterator_tag{}; struct output_iterator_tag{}; struct forward_iterator_tag :public input_iterator_tag{}; struct bidirectional_iterator_tag :public forward_iterator_tag{}; struct random_access_iterator_tag :public bidirectional_iterator_tag{};//list迭代器设计 template <class T,class Ref,class Ptr> struct _list_iterator {typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, Ref, Ptr>self;//traits萃取 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){}reference operator*()const{return (*node).data;}pointer operator->()const{return &(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;} };//SGI list是一个环状双向链表 template<class T,class Alloc=alloc> class list { protected:typedef _list_node<T> list_node; public:typedef list_node* link_type;protected:link_type node;//该指针表示整个环状双向链表，可使其指向置于尾端的一个空白结点//list缺省使用alloc作为空间配置器，并据此另外定义了list_node_allocator,为的是更方便地以节点大小为配置单位typedef simple_alloc<list_node, Alloc>list_node_allocator; };
