《STL源碼剖析》——疊代器（iterators）概念與traits程式設計技法（一）

一、疊代器設計思維——STL關鍵所在

        STL的中心思想在于：将資料容器（containers）和算法（algorithms）分開，彼此獨立設計，最後再以一帖粘合劑将它們撮合在一起。

二、疊代器（iterator）是一種 smart pointer

        疊代器是一種行為類似指針的對象，而指針的各種行為中最常見也最重要的便是内容提領（dereference）和成員通路（member access），是以，疊代器最重要的程式設計工作就是對 operator* 和 operator-> 進行重載（overloading）工作。

        每一種STL容器都提供有專屬疊代器的緣故。

三、Traits程式設計技法——STL源代碼門鑰

        若要 traits 能夠有效運作，每一個疊代器必須遵循約定，自行以内嵌型别定義（nested typedef）的方式定義出相應型别（associated types）。根據經驗，最常用到的疊代器相應型别有五類：value type，difference type，pointer，reference，iterator catagoly。

// "榨汁機"traits
template <class 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;
};
           

        1. 疊代器相應型别之一：value type

        value type，是指疊代器所指對象的型别。任何一個打算與STL算法有完美搭配的 class，都應該定義自己的value type内嵌型别。

        2. 疊代器相應型别之二：difference type

        difference type 用來表示兩個疊代器之間的距離。針對相應型别 difference type，traits 的如下兩個（針對原生指針而寫的）特化版本，以C++内建的ptrdiff_t（定義于<cstddef>頭檔案）作為原生指針的difference type：

template<class Iterator>
struct iterator_traits {
    ...
    typedef typename Iterator::difference_type   difference_type;
};

// 針對原生指針而設計的“偏特化（partial  specialization）”版
template <class T>
struct iterator_traits<T *> {
    ...
    typedef ptrdiff_t    difference_type;
};

// 針對原生的 pointer-to-const 而設計的“偏特化（partial specialization）”版
template <class T>
struct iterator_traits<const T*> {
    ...
    typedef ptrdiff_t  difference_type;
};
           

        3. 疊代器相應型别之三：reference type

        4. 疊代器相應型别之四：pointer type

template<class Iterator>
struct iterator_traits {
    ...
    typedef typename Iterator::pointer pointer;
    typedef typename Iterator::reference  reference;
};

// 針對原生指針而設計的“偏特化（partial  specialization）”版
template <class T>
struct iterator_traits<T *> {
    ...
    typedef T*  pointer;
    typedef T&  reference;
};

// 針對原生的 pointer-to-const 而設計的“偏特化（partial specialization）”版
template <class T>
struct iterator_traits<const T*> {
    ...
    typedef const T*  pointer;
    typedef const T&  reference;
};
           

        5. 疊代器相應型别之五：iterator_category

        根據移動特性與施行操作，疊代器被分為五類：

                a. Input Iterator：這種疊代器所指的對象，不允許外界改變。隻讀（read only）。

                b. Output Iterator：唯寫（write only）。

                c. Forward Iterator：允許“寫入型”算法在此種疊代器所形成的區間上進行讀寫操作。

                d. Bidirectional Iterator：可雙向移動。某些算法需要逆向走訪某個疊代器區間，可以使用 Bidirectional Iterator。

                e. Random Access Iterator：前四種疊代器都隻供應一部分指針算術能力（前三種支援 operator++，第四種在加上 operator--），第五種則涵蓋所有指針算術能力，包括 p+n, p-n, p[n], p1 - p2, p1 < p2。

四、std::iterator 的保證

        為了符合規範，任何疊代器都應該提供五個内嵌相應型别，以利于 traits 萃取，否則便是自别于整個STL架構，可能無法與其它 STL 元件順利搭配。STL 提供了一個 iterators class 如下，如果每個新設計的疊代器都繼承自它，就可保證符合 STL 所需之規則：

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

        由于後三個參數皆有預設值，故新的疊代器隻需提供前兩個參數即可。