STL源码剖析--迭代器

STL设计的精髓在于，把容器（Containers）和算法（Algorithms）分开，彼此独立设计，最后再用迭代器（Iterator）把他们粘 合在一起。可见迭代器在STL中的重要程度。迭代器已经作为一种设计思想被记录与《设计模式》中，它的意图在于“提供一种方法顺序访问一个聚合对象中的各 个元素，而又不需暴露该对象的内部表示”。

  迭代器的作用其实相当于一个智能指针，它指向容器内部的数据，可以通过operator *操作符来解指针获得数据的值，也可以通过operator ->操作符来获取数据的指针，还能够重载++,--等运算符来移动指针。

 

迭代器的分类

迭代器大致可以分为以下几种：

1、Input Interator ：只允许作为输入，也就是只读（Read Only）
2、Output Interator ：只允许作为输出，也就是只写（Write Only）
3、Forward Interator ：允许读写，但只能做前向移动
4、Bidirectional Interator ：允许读写，可以做双向移动
5、Random Access Interator ：允许读写，可以任意移动

  1. struct input_iterator_tag {};
  2. struct output_iterator_tag {};
  3. struct forward_iterator_tag : public input_iterator_tag {};
  4. struct bidirectional_iterator_tag : public forward_iterator_tag {};
  5. struct random_access_iterator_tag : public bidirectional_iterator_tag {};

实现原理

