迭代器最重要的编程工作就是对operator*和operator->进行重载(overloading)工作。

迭代器的分类

迭代器（iterator） - 图1为了保证性能，针对于不同的情况应该使用不同的迭代器。

Example1

header: 

  1. template<class InputIt, class Distance>
  2. void advance(InputIt&, Distance n);
  4. template<class InputIt, class Distance>
  5. constexpr void advance(InputIt& it, Distance n);

该函数旨在对给予的迭代器 迭代n次，如果n为负，则进行递减。

现在为了保证advance的效率，有如下三种迭代器，应该选择哪种作为advance的迭代器呢？

  1. template<class InputIterator, class Distance>
  2. void advance_II(InputIterator& i, Distance n)
  3. {
  4.     while(n--) ++i;
  5. }
  7. template<class BidirectionalIterator, class Distance>
  8. void advance_BI(BidirectionalIterator& i, Distance n)
  9. {
  10.     if(n >= 0)
  11.         while(n--) ++i;
  12.     else
  13.         while(n++) --i;
  14. }
  16. template<class RandomAccessIterator, class Distance>
  17. void advance_RAI(RandomAccessIterator& i, Distance n)
  18. {
  19.     i += n; //双向，跳跃前进
  20. }

advance_II 效率太低，对于Random Access Iterator而言缺乏效率，使得原本应该为O(1)的时间负责度，变成了O（n）的时间复杂度。

Example2

distance()是常用的迭代器操作函数，用来计算两个迭代器之间的距离。设计模式和advance（）一样。