STL中迭代器的实现
junguo

    
       最近在看候捷先生的《STL源码剖析》，侯先生写的挺好的。但我读起来总感觉有些拗，理解起来有些费劲，可能他看问题的观点和我不一样造成的。开始的时候总是不太理解，后来理顺了自己的思路，发现有些东西其实并不难。在此把我对迭代器的理解整理一下，也是帮助自己消化一下，因为我发现不动手，很多东西容易遗忘。
      文章里提供的一些例子程序是在Dev-C++ 4.9.9.0中编译的，该版编译器使用的是GNU C++ 3.3.1版本的类库，该代码在其它版本上以及其它编译器中可能无法通过。3.3.1版本中的STL改进了一些内容，例如安全检查一类的东西，虽说使用上更保险。但也增加了理解的困难，所以我在源代码的摘取上参考了侯先生网站上提供的sgi-stl-2.91.57版本的内容，GUN的3.3.1其实也是在sgi-stl版本的基础上改进的。源代码可以在Dev-C++的安装目录的include/c++/3.3.1下找到，多是以stl_开头的（如list的实现文件是stl_list.h）。
        STL中为我们提供的最重要的两个内容是容器（vector，list等）和一系列的算法。在这些算法中有许多需要遍历容器中的所有元素，如search，sort等算法。STL的设计者希望将算法和容器分离开来，一个算法可以帮不同的容器实现功能。为此目的，STL应用到了《设计模式》中提到的迭代器模式。
    《设计模式》中将迭代器模式定义为：提供一种方法，使之能依序遍历容器中的每个元素，而不需要暴露容器内部的信息。在面向对象的设计里，实现迭代器，我们会为所有的迭代器提供一个统一的接口，然后更个容器的迭代器继承这个接口，然后在使用处通过接口来实现对不同迭代器的调用。但STL是采用泛型思维，利用摸版来实现的类库，所以它的迭代器的实现和面向对象稍有不同，但原理类似。在此将通过例子来具体看看STL中迭代器的实现。
    我们先来看看find()函数的实现：

 

    //摘自stl_algo.h
    template<typename _InputIter, typename _Tp>
    inline _InputIter
    find(_InputIter __first, _InputIter __last,
  const _Tp& __val,
  input_iterator_tag)
    {
      while (__first != __last && !(*__first == __val))
 ++__first;
      return __first;
    }

    find()函数的功能是在一个容器中查找一个元素，需要遍历两个迭代器对象_first和_last所在的区间。在此我们看到它对区间的遍历是通过++__first来实现的。也就是说迭代器需要重载++运算符来实现对容器的遍历。来具体看看vector和list中的迭代器实现。
    我们知道vector中的元素是连续存放的，类似于数组，在数组中可以通过指针很容易的实现对数组的遍历，在vector中也一样，并不需要提供给它专门的迭代器类，通过指针就可以实现迭代器的功能。看看例子：

#include<iostream>
#include<vector>
using namespace std;

template<typename _InputIter, typename _Tp>
inline _InputIter
myfind(_InputIter __first, _InputIter __last,
  const _Tp& __val)
{
  while (__first != __last && !(*__first == __val))
 ++__first;
  return __first;
}

int main()
{
    vector<int> vec;

 for( int i = 0; i < 10 ; i ++ )
  vec.push_back(i);

 int *p0 = &vec[0];
 int *p1 = &vec[10];
 
 int *p2 = myfind(p0,p1,6);

 if ( p2 != &vec[10])
  cout << *p2 << endl;
  
 system("pause");
    return 0;
}   

    例子中，我对find做了改动，改成了myfind，这是因为3.3.1的源代码中加入了traits技巧（在VC中我们是可以直接用find的），稍后我们将讲到该问题。但这里可以看到，通过指针就可以实现对vector的遍历。一般我们对迭代器的使用是如下的方式：
   vector<int>::iterator it;
   这里需要借助vector来定义迭代器，这里主要是为容器的使用提供一种统一的方式。因为list容器不能通过指针来实现遍历，它们需要实现自己的迭代器。我们来看看在vector中对于iterator的实现：

 template<typename T,class Alloc = alloc >
    class vector
    { 
 public:
      typedef T    value_type;
      typedef value_type*  iterator;
     
   ...
 };
 在此可以看到iterator在vector中也只是简单的被定义成了我们传入的类型参数T的指针（在3.3.1的代码中与这里的代码并不一样，还是traits的原因）。我们使用迭代器的一般方式是如下：
     find(vec.begin(),vec.end,6);
     再简单看看begin和end函数的实现：
