SGI list代码分析与原理解析[1]

2013年5月1日 由 Creater 留言 »

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配套的迭代器。

广告位

发表评论

你必须 登陆 方可发表评论.