C++實現STL迭代器萃取的範例程式碼

2022-12-01 14:04:04

導言

什麼是迭代器

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

為什麼需要迭代器萃取

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

如果我們想要以迭代器所指之物型別為型別宣告一個變數，該怎麼辦呢？

一種解決方法是：利用 function template 的引數推倒（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 用於函數返回值的情況，畢竟推導的只是引數，無法推導返回值型別。

宣告內嵌型別似乎是個很好的方法，像這樣：

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 是一個模板引數，在它被具現化之前編譯器對它一無所知，也就是說編譯器不知道 I::valie_type 是個型別或是成員函數等等。

更多關於 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 用來表示兩個迭代器之間的距離。對於連續空間的容器來說，頭尾之間的距離就是最大容量，因此它也可以用來表示一個容器的最大容量。

如果一個泛型演演算法提供記數功能，例如 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++ 中，函數如果要傳回左值，都是以參照的方式進行。所以當 p 是個 mutable iterators 時，如果其 value type 是 T，那麼 *p 的型別不應該是 T，而應是 T&。同樣的，如果 p 是一個 constant iterators，其 value type 是 T，那麼 *p 的型別不應該是 const T，而應該是 const T&。實現將在下一部分給出。

point type

同樣的問題也出現在指標這裡，能否改變所指地址的內容，影響著取出的指標型別。

實現如下：

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

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

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

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

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

以 distance() 為例

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

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 命名規則：所能接受的最低階迭代器型別
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.

在模板宣告的模板參數列中，typename 可以用來替換 class 宣告模板引數型別

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

在模板的宣告或定義中，typename 可以用來宣告從屬名稱是一種型別

宣告模板引數型別

以下 tempalate 宣告式中，class 和 typename 用什麼不同？

template <class T>
class Qgw;

template <typename T>
class Qgw;

答案：完全一樣。標準中說 typename 可以用來替換 class 宣告模板引數型別，並沒有說在此時有什麼不同。

宣告巢狀從屬名稱

在瞭解這個作用前，我們需要先學習兩種名稱，從屬名稱（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 引數 C。template 內出現的名稱如果依賴於某個 template 引數稱之從屬名稱。如果從屬名稱在 class 內呈巢狀狀，就稱為巢狀從屬名稱，像 iter 的型別為 C::iterator，就是一個巢狀從屬名稱。

巢狀狀的理解：C 是一個 template 引數，在它被編譯器具現化之前，編譯器並不知道它是什麼，也就無從得知 C 裡面的 iterator 究竟是個型別還是函數又或是其他東西，因此需要我們用 typename 來指出它是一個型別。

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

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

上述程式碼我們宣告了一個區域性變數 x，它是個指標，指向一個 C::iterator。但它之所以被這麼認為，是因為我們已經知道 C::iterator 是個型別。如果 C::iterator 不是個型別呢？如果 C 有個 static 成員變數而又剛好叫 iterator，或者 x 是個全域性變數呢？那樣的話上述程式碼不再是宣告一個區域性變數，而是一個相乘動作。

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

我們可以用 typename 來明確指出巢狀從屬名稱是一個型別，標準中寫到 typename 可以用來宣告從屬名稱是一種型別。於是我們可以這樣修改程式碼：

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

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

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

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

例外

typename 不可以出現在 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++實現STL迭代器萃取的範例程式碼的文章就介紹到這了,更多相關C++ STL迭代器萃取內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com