template<typename T,class Alloc = alloc >
  class vector
    { 
proteted:
  iterator start;
  iterator finist;
 public:
      iterator begin(){return start;}
        iterator end(){return end;}
   ...
 };
    这里可以看到，只是为vector设置一个头指针和尾指针，然后通过begin和end来得到这两个指针。
 list就不可以直接通过指针来实现迭代器了，因为它里面的元素是不连续的。需要我们自己去实现，我们先把list的定义抽出来看看。
template <class _Tp >
struct _List_node {
  _List_node< _Tp>* _M_next; 
  _List_node< _Tp>* _M_prev;
  _Tp _M_data;
};
template <class _Tp, class Alloc = alloc>
class list {
protected:
  _List_nod<_Tp>e* node;
  ....
public:
  void push_front(const _Tp & x);
  void push_back(const _Tp & x);
  ....
};
   为了便于理解，我将代码进行了简单的修改，事实上3.3.1里的代码要比这个要复杂一些。一般来说设计一个链表，我们会把它分成两部分：_List_node用来存放数据，list用来操作链表。这样，迭代器实际传回的应该是_List_node，当它向前遍历的时候，传回的应该是它的下一个结点。按着这个结构，为链表来设计一个迭代器，如下：
template<class T>
struct __list_iterator {
   _List_node<T>* node;
  __list_iterator(_List_node<T>* x) : node(x) {}
  __list_iterator() {}

  bool operator==(const __list_iterator<T>& x) const { return node == x.node; }
  bool operator!=(const __list_iterator<T>& x) const { return node != x.node; }

  T& operator*() const { return (*node)._M_data; }
 
  __list_iterator<T>& operator++() {
    node = (_List_node<T>*)((*node)._M_next);   
    return *this;
  }
 
  __list_iterator<T> operator++(int) {
    __list_iterator<T> tmp = *this;
    ++*this;
    return tmp;
  }
 
};
      我们可以看到，迭代器中重载了==，！=，*，++等操作符，这是因为这些操作是在算法中经常要用到的操作符。看看myfind中实现，就可以明白：
while (__first != __last && !(*__first == __val))
 ++__first;
      这里要用到两个迭代器的比较（__first != __last），所以我们需要重载等于运算符；迭代器中值的比较（*__first == __val），这时候比较的不再是迭代器，而是迭代器所包含的内容（这里是_List_node的对象），所以我们需要重载*来得到它；最重要的就是遍历的实现，需要重载++运算符，这里是通过node = (_List_node<T>*)((*node)._M_next);将迭代器中的_List_node对象改为它的下一个对象来实现的。这样我们就完成了迭代器的设计。再来看看它的用法：
int main(int argc, char *argv[])
{
  list<int> mylist;
 
  for(int i = 0;i <= 10; i++ )
  {
      mylist.push_back(i);
  }
  // mylist.begin()得到的是STL本身提供的迭代器，所以我们需要得到它所包含的_List_node<T>对象指针。
  _List_node<int>* p1 = (_List_node<int>*)mylist.begin()._M_node;
  _List_node<int>* p2 = (_List_node<int>*)mylist.end()._M_node;
 
 //这里用我们得到的指针来生成我们自己的迭代器
  __list_iterator<int> it1(p1);
  __list_iterator<int> it2(p2);
 
  __list_iterator<int>  it3 = myfind(it1,it2,6);

 if ( it3 != it2 )
  cout << *it3 << endl;

  system("PAUSE"); 
  return 0;
}
        实际的迭代器的设计中，还会重载--和->运算符，感兴趣的可以自己看看源代码。还是和vector一样，STL会把迭代器的定义绑定到list类中去，我们来看看它的具体做法：