下面以List为例说明迭代器的原理

  1. // List节点的定义
  2. template <class T>
  3. struct __list_node {
  4.   typedef void* void_pointer;
  5.   void_pointer next;
  6.   void_pointer prev;
  7.   T data;
  8. };
  10. // List迭代器的定义
  11. template<class T, class Ref, class Ptr>
  12. struct __list_iterator {
  13.   // 这三个typedef是为了简化后面的代码书写
  14.   typedef __list_iterator<T, T&, T*>             iterator;
  15.   typedef __list_iterator<T, const T&, const T*> const_iterator;
  16.   typedef __list_iterator<T, Ref, Ptr>           self;
  18.   typedef bidirectional_iterator_tag iterator_category;     // 迭代器类型属于bidirectional iterator
  19.   typedef T value_type;     // 值类型
  20.   typedef Ptr pointer;      // 指针类型
  21.   typedef Ref reference;    // 引用类型
  22.   typedef __list_node<T>* link_type;    // 节点指针类型
  23.   typedef size_t size_type;
  24.   typedef ptrdiff_t difference_type;
  26.   link_type node;   // 迭代器当前所指的节点
  28.   // 三种构造函数
  29.   __list_iterator(link_type x) : node(x) {}
  30.   __list_iterator() {}
  31.   __list_iterator(const iterator& x) : node(x.node) {}
  33.   // ==和!=操作符重载
  34.   bool operator==(const self& x) const { return node == x.node; }
  35.   bool operator!=(const self& x) const { return node != x.node; }
  36.   
  37.   // *操作符，汲取所指节点中的数据
  38.   reference operator*() const { return (*node).data; }
  39.   // ->操作符，汲取所指节点中数据的地址
  40.   pointer operator->() const { return &(operator*()); 
  41.   // 前置++操作符，指向下一个节点
  42.   self& operator++() { 
  43.     node = (link_type)((*node).next);
  44.     return *this;
  45.   }
  46.   // 后置++操作符，指向下一个节点
  47.   self operator++(int) { 
  48.     self tmp = *this;
  49.     ++*this;
  50.     return tmp;
  51.   }
  52.   // 前置--操作符，指向前一个节点
  53.   self& operator--() { 
  54.     node = (link_type)((*node).prev);
  55.     return *this;
  56.   }
  57.   // 后置--操作符，指向前一个节点
  58.   self operator--(int) { 
  59.     self tmp = *this;
  60.     --*this;
  61.     return tmp;
  62.   }
  63. };
  65. template <class T, class Alloc = alloc>
  66. class list {
  67.   ...
  68.   ...
  70. public:
  71.   typedef __list_iterator<T, T&, T*>             iterator;          // 注意iterator所用的就是__list_iterator
  72.   typedef __list_iterator<T, const T&, const T*> const_iterator;
  74.   ...
  75.   ...
  77. protected:
  78.   link_type node;   // 头节点,该List其实是一个带头节点的双向循环链表
  80. public:
  81.   list() { empty_initialize(); }
  83.   iterator begin() { return (link_type)((*node).next); }        // 返回头节点的下一个节点，即第一个节点的iterator
  84.   const_iterator begin() const { return (link_type)((*node).next); }
  85.   iterator end() { return node; }               // 返回头节点的iterator，其实就是返回链表的结尾
  86.   const_iterator end() const { return node; }
  87.   
  88.   ...
  89.   ...
  90. }

如果我们对List容器使用find算法，这一过程中会发生什么？
int a[] = {1,2,3,4,5};
list<int> l(a, a+5);
list<int>::iterator it = find(l.begin(), l.end(), 3);
cout << *it << end;

先看看find函数的定义

  1. template <class InputIterator, class T>
  2. InputIterator find(InputIterator first, InputIterator last, const T& value) {
  3.   while (first != last && *first != value) ++first;
  4.   return first;
  5. }

  我们所调用的find函数的特化版本其实是：
find<__list_iterator<int, int&, int*>, int>(__list_iterator<int, int&, int*> first, __list_iterator<int, int&, int*> last, const int& value)
从而find函数中所用到的!=、*、++等操作符都作用在__list_iterator<int, int&, int*>的身上，这正是泛型的作用所在。

 

STL中迭代器的各种特性

  还记得我在《STL源码剖析学习笔记2——神奇的__type_traits》中所提到的traits编程技巧么？在STL的迭代器中同样用到了这种技巧，因为STL的迭代器在使用的时候需要了解各种迭代器的特性。主要特性包含以下几种：
1、iterator_category：表示迭代器所属的类型
2、value_type：表示迭代器所指数据的类型
3、difference_type：表示两个迭代器之间的距离类型
4、pointer：表示迭代器所指数据的指针类型
5、reference：表示迭代器所指数据的引用类型

  通常迭代器的几种特性被放在iterator_traits中。

  1. // 对所有Iterator的泛化
  2. template <class Iterator>
  3. struct iterator_traits {
  4.   typedef typename Iterator::iterator_category iterator_category;
  5.   typedef typename Iterator::value_type        value_type;
  6.   typedef typename Iterator::difference_type   difference_type;
  7.   typedef typename Iterator::pointer           pointer;
  8.   typedef typename Iterator::reference         reference;
  9. };
  11. // 对指针类型的偏特化（Partial Spetialization）
  12. template <class T>
  13. struct iterator_traits<T*> {
  14.   typedef random_access_iterator_tag iterator_category;     // 指针类型是可以随机访问的
  15.   typedef T                          value_type;            // 值类型
  16.   typedef ptrdiff_t                  difference_type;       // 指针类型之间的距离一定是整型（ptrdiff_t被定义为int型）
  17.   typedef T*                         pointer;
  18.   typedef T&                         reference;
  19. };
  20. template <class T>
  21. struct iterator_traits<const T*> {      // 同上，只不过这里是常量指针
  22.   typedef random_access_iterator_tag iterator_category;
  23.   typedef T                          value_type;
  24.   typedef ptrdiff_t                  difference_type;
  25.   typedef const T*                   pointer;
  26.   typedef const T&                   reference;
  27. };

  各种不同的迭代器的特性定义如下：

  1. // input iterator的属性
  2. template <class T, class Distance> struct input_iterator {
  3.   typedef input_iterator_tag iterator_category;
  4.   typedef T                  value_type;
  5.   typedef Distance           difference_type;
  6.   typedef T*                 pointer;
  7.   typedef T&                 reference;
  8. };
  9. // output iterator的属性
  10. struct output_iterator {
  11.   typedef output_iterator_tag iterator_category;
  12.   typedef void                value_type;
  13.   typedef void                difference_type;
  14.   typedef void                pointer;
  15.   typedef void                reference;
  16. };
  17. // forward iterator的属性
  18. template <class T, class Distance> struct forward_iterator {
  19.   typedef forward_iterator_tag iterator_category;
  20.   typedef T                    value_type;
  21.   typedef Distance             difference_type;
  22.   typedef T*                   pointer;
  23.   typedef T&                   reference;
  24. };
  25. // bidirectional iterator的属性
  26. template <class T, class Distance> struct bidirectional_iterator {
  27.   typedef bidirectional_iterator_tag iterator_category;
  28.   typedef T                          value_type;
  29.   typedef Distance                   difference_type;
  30.   typedef T*                         pointer;
  31.   typedef T&                         reference;
  32. };
  33. // random access iterator的属性
  34. template <class T, class Distance> struct random_access_iterator {
  35.   typedef random_access_iterator_tag iterator_category;
  36.   typedef T                          value_type;
  37.   typedef Distance                   difference_type;
  38.   typedef T*                         pointer;
  39.   typedef T&                         reference;
  40. };

  通过iterator_traits就能得到相应interator的各种特性，这样可以让程序更灵活，也能提高效率。
下面几个例子是为了说明iterator_traits在STL中的使用
eg1. count模板函数，它的返回值必须使用difference_type

  1. template <class InputIterator, class T>
  2. typename iterator_traits<InputIterator>::difference_type
  3. count(InputIterator first, InputIterator last, const T& value) {
  4.   typename iterator_traits<InputIterator>::difference_type n = 0;   // 萃取迭代器的difference_type类型
  5.   for ( ; first != last; ++first)
  6.     if (*first == value)
  7.       ++n;
  8.   return n;
  9. }

eg2. advance模板函数，为了提高效率，必须针对不同类型的iterator重载不同的处理函数

  1. template <class InputIterator, class Distance>
  2. inline void advance(InputIterator& i, Distance n) {
  3.   __advance(i, n, iterator_category(i));    // 根据不同的类型调用不同的重载函数
  4. }
  6. // iterator_category函数的定义
  7. template <class Iterator>
  8. inline typename iterator_traits<Iterator>::iterator_category
  9. iterator_category(const Iterator&) {
  10.   typedef typename iterator_traits<Iterator>::iterator_category category;   // 其实就是返回Iterator的iterator_category类型
  11.   return category();
  12. }

  再看__advance函数针对不同迭代器的三种版本，它们分别针对input iterator、forward iterator、Bidirectional iterator和Random access iterator四种不同的迭代器

  1. // 针对input iterator和forward iterator的版本
  2. template <class InputIterator, class Distance>
  3. inline void __advance(InputIterator& i, Distance n, input_iterator_tag) {
  4.   while (n--) ++i;  // 只能单向移动
  5. }
  6. // 针对Bidirectional iterator的版本
  7. template <class BidirectionalIterator, class Distance>
  8. inline void __advance(BidirectionalIterator& i, Distance n, 
  9.                       bidirectional_iterator_tag) {
  10.   if (n >= 0)           // 根据方向不同有不同的处理
  11.     while (n--) ++i;
  12.   else
  13.     while (n++) --i;
  14. }
  15. // 针对Random access iterator的版本
  16. template <class RandomAccessIterator, class Distance>
  17. inline void __advance(RandomAccessIterator& i, Distance n, 
  18.                       random_access_iterator_tag) {
  19.   i += n;   // 随机访问，提高效率
  20. }

  总的来说，在STL中是由容器（container）来负责设计适当的迭代器（iterator），由迭代器（iterator）来负责设计适当的迭代器 属性。正因为这一点才使得容器和算法可以完全分离开来，通过迭代器提供的接口来访问容器的内部元素。在这里我们又一次看到了traits编程技巧的强大功 能，在很大程度上弥补了C++语言不是强类型语言的不足之处。


posted on 2011-01-14 15:56 Mr.wang 阅读(697) 评论(0)  编辑 收藏 引用 所属分类: C++

<2011年1月>
日一二三四五六
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