迭代器是一種抽象的設計概念，現(xiàn)實程序語言中并沒有直接對應于這個概念的實物。
在設計模式中，迭代器模式是指：提供一種方法，使之能夠依序巡防某個聚合物(容器)所含的各個元素，而又無須暴露該聚合物的內部表述方式。

迭代器是STL的關鍵所在：將數據容器和算法分開，彼此獨立設計，最后再用橋梁將它們聯(lián)系在一起，這個橋梁就是迭代器。
比如泛型算法 find 的實現(xiàn)

template <typename InputIterator, typename T>
InputIterator find(InputIterator first, InputIterator last, const T& value)
{
    for (; first != last; ++first)
    {
        if (*first == value)
            return first;
    }

    return first;
}

我們不需要關心容器的具體類型，也不需要關心T的具體實現(xiàn)，就能夠對不同的容器進行查找操作。

迭代器榨汁機

template<typename I>
struct iterator_traits
{
    typedef typename I::iterator_category
    typedef typename I::value_type;
    typedef typename I::difference_type;
    typedef typename I::pointer;
    typedef typename I::reference;
}

template<typename Category, typename T, typename Distance = ptrdiff_t,
            typename Pointer = T*, typename Reference = T&>
struct iterator 
{
    typedef Category iterator_category;
    typedef T value_type;
    typedef Distance difference_type;
    typedef Pointer pointer;
    typedef Reference reference;
};

迭代器型別

• 迭代器型別之一：value_type
  value_type 是指對象的型別，每一個打算與STL算法完美搭配的class，都應該定義自己的value_type內嵌型別。

• 迭代器型別之二：difference_type
  difference_type用來表示2個迭代器的距離，因此它可以用來表示容器的最大容量。通常用于STL中泛型算法提供的計數功能，例如STL中的count()。

  template <typename I, typename T>
  typename iterator_traits<I>::difference_type count
  (I first, I last, count T& value)
  {
      typename iterator_traits<I>::difference_type n = 0;
      for (; first != last; first++)
        if (*first == value)
            ++n;
  
      return n;
  }
  

• 迭代器相應型別之三：reference_type
  迭代器所指之物的內容是否允許改變， 迭代器分為2類，

  • 不允許改變“所指對象之內容者”稱為constant iterators 例如 const int* pic。
  • 允許改變“所指對象之內容者” 稱為mutable iterators，例如int *pi。

• 迭代器相應型別之四：pointer type
  reference_type 表示迭代器所指之物，那么pointer type則表示迭代器所指之物的地址。

  // 針對原生指針而設計的"偏特化版"
  template <typename T>
  struct iterator_traits<T*> {
      ......
      typedef T* pointer;
      typedef T& reference;
  }
  
  // 針對原生的pointer-to-const而設計的"偏特化"
  template <typename T>
  struct iterator_traits<const T*> {
      ......
      typedef T* pointer;
      typedef T& reference;
  }
  

• 迭代器相應型別之五：Iterator_category
  根據移動特性與施行操作迭代器被分為5類：

  • Input Iterator：這種迭代器所指的對象，不允許外界改變，只讀。
  • Output Iterator：只寫。
  • Forward Iterator：允許寫入型算法在此種迭代器所形成的區(qū)間上進行讀寫操作。
  • Bidirectional Iterator：可雙向移動，某些算法需要逆向走訪某個區(qū)間。
  • Random Access Iterator：前4種迭代器只提供一部分指針算術能力，(前3種支持operator++，第4種支持operator--)，第5種則涵蓋所有指針算術能力。

  為什么需要區(qū)分這么多的迭代器種類？因為我們在設計算法時，應該針對某種強化的迭代器提供另一種定義，這樣才能提供最大的效率。

迭代器類型.jpg

任何一個迭代器，其類型應該落在 "該迭代器所隸屬的各種類型中，最強化的那個"，例如，int* 既是 RandomAccess Iterator，又是 Bidirectional Iterator，同時也是 Forward Iterator，而且也是 Input Iterator，那么其類型應該歸屬為RandomAccess iterator。

struct input_iterator_tag {  };
struct output_iterator_tag {  };
struct forward_iterator_tag : public input_iterator_tag 
{  };
struct bidirectional_iterator_tag : public forward_iterator_tag 
{  };
struct random_access_iterator_tag : public bidirectional_iterator_tag 
{  };

比如以 advanced() 為例，它的目的是使迭代器向前移動n步。

/* 適合Input Iterator */
template <typename InputIterator, typename Distance>
void advance_II(InputIterator& i, Distance n)
{
   while(n--)
     ++i;
}

/* 適合Bidirectional Iterator */
template <typename BidirectionalIterator, typename Distance>
void advance_BI(BidirectionalIterator& i, Distance n)
{
   if (n >= 0)
     while(n--)
       ++i; 
   else
     while(n++)
        --i;
}

 /* 適合Random Access Iterator */
template <typename RandomAccessIterator, typename Distance>
void advance_RAI(RandomAccessIterator& i, Distance n)
{
   i += n;
}

template <typename InputIterator, typename Distance>
void advance(InputIterator& i, Distance n)
{
    if (is_random_access_iterator(i))    // 有待實現(xiàn)。
        advanced_RAI(i, n);
    else if (is_bidirectional_iterator(i))    // 有待實現(xiàn)。
        advance_BI(i, n)
    ......
}

像在advanced中，通過判斷不同迭代器類型來調用不同的函數以達到最大的效率。
那怎么判斷出不同類型呢？
第一種方法是多態(tài)，但運行期才確定未免成本太高，同時胡亂繼承多態(tài)也是把問題復雜化。
第二種就是函數重載，我們可以事先標記不同迭代器類型，并將其作為第3個參數傳給advanced。

template <typename InputIterator, typename Distance>
inline void advance(InputIterator &iter, Distance n)
{
    typedef typename iterator_traits<InputIterator>::iterator_category category;
    __advance(iter, n, category());
}

template <typename RandomAccessIterator, typename Distance>
void __advance(RandomAccessIterator iter, Distance n, random_access_iterator_tag)
{
    iter += n;
}

template <typename InputIterator, typename Distance>
void __advance(InputIterator iter, Distance n, input_iterator_tag)
{
    while(n--)
        iter++;
}

template <typename BidirectionalIterator, typename Distance>
void __advance(BidirectionalIterator iter, Distance n, bidirectional_iterator_tag)
{
    if (n >= 0)
        while(n--)
            iter++;
    else
        while(n++)
            iter--;
}

__advanced中的第三個參數僅僅是激活重載。但我們還需要一個提供上層統(tǒng)一的接口，在這一層中通過traits機制，將迭代器類型推導出來。

參考資料
[1]《STL源碼剖析》侯捷