• 欢迎浏览“String me = Creater\忠实的资深Linux玩家;”,请文明浏览,理性发言,有侵犯你的权益请邮件我(creater@vip.qq.com).
  • 把任何的失败都当作一次尝试,不要自卑;把所有的成功都想成是一种幸运,不要自傲。
  •    5年前 (2013-05-01)  STL |   3 条评论  13 
    文章评分 0 次,平均分 0.0

    list内部采用双向链表实现,而且还是一个环状双向链表,使用一个指针就可以访问整个链表。list的每个节点定义如下。

    template <class T>
    struct __list_node {
      typedef void* void_pointer;
      void_pointer next;
      void_pointer prev;
      T data;
    };

    那么list如下定义呢?一下只截取部分代码

    template <class T, class Alloc = alloc>
    class list {
    protected:
      typedef void* void_pointer;
      typedef __list_node<T> list_node;
      typedef simple_alloc<list_node, Alloc> list_node_allocator;
    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;
      typedef 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;
    protected:
      link_type node;
    };

    在list的定义中,每个节点定义为typedef __list_node list_node;
    那么指向每个节点的指针为typedef list_node* link_type;
    前面说了,一个list,可以用一个指针访问,那么整个指针为link_type node,整个指针式list类内部使用。然而对于客户要使用list,并且融入stl框架,则需要迭代器。那么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;
    
      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_iterator(link_type x) : node(x) {}
      __list_iterator() {}
      __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; }
    
    #ifndef __SGI_STL_NO_ARROW_OPERATOR
      pointer operator->() const { return &(operator*()); }
    #endif /* __SGI_STL_NO_ARROW_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;
      }
    };

    迭代器定义了一些内置类型,==与!=操作符,取地址与解引用,自增,自减等。另外观察到迭代器类里的唯一数据成员 link_type node。可以知道这个迭代器__list_iterator 是指向节点指针的包装。当然由前缀可以知道__list_iterator 并不是提供给客户使用的。
    在list里我们看到
    typedef __list_iterator iterator;
    typedef __list_iterator const_iterator;
    到这里,list的迭代器就做好了,客户可以使用iterator,const_iterator来操作list容器了。 这个iterator就是list配套的迭代器。

     

    除特别注明外,本站所有文章均为String me = "Creater\忠实的资深Linux玩家";原创,转载请注明出处来自http://unix8.net/home.php/898.html

    关于

    发表评论

    暂无评论

    切换注册

    登录

    忘记密码 ?

    切换登录

    注册

    扫一扫二维码分享