typedef _list_iterator<_Tp>                 iterator;
其实和vector一样，只要把以上的定义放到list类中，就可以了，然后，我们就可以通过list<int>::iterator ite 来定义list的迭代器了，事实上它生成的就是一个_list_iterator<int>对象。
从此可以看到迭代器就是为各个容器生成一个可以迭代自身的类，而再通过typedef来把该迭代类绑定到容器类中，这样就给了外部一个形式统一的使用方法。
 除了遍历，迭代器中还用到了一个重要的技巧——traits。我们先来看看traits的用处。

template <class ForwardIterator1, class ForwardIterator2, class T>
inline void __iter_swap(ForwardIterator1 a, ForwardIterator2 b, T*) {
  T tmp = *a;
  *a = *b;
  *b = tmp;
}  
        该方法是用来实现两个迭代器中内容的交换，我们可以看到此处需要一个临时变量tmp，而tmp所对应的类型是它所包含的对象的类型。这样我们就需要传入一个类型参数T*进去，如果我们不想传这个参数进去可不可以呢？这时候就需要用到traits技巧了。事实上traits并没有什么太难理解的部分，还是看看例子：
template<class T>
struct __list_iterator {
  typedef T value_type;
  ….
};
      现在我们在__list_iterator头部加typedef T value_type;这么一句话，然后我们重新写一下迭代器的交换函数，如下：
template <class ForwardIterator1, class ForwardIterator2>
inline void myiter_swap(ForwardIterator1 a, ForwardIterator2 b) {
  typename ForwardIterator1::value_type tmp = *a;
  *a = *b;
  *b = tmp;
}
    此时，就可以通过typename ForwardIterator1::value_type来定义临时变量了，看看它的效果：
int main(int argc, char *argv[])
{
  list<int> mylist;
 
  for(int i = 0;i <= 10; i++ )
  {
      mylist.push_back(i);
  }
  _List_node<int>* p1 = (_List_node<int>*)mylist.begin()._M_node;
  _List_node<int>* p2 = (_List_node<int>*)mylist.end()._M_node;
 
  __list_iterator<int> it1(p1);
  __list_iterator<int> it2(p2);
 
  __list_iterator<int> it3(p2);
  //交换第一个和最后一个元素的内容
  myiter_swap(it1,--it3);
  //打印所有的元素
   for( ;it1 != it2;it1++)
  cout << *it1 << endl;
  system("PAUSE"); 
  return 0;
}
     事实上，在迭代器中还会包括指针，引用，还有就是两个迭代器之间距离的类型。所以迭代器的中的实际代码应该如下：
template<class T>
struct __list_iterator {
typedef bidirectional_iterator_tag iterator_category;  //迭代器的类型，稍后解释
typedef T value_type;    // 对象类型
typedef value_type*pointer;  // 指针类型
typedef value_type& reference;  // 引用类型
typedef ptrdiff_t difference_type; // 迭代器距离类型，关于这个参数，我也搞不明白为什么需要
…
};
        这样具体的算法中就可以根据这些内容来定义自己所需要的类型了（STL的实际定义中和这里有些不同，在容器类（vector,list）中已经定义了这些类型，迭代器是再通过容器类定义，不过原理是一致的）。另外，STL中还提供了一个自己的萃取机，如下：
  template<typename _Iterator>
    struct iterator_traits {
      typedef typename _Iterator::iterator_category iterator_category;
      typedef typename _Iterator::value_type        value_type;
      typedef typename _Iterator::difference_type   difference_type;
      typedef typename _Iterator::pointer           pointer;
      typedef typename _Iterator::reference         reference;
};
    有了它，我们的myinter_swap函数就可以变成以下的内容：
