導言

什么是迭代器

迭代器是一種抽象的設計概念，《Design Patterns》一書中對于 iterator 模式的定義如下：提供一種方法，使之能夠依序巡訪某個聚合物（容器）所含的各個元素，而又無需暴露該聚合物的內部表述方式。

為什么需要迭代器萃取

有時在我們使用迭代器的時候，很可能會用到其相應型別（associated type）。什么是相應型別，迭代器所指之物的型別、所屬的類型（隨機迭代器、單向雙向、只讀只寫）便是。

如果我們想要以迭代器所指之物型別為類型聲明一個變量，該怎么辦呢？

一種解決方法是：利用 function template 的參數(shù)推倒（argument deducation）機制。

例如：

template <class I, class T>
void func(I iter, T t) {
	T tmp;	// 成功聲明了迭代器所指之物類型的變量
}

template <class I>
void func(I iter) {
	func_impl(iter, *iter);
}

int main() {
	int num = 0;
    func(&num);
}

但迭代器的型別不只是迭代器所指對象的型別，而且上述解法并不能用于所有情況，因此需要更加全面的解法。

比如上述解法就無法解決 value type 用于函數(shù)返回值的情況，畢竟推導的只是參數(shù)，無法推導返回值型別。

聲明內嵌類型似乎是個很好的方法，像這樣：

template <class T>
struct MyIter {
	typedef T value_type;
    T* ptr;
    
    MyIter(T* p) {
        ptr = p;
    }
    T& operator*() { 
        return *ptr; 
    }
};

template <class I>
typename I::valie_type func (I ite) {	// typename I::valie_type 為返回值類型
	return *ite;
}

MyIter<int> ite(new int(1231));
cout << func(ite) << endl;

此處 typename 的作用是告訴編譯器這是一個類型，因為 I 是一個模板參數(shù)，在它被具現(xiàn)化之前編譯器對它一無所知，也就是說編譯器不知道 I::valie_type 是個類型或是成員函數(shù)等等。

更多關于 typename 的用法可以查看文末補充內容

還有一種情況是上述代碼無法解決的，那就是不是所有的迭代器都是 class type，原生指針就不是。如果不是 class type 就無法為它定義內嵌型別，因此我們需要對原生指針作些特殊處理。

例如：

template <class I>
struct iterator_traits {
    typedef typename I::value_type value_type;
};
template <class T>
struct iterator_traits<T*> {
    typedef T value_type;
};
template <class T>
struct iterator_traits<const T*> {
    typedef T value_type;
};

此時，不管是 class type 類型的迭代器還是原生指針都可以處理了。

迭代器萃取，就是為我們榨取出迭代器的相應型別。當然，要使萃取有效的運行，每個迭代器都要自行以內嵌性別定義（nested typedef）的方式定義出相應型別。

最常用的迭代器型別有五種：value type，difference type，pointer，reference，iterator catagoly。

迭代萃取機 traits 會很忠實地將它們榨取出來：

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

iterator_traits 必須針對傳入型別為 point 及 point-to-const 者，設計特化版本。

value type

value type 是指迭代器所指對象的型別。

做法如上文所述。

difference type

difference type 用來表示兩個迭代器之間的距離。對于連續(xù)空間的容器來說，頭尾之間的距離就是最大容量，因此它也可以用來表示一個容器的最大容量。

如果一個泛型算法提供記數(shù)功能，例如 STL 的 count()，其返回值就必須使用迭代器的 difference type：

template<class I, class T>
typename iterator_traits<I>::difference_type        // 返回值類型，實際是 I::difference type
    count(I first, I last, const T& value) {
    typename iterator_traits<I>::difference_type ret = 0;
    for (; first != last; ++first) {
        if (*first == value) {
            ret++;
        }
    }
    return ret;
}

針對相應型別 difference type，traits 的兩個特化版本，以 C++ 內建的 ptrdiff_t 作為原生指針的 difference type。

template <class I>
struct iterator_traits {
    typedef typename I::difference_type difference_type;
};
template <class T>
struct iterator_traits<T*> {
    typedef ptrdiff_t difference_type;
};
template <class T>
struct iterator_traits<const T*> {
    typedef ptrdiff_t difference_type;
};

reference type

從迭代器所指之物的內容是否允許改變的角度來說，迭代器分為兩種：不允許改變所指對象的內容者，稱為 constant iterators；允許改變所指對象的內容者，稱為 mutable iterators。當我們對允許改變內容的迭代器進行解引用操作時，獲得的不應是一個右值，應該是一個左值，因為右值不允許賦值操作。

在 C++ 中，函數(shù)如果要傳回左值，都是以引用的方式進行。所以當 p 是個 mutable iterators 時，如果其 value type 是 T，那么 *p 的型別不應該是 T，而應是 T&。同樣的，如果 p 是一個 constant iterators，其 value type 是 T，那么 *p 的型別不應該是 const T，而應該是 const T&。實現(xiàn)將在下一部分給出。

point type

同樣的問題也出現(xiàn)在指針這里，能否改變所指地址的內容，影響著取出的指針類型。

實現(xiàn)如下：

template <class I>
struct iterator_traits {
    typedef typename I::pointer     pointer;
    typedef typename I::reference    reference;
};
template <class T>
struct iterstor_traits<T*> {
    typedef T*     pointer;
    typedef T&     reference;
};
template <class T>
struct iterstor_traits<const T*> {
    typedef const T*    pointer;
    typedef const T&     reference;
};

iterator_category

根據(jù)移動特性與施行操作，迭代器被分為五類：

前三種支持 operator++，第四種再加上 oprerator--，最后一種則涵蓋所有指針算術能力。

