導(dǎo)言

什么是迭代器

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

為什么需要迭代器萃取

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

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

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

例如：

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);
}

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

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

聲明內(nèi)嵌類型似乎是個(gè)很好的方法，像這樣：

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 的作用是告訴編譯器這是一個(gè)類型，因?yàn)?I 是一個(gè)模板參數(shù)，在它被具現(xiàn)化之前編譯器對(duì)它一無(wú)所知，也就是說(shuō)編譯器不知道 I::valie_type 是個(gè)類型或是成員函數(shù)等等。

更多關(guān)于 typename 的用法可以查看文末補(bǔ)充內(nèi)容

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

例如：

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;
};

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

迭代器萃取，就是為我們榨取出迭代器的相應(yīng)型別。當(dāng)然，要使萃取有效的運(yùn)行，每個(gè)迭代器都要自行以內(nèi)嵌性別定義（nested typedef）的方式定義出相應(yīng)型別。

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

迭代萃取機(jī) traits 會(huì)很忠實(shí)地將它們榨取出來(lái)：

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 必須針對(duì)傳入型別為 point 及 point-to-const 者，設(shè)計(jì)特化版本。

value type

value type 是指迭代器所指對(duì)象的型別。

做法如上文所述。

difference type

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

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

template<class I, class T>
typename iterator_traits<I>::difference_type        // 返回值類型，實(shí)際是 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;
}

針對(duì)相應(yīng)型別 difference type，traits 的兩個(gè)特化版本，以 C++ 內(nèi)建的 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

從迭代器所指之物的內(nèi)容是否允許改變的角度來(lái)說(shuō)，迭代器分為兩種：不允許改變所指對(duì)象的內(nèi)容者，稱為 constant iterators；允許改變所指對(duì)象的內(nèi)容者，稱為 mutable iterators。當(dāng)我們對(duì)允許改變內(nèi)容的迭代器進(jìn)行解引用操作時(shí)，獲得的不應(yīng)是一個(gè)右值，應(yīng)該是一個(gè)左值，因?yàn)橛抑挡辉试S賦值操作。

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

point type

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

實(shí)現(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ù)移動(dòng)特性與施行操作，迭代器被分為五類：

前三種支持 operator++，第四種再加上 oprerator--，最后一種則涵蓋所有指針?biāo)阈g(shù)能力。

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

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

以 distance() 為例

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

template <class InputIterator>
inline iterator_traits<InputIterator>::difference_type
    __distance(InputIterator first, InputIterator last,
              input_iterator_tag) {
	iterator_traits<InputIterator>::iteratordifference_type n = 0;
    // 逐一累計(jì)距離
    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) {
    // 直接計(jì)算差距
    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());
}

知識(shí)點(diǎn)補(bǔ)充

typename 的用法

Usage

typename 主要有兩個(gè)作用，讓我們先來(lái)看看標(biāo)準(zhǔn)手冊(cè)對(duì)該關(guān)鍵字的說(shuō)明。

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 可以用來(lái)替換 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 可以用來(lái)聲明從屬名稱是一種類型

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

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

template <class T>
class Qgw;

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

答案：完全一樣。標(biāo)準(zhǔn)中說(shuō) typename 可以用來(lái)替換 class 聲明模板參數(shù)類型，并沒(méi)有說(shuō)在此時(shí)有什么不同。

聲明嵌套從屬名稱

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

讓我們來(lái)看這樣一段代碼，代碼本身并沒(méi)有實(shí)際意義。

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

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

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

嵌套從屬名稱有可能導(dǎo)致解析困難，先來(lái)看個(gè)比較極端的例子：

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

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

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

我們可以用 typename 來(lái)明確指出嵌套從屬名稱是一個(gè)類型，標(biāo)準(zhǔn)中寫到 typename 可以用來(lái)聲明從屬名稱是一種類型。于是我們可以這樣修改代碼：

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

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

typename 只能被用來(lái)驗(yàn)明嵌套從屬名稱，其他名稱不該有它存在。

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

例外

typename 不可以出現(xiàn)在 base classes list 內(nèi)嵌套從屬名稱之前，也不可以在 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
    }
}

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

最新評(píng)論