template <class ForwardIterator1, class ForwardIterator2>
inline void myiter_swap(ForwardIterator1 a, ForwardIterator2 b) {
  typedef typename iterator_traits<ForwardIterator1>::value_type _ValueType1;
  _ValueType1 tmp = *a;
  *a = *b;
  *b = tmp;
}  

       似乎这段代码并没有使代码变的方便？想想，我们的vector中并没有定义迭代器类，只是直接把指针当作了迭代器。如果直接用以上的代码明显是会出问题的，因为指针根本没有value_type这些信息。为了这种情况，STL中提供了萃取机中针对指针的偏特化版本：

  template<typename _Tp>
    struct iterator_traits<_Tp*> {
      typedef random_access_iterator_tag iterator_category;
      typedef _Tp                         value_type;
      typedef ptrdiff_t                   difference_type;
      typedef _Tp*                        pointer;
      typedef _Tp&                        reference;
};

        这样vector对象就可以使用myiter_swap了，不然肯定编译不过去。还有一些针对其它类型（如常量指针）的偏特化版本，可以自己看看源码。
       在以上的代码中，我们看到了typedef random_access_iterator_tag iterator_category;这样的语句。iterator_category代表的是迭代器的分类，迭代器分为五种类型：
1， Input Iterator 这种类型的迭代器不允许外界改变，是唯读的。
2， Output Iterator 是唯写的。
3， Forard Iterator 可以读写，但它只能向前移动。
4， Bidirectional Iterator 可以读写，可以前后移动。
5， Random Access Iterator 可以读写，前后移动，并且支持p+n型的操作，也就是说可以前后移动多位，而不是一个一个的移动。
     在STL中，它们被定义为如下的形式：
///  Marking input iterators.
  struct input_iterator_tag {};
  ///  Marking output iterators.
  struct output_iterator_tag {};
  /// Forward iterators support a superset of input iterator operations.
  struct forward_iterator_tag : public input_iterator_tag {};
  /// Bidirectional iterators support a superset of forward iterator operations.
  struct bidirectional_iterator_tag : public forward_iterator_tag {};
  /// Random-access iterators support a superset of bidirectional iterator operations.
  struct random_access_iterator_tag : public bidirectional_iterator_tag {};

        可以看到它们并没有实际的代码，只是作为一个标记来用的。具体作用的话，还是通过函数来看看。STL的算法中提供了这样一个函数distance，它的作用是求出两个迭代器之间的距离，为了统一，函数可能写成这样：
template<typename _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
__distance(_InputIterator __first, _InputIterator __last)
{
  typename iterator_traits<_InputIterator>::difference_type __n = 0;
  while (__first != __last) {
   ++__first; ++__n;
   }
    return __n;
 }
        这样的话，vector和list都可以使用这个函数，但这样一来，vector也需要遍历两个迭代器之间的所有内容了。但事实上，我们知道vector是连续的区间，完全可以通过两个迭代器之间的相减操作来完成这个计算。如果采用以上的操作，会降低它的效率。有什么办法来区分这两种操作呢？通过迭代器类型就可以完成，还是看看代码：
  template<typename _InputIterator>
    inline typename iterator_traits<_InputIterator>::difference_type
    __distance(_InputIterator __first, _InputIterator __last,
               input_iterator_tag)
    { 
      typename iterator_traits<_InputIterator>::difference_type __n = 0;
      while (__first != __last) {
        ++__first; ++__n;
      }
      return __n;
    }
 
  template<typename _RandomAccessIterator>
    inline typename iterator_traits<_RandomAccessIterator>::difference_type
    __distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
               random_access_iterator_tag)
    {
      return __last - __first;
    }
  template<typename _InputIterator>
    inline typename iterator_traits<_InputIterator>::difference_type
    distance(_InputIterator __first, _InputIterator __last)
    {
      typedef typename iterator_traits<_InputIterator>::iterator_category category;
      return __distance(__first, __last, category ());
    }

       可以看到，STL提供了__distance的两个重载函数：一个针对input_iterator_tag，使用的我们上面提到的遍历的方法；一个针对random_access_iterator_tag，采用的直接相减的方法。并提供了distance函数，在该函数里通过
typedef typename iterator_traits<_InputIterator>::iterator_category category;来得到迭代器的类型，并通过category ()生成一个对象传入到__distance中，经过C++的重载机制实现了不同类型的调用。
      迭代器是STL中的重要内容，掌握它能帮助你更好的读懂STL源码，希望这篇文章能对你有帮助。
    （写完这篇东西，时间已经不早了，错误来不及挑了。呵呵，不过有时间也不一定会检查，太懒了，这个懒字了得）

 参考书籍： 《STL源码解析》 侯捷著 华中科技大学出版社