這些迭代器的分類與從屬關系，可以用下圖表示。直線與箭頭并非表示繼承關系，而是所謂概念與強化的關系。更類似于，隨機迭代器是一個雙向迭代器，雙向迭代器也是一個單向迭代器的概念。

設計一個算法時，要盡可能針對圖中某種迭代器提供一個明確定義，并針對更加強化的某種迭代器提供另一種定義，這樣才能在不同情況下提供最大效率。

以 distance() 為例

distance() 函數(shù)用來計算兩個迭代器之間的距離。針對不同的迭代器類型，它可以用不同的計算方式，帶來不同的效率。

template <class InputIterator>
inline iterator_traits<InputIterator>::difference_type
    __distance(InputIterator first, InputIterator last,
              input_iterator_tag) {
	iterator_traits<InputIterator>::iteratordifference_type n = 0;
    // 逐一累計距離
    while (first != last) {
		++first;
        ++n;
    }
    return n;
}

template <class RandomAccessIterator>
inline iterator_traits<RandomAccessIterator>::difference_type
    __distance(RandomAccessIterator first, RandomAccessIterator last,
               random_access_iterator_tag) {
    // 直接計算差距
    return last - first;
}

// InputIterator 命名規(guī)則：所能接受的最低階迭代器類型
template <class InputIterator>
inline iterator_traits<InputIterator>::difference_type
    distance(InputIterator first, InputIterator last) {
	typedef typename iterator_traits<InputIterator>::iterator_category category;
    return __distance(first, last, category());
}

知識點補充

typename 的用法

Usage

typename 主要有兩個作用，讓我們先來看看標準手冊對該關鍵字的說明。

In the template parameter list of a template declaration, typename can be used as an alternative to class to declare type template parameters.

在模板聲明的模板參數(shù)列表中，typename 可以用來替換 class 聲明模板參數(shù)類型

Inside a declaration or a definition of a template, typename can be used to declare that a dependent qualified name is a type.

在模板的聲明或定義中，typename 可以用來聲明從屬名稱是一種類型

聲明模板參數(shù)類型

以下 tempalate 聲明式中，class 和 typename 用什么不同？

template <class T>
class Qgw;

???????template <typename T>
class Qgw;

答案：完全一樣。標準中說 typename 可以用來替換 class 聲明模板參數(shù)類型，并沒有說在此時有什么不同。

聲明嵌套從屬名稱

在了解這個作用前，我們需要先學習兩種名稱，從屬名稱（dependent names）和嵌套從屬名稱（nested dependent name）。

讓我們來看這樣一段代碼，代碼本身并沒有實際意義。

// C 接收一個 STL 容器類型
// 這份代碼并不正確
template <class C>
void Test(C& container) {
    C w;
    C::iterator iter(container.begin());
}

在上述代碼中有兩個局部變量 w 和 iter。w 的類型是 C，實際是什么取決于 template 參數(shù) C。template 內出現(xiàn)的名稱如果依賴于某個 template 參數(shù)稱之從屬名稱。如果從屬名稱在 class 內呈嵌套狀，就稱為嵌套從屬名稱，像 iter 的類型為 C::iterator，就是一個嵌套從屬名稱。

嵌套狀的理解：C 是一個 template 參數(shù)，在它被編譯器具現(xiàn)化之前，編譯器并不知道它是什么，也就無從得知 C 里面的 iterator 究竟是個類型還是函數(shù)又或是其他東西，因此需要我們用 typename 來指出它是一個類型。

嵌套從屬名稱有可能導致解析困難，先來看個比較極端的例子：

template <class C>
void Test(C& container) {
    C::iterator* x;
    ...
}

上述代碼我們聲明了一個局部變量 x，它是個指針，指向一個 C::iterator。但它之所以被這么認為，是因為我們已經(jīng)知道 C::iterator 是個類型。如果 C::iterator 不是個類型呢？如果 C 有個 static 成員變量而又剛好叫 iterator，或者 x 是個全局變量呢？那樣的話上述代碼不再是聲明一個局部變量，而是一個相乘動作。

在我們知道 C 是什么之前，沒有任何辦法可以知道 C::iterator 是否是一個類型。C++ 有個規(guī)則可以解析這一歧義狀態(tài)：如果解析器在 template 中遇到一個嵌套從屬名稱，它便假設這名稱不是一個類型，除非你明確指出它是一個類型。所以缺省情況下嵌套從屬名稱不是類型，有兩個例外會在下面指出。

我們可以用 typename 來明確指出嵌套從屬名稱是一個類型，標準中寫到 typename 可以用來聲明從屬名稱是一種類型。于是我們可以這樣修改代碼：

template <class C>
void Test(C& container) {
    C w;
    typename C::iterator iter(container.begin());
    typename C::iterator* x;
}

一個簡單的規(guī)則：任何時候當你想在 template 中指涉一個嵌套從屬名稱，就必須在它的前一個位置放上關鍵字 typename。

typename 只能被用來驗明嵌套從屬名稱，其他名稱不該有它存在。

template <class C>
void Test(const C& container,             // 不允許使用 typename，vs 下沒報錯，g++ 報錯了
          typename C::iterator iter);    // 一定要使用 typename

例外

typename 不可以出現(xiàn)在 base classes list 內嵌套從屬名稱之前，也不可以在 member initialization list（成員初始化列表）中作為 base class 修飾符。例如：

temalate <class T>
class Derived : public Base<T>::Nested {// base classes list 中不允許 typename
public:
    Derived (int x)
        : Base<T>::Nested(x) {            // mem.init.list 中不允許 typename
        typename Base<T>::Nested temp;    // 既不在 base classes list 也不在 mem.init.list 需要加 typename
    }
}

到此這篇關于C++實現(xiàn)STL迭代器萃取的示例代碼的文章就介紹到這了,更多相關C++ STL迭代器萃取內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家