STL学习_stl_list.h_源码分析

stl_list.h中有几个函数自己觉得比较重要，transfer()  merge()  sort()

#ifndef _SGI_STL_INTERNAL_LIST_H
#define _SGI_STL_INTERNAL_LIST_H
 
//list迭代器结构
//不同的容器往往要给容器设置符合自己的迭代器，list的迭代器类型是双向迭代器
//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;
    //这样写的目的是，为了否和规范，自行开发的迭代器因该提供五个内嵌相应型别，
    //以利于traits萃取。
    typedef bidirectional_iterator_tag iterator_category;
    typedef T value_type;
    typedef Ref reference;
    typedef Ptr pointer;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef __list_node<T>* link_type;
    //迭代器内部指针node指向list的节点
    link_type node;
    //list迭代器的构造函数
    __list_iterator(){}
    __list_iterator(link_type x):node(x){}
    __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;
    }
    //对迭代器的成员存取
    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;
    }
    
};
//list的节点结构
template<class T>
struct __list_node{
    typedef void* void_pointer;
    void_pointer next;
    void_pointer perv;
    T data;
};
 
//list的结构
//list缺省使用alloc第二空间配置器
template<class T, class Alloc=alloc>
class list{
protected:
    typedef __list_node<T> list_node;
    //定义的list_node_allocator这个专属空间配置器，方便以节点大小为配置单位
    typedef simple_alloc<list_node, Alloc> list_node_allocator;
    typedef void* void_pointer;
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;
    size_t 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;
    //逆置迭代器
    typedef reverse_iterator<const_iterator> const_reverse_iterator;
    typedef reverse_iterator<iterator> reverse_iterator;
public:
    //list提供的接口
    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());
    }
    bool empty()const{return node->next == 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(){return *(--end());}
 
    void swap(list<T, Alloc>&x)
    {
        __STD::swap(node, x.node);
    }
 
    void clear();
    iterator erase(iterator position);
    iterator erase(iterator first, iterator last);
    //