摘要訊息 : 樣板超編程中的 traits 技巧.

目錄 隱藏
0. 前言
1. 疊代器和函式多載
2. std::iterator_traits
3. 將 traits 用在類別特製化上

0. 前言

C++ 的疊代器分為五種 : 輸出疊代器,輸入疊代器, 前向疊代器, 雙向疊代器和隨機訪問疊代器. 這五種疊代器從前到後功能越來越豐富. 隨著功能的增多, 我們希望根據疊代器種類的不同, 同一個函式做的事情也不同. 例如針對輸入疊代器, 它裡面的元素是不能重複使用的, 所以我們有時候我們必須把裡面的資料複製下來. 而對於隨機訪問疊代器, 我們就不需要這樣做. 從大致上來說, 對於功能較多的疊代器, 某一些實作更加簡單一些; 對於功能比較少的疊代器, 可能要寫更多的程式碼.

這篇文章將使用疊代器作為實例, 來展現樣板超編程中的一個簡單技巧 —— traits.

更新紀錄 :

  • 2022 年 4 月 18 日進行第一次更新和修正.

1. 疊代器和函式多載

在 C++ 中, 我們通常使用函式多載來讓一個函式針對不同的型別表現出相應的不同. 但是 std::vector<T>::iterator, std::deque<T>::iterator 和內建非 void 型別的指標都屬於隨機訪問疊代器, 如何讓一個函式支援一類隨機訪問疊代器而不需要針對具體的疊代器型別進行實作呢? 於是, 我們就用到了 traits 技巧.

我們首先來看一下 std::vector 的疊代器可能的實作是什麼樣的 :

#include <iterator>
#include <cstddef>

template <typename T>
class vector_iterator {
public:
    using iterator_type = T *;
    using value_type = T;
    using pointer = T *;
    using reference = T &;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::random_access_iterator_tag;
    //...
};

在 vector_iterator 這個類別中, 我們首先注意到 iterator_category 這個型別別名成員. 顯然, vector_iterator 是隨機訪問疊代器, 所以它的標籤是 std::random_access_iterator_tag. 在標準樣板程式庫的標頭檔 <iterator> 中, 提供了五種標籤 :

  • std::output_iterator_tag : 輸出疊代器標籤;
  • std::input_iterator_tag : 輸入疊代器標籤;
  • std::forward_iterator_tag : 前向疊代器標籤;
  • std::bidirectional_iterator_tag : 雙向疊代器標籤;
  • std::random_access_iterator_tag : 隨機訪問疊代器標籤.

每一個疊代器內部都有這樣的型別別名成員用於說明疊代器的標籤. 所以我們可以通過這個標籤對函式進行多載 :

#include <iterator>
#include <forward_list>
#include <vector>
#include <list>

template <typename Iterator>
void f(Iterator begin, Iterator end, std::input_iterator_tag);
template <typename Iterator>
void f(Iterator begin, Iterator end, std::forward_iterator_tag);
template <typename Iterator>
void f(Iterator begin, Iterator end, std::bidirectional_iterator_tag);
template <typename Iterator>
void f(Iterator begin, Iterator end, std::random_access_iterator_tag);

int main(int argc, char *argv[]) {
    std::forward_list<int> flist {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector<int> vec {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::list<int> blist {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    f(flist.cbegin(), flist.cend(), std::forward_list<int>::const_iterator::iterator_category {});
    f(vec.cbegin(), vec.cend(), std::vector<int>::const_iterator::iterator_category {});
    f(blist.cbegin(), blist.cend(), std::list<int>::const_iterator::iterator_category {});
}

2. std::iterator_traits

Code 2 看似運作地不錯, 但是對於內建的指標型別, 它無能為力. 因為不存在 int *::iterator_category 這樣的操作. 為了解決這個問題, 我們可以借助來自標準樣板程式庫標頭檔 <iterator> 的 std::iterator_traits :

#include <iterator>
#include <forward_list>
#include <vector>
#include <list>

template <typename Iterator>
void f(Iterator begin, Iterator end, std::input_iterator_tag);
template <typename Iterator>
void f(Iterator begin, Iterator end, std::forward_iterator_tag);
template <typename Iterator>
void f(Iterator begin, Iterator end, std::bidirectional_iterator_tag);
template <typename Iterator>
void f(Iterator begin, Iterator end, std::random_access_iterator_tag);
int main(int argc, char *argv[]) {
    std::forward_list<int> flist {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector<int> vec {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::list<int> blist {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int arr[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    f(flist.cbegin(), flist.cend(), std::iterator_traits<decltype(flist.cbegin())>::iterator_category {});
    f(vec.cbegin(), vec.cend(), std::iterator_traits<decltype(vec.cbegin())>::iterator_category {});
    f(blist.cbegin(), blist.cend(), std::iterator_traits<decltype(blist.cbegin())>::iterator_category {});
    f(arr, arr + 10, std::iterator_traits<int *>::iterator_category {});
}

這是因為 std::iterator_traits 針對內建指標進行了偏特製化.

std::iterator_traits 使用是簡單的 traits 技巧, 就是簡單地對一個傳入的疊代器進行包裝. 實際上, 它就是一個介面 :

template <typename Iterator>
struct iterator_traits {
    using iterator_type = Iterator;
    using difference_type = decltype(static_cast<int *>(nullptr) - static_cast<int *>(nullptr));
    using value_type = typename Iterator::value_type;
    using pointer = typename Iterator::pointer;
    using reference = typename Iterator::reference;
    using iterator_category = typename Iterator::iterator_category;
    // ...
};
template <typename T>
struct iterator_traits<T *> {
    using iterator_type = T *;
    using difference_type = decltype(static_cast<T *>(nullptr) - static_cast<T *>(nullptr));
    using value_type = T;
    using pointer = T *;
    using reference = T &;
    using iterator_category = std::random_access_iterator_tag;
    // ...
};

對於 void 型別的指標, 為其增加一個 & 形成參考或者對其進行指標運算的時候, 都會產生編碼錯誤. 另外, 放入非疊代器型別, 由於類別內部不存在 iterator_category 這樣類似的型別別名成員, 也會產生編碼錯誤.

3. 將 traits 用在類別特製化上

前面, 我們都將 traits 技巧用在了函式多載上, 它也可以用在類別特製化上. 例如我們可以寫一個專門用於疊代器檢查的類別 iterator_checker :

#include <iterator>
#include <forward_list>

template <typename Tag>
struct iterator_checker {
    constexpr bool operator()() const noexcept {
        return false;
    }
};
template <>
struct iterator_checker<std::random_access_iterator_tag> {
    constexpr bool operator()() const noexcept {
        return true;
    }
};

int main(int argc, char *argv[]) {
    if(iterator_checker<std::iterator_traits<std::forward_list<int>::iterator>::iterator_category> {}()) {
        // if std::forward<int>::iterator is random access iterator
    }
    if(iterator_checker<int> {}()) {
        // if int is random access iterator
    }
    if(iterator_checker<std::iterator_traits<int *>::iterator_category> {}()) {
        // if int * is random access iterator
    }
}