摘要訊息 : 替換失敗並不是一個錯誤!

目錄 隱藏
0. 前言
1. 嘗試改進
1.1 借助 using 宣告
1.2 借助超函式
2. SFINAE
3. 解決方案
4. SFINAE 不是函式多載

0. 前言

C++ 的多型除了體現在類別的動態繫結上之外, 還體現於函式的多載. 函式的多載屬於編碼期多型, 也就是靜態多型, 它的行為在編碼期就會被確定, 在運作期不會更改. 我們通常利用函式多載不會影響運作期程式效能的這個特點進行簡單的樣板超編程. 在《【C++ Template Meta-Programming】Traits 技巧》中, 我們講述了 Traits 技巧. Traits 技巧是樣板超編程中一個非常常用的技巧, 它通常和函式結合. 在《【C++ Template Meta-Programming】Traits 技巧》中, 我們可以利用疊代器標記來表示同名函式的不同行為 :

#include <iterator>

template <typename InputIterator>
void func(InputIterator, InputIterator, std::input_iterator_tag);
template <typename OutputIterator>
void func(OutputIterator, OutputIterator, std::output_iterator_tag);
template <typename ForwardIterator>
void func(ForwardIterator, ForwardIterator, std::forward_iterator_tag);
template <typename BidirectionalIterator>
void func(BidirectionalIterator, BidirectionalIterator, std::bidirectional_iterator_tag);
template <typename RandomAccessIterator>
void func(RandomAccessIterator, RandomAccessIterator, std::random_access_iterator_tag);

int main(int argc, char *argv[]) {
    func(static_cast<int *>(nullptr), static_cast<int *>(nullptr), typename std::iterator_traits<int *>::iterator_category {});
}

對於程式庫使用者來說, 每一個函式後面都加一個 typename iterator_traits<iterator>::iterator_category 物件的初始化顯然是很麻煩的. 我們想要的結果是去掉這個看似多餘的函式參數.

更新紀錄 :

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

1. 嘗試改進

參閱 C++ 標準樣板程式庫文檔之後, 我們發現 : 來自 C++ 標準樣板程式庫所有容器的建構子都支援放入一個範圍疊代器, 但是它們不需要明確地給出疊代器標籤, 因此我們去除函式中疊代器標籤參數的想法是可行的. 對於如何做到函式參數無需放入疊代器標籤, 我們有幾個初步的想法.

1.1 借助 using 宣告

如果不想在運作期有任何的消耗, 那麼我們可以在函式內使用 using 宣告一個疊代器標籤的別名 :

template <typename InputIterator>
void f(InputIterator begin, InputIterator end) {
    using iterator_category = typename std::iterator_traits<InputIterator>::iterator_category;
    // ...
}

int main(int argc, char *argv[]) {
    f(static_cast<int *>(nullptr), static_cast<int *>(nullptr));     // OK
    f(0, 0);     // Error : no type named 'iterator_category' in 'std::iterator_traits<int>'
}

Code 2 看起來貌似可行. 但是實際上我們只是限定了參數必須是一個疊代器, 如若我們要更加細緻地限定疊代器的具體種類, 那麼它束手無策.

1.2 借助超函式

要想判斷一個疊代器的具體種類, 這其中涉及到了條件判斷, 因此我們需要超函式的幫助. 這個超函式所要做的就是判斷兩個給出的型別是否為同一個型別, 那麼它自然也就可以判斷疊代器對應的疊代器種類是否為我們需要的型別. 不妨叫這個超函式為 is_same, 那麼應該如何實作它呢? 我們應該先理解這個超函式具體要幹什麼. 假如給出兩個型別, 如果是一樣的型別, 那麼超函式的回傳結果是 true; 否則, 回傳型別是 false. 在《【C++ Template Meta-Programming】認識樣板超編程 (TMP)》中, 我們介紹過超函式有兩種形式的回傳值, 一個是型別, 一個是具體的值. 為了方便起見, 我們先讓它回傳值 :

template <typename T, typename U>
struct is_same {
    constexpr static auto value {false};
};
template <typename T>
struct is_same<T, T> {
    constexpr static auto value {true};
};

當給定的兩個型別是一樣的, 那麼自動特製化到 is_same_type<T, T>, 此時 value 的值為 true; 此外的其它情況, value 的值全都是 false. 現在, 我們對 Code 2 進行一些修改 :

template <typename T, typename U>
struct is_same {
    constexpr static auto value {false};
};
template <typename T>
struct is_same<T, T> {
    constexpr static auto value {true};
};

template <typename InputIterator>
void f(InputIterator begin, InputIterator end) {
    if(is_same_type<typename iterator_traits<InputIterator>::iterator_category, std::random_access_iterator_tag>::value) {
        // this scope is able to use the features from random access iterator
        // ...
    }else {
        // ...
    }
}

int main(int argc, char *argv[]) {
    f(static_cast<int *>(nullptr), static_cast<int *>(nullptr));     // OK
    f(0, 0);     // Error : no type named 'iterator_category' in 'std::iterator_traits<int>'

}

Code 4 仍然有不足的地方. 如果我們希望函式 f 只接受隨機訪問疊代器, 傳入其它疊代器應該產生編碼錯誤, 那麼 Code 4 就無法做到. 另外, 還有一點值得我們深思. 像 std::vector 這樣的容器, 針對 int 型別的具現化都會產生一個建構子的具現體 std::vector<int>(size_type, const int &);. 那麼, 對於 std::vector<int>(10, 10) 這樣的建構, 它會匹配到這個建構子上而不會匹配到其它建構子上. 但是實際上, 當我們自己實作 vector 的時候並沒有那麼簡單 :

#include <cstddef>
#include <iterator>

template <typename T, typename U>
struct is_same {
    constexpr static auto value {false};
};
template <typename T>
struct is_same<T, T> {
    constexpr static auto value {true};
};

template <typename T>
class vector {
public:
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using value_type = T;
    using const_reference = const T &;
    // ...
public:
    vector(size_type, const_reference);
    template <typename Iterator>
    vector(Iterator, Iterator);
    // ...
};

template <typename T>
template <typename Iterator>
vector<T>::vector(Iterator begin, Iterator end) {
    if(is_same_type<typename iterator_traits<InputIterator>::iterator_category, std::forward_iterator_tag>::value) {
        // ...
    }else {
        // ...
    }
}

對於 vector<int>(10, 10) 這樣的初始化, size_type 的型別為 std::size_t, 在 macOS 12 和 Apple Clang 下, std::size_t 是 unsigned long. 因此 size_type 實際上是 unsigned long, const_reference 實際上是 const int &. 但是 vector<int>(10, 10) 中的兩個 10 都是 int 型別, 它如果想要匹配到 vector(size_type, const_reference); 這個建構子上, 第一個 10 就要發生一次隱含型別轉換. 而如果匹配到 template <typename Iterator> vector(Iterator, Iterator); 這個建構子上的話, Iterator 會被推導為 int, 顯然具現體 vector(int, int); 更加匹配 vector<int>(10, 10). 而 int 型別中不存在一個名稱為 iterator_category 這樣的型別別名成員. 最終, Code 5 產生編碼錯誤. 即使 std::size_t 在不同的作業系統或者不同的編碼器下不是 unsigned long, 但它總歸是無號數型別, 不會是 int. 所以, Code 5 總會產生編碼錯誤.

2. SFINAE

我們首先隨意寫一個和函式樣板匹配有關的程式碼 :

struct Foo {
    using type = int;
};

template <typename T>
void f(typename T::type);
void f2(int);

int main(int argc, char *argv[]) {
    f(0);        // Error
    f2("");       // Error
}

如果大家觀察仔細的話, 就會發現 f(0) 和 f2("") 這兩個呼叫所產生的編碼錯誤是不一樣的. 在 Apple Clang 編碼器下, f(0) 這個呼叫產生的編碼錯誤是 no matching function for call to 'f'. candidate template ignored: couldn't infer template argument 'T', f2("") 這個呼叫產生的編碼錯誤是 no matching function for call to 'f2', candidate function not viable: no known conversion from 'const char [1]' to 'int' for 1st argument.

對於 f(0) 這個呼叫來說, 編碼器說的是候選樣板函式 f 被忽略; 對於 f("") 這個呼叫來說, 編碼器說的是候選函式 f2 不可行. 所以我們應該可以推斷, 編碼器針對函式樣板的處理和普通函式是不一樣的. 針對函式樣板, 編碼器首先嘗試使用實際的型別替換樣板參數, 然後產生對應的具現體. 這時, 我們有了疑問 : 替換失敗就會導致編碼錯誤嗎? 回答是 SFINAE.

在解釋 SFINAE 之前, 我們來看另外一個和函式樣板匹配的程式碼 :

struct Foo {
    using type = int;
};
struct Bar {
    using type2 = int;
};

template <typename T>
void f(typename T::type);
template <typename T>
void f(typename T::type2);

int main(int argc, char *argv[]) {
    f<Foo>(0);       //OK
    f<Bar>(0);       //OK
}

當 func<Bar>(0) 嘗試匹配具現化的 template <> void func<Bar>(typename Bar::type); 時, 編碼器發現 Bar 裡面沒有名稱為 type 的型別別名成員. 此時, 編碼器並沒有放棄繼續匹配其它函式, 因為多載集合內部還有別的具現體可以去嘗試匹配, 直接擲出無法匹配的編碼錯誤顯然是不太負責任的. 當匹配到具現化的 template <> void func<Bar>(typename Bar::type2); 時, 成功了.

通過分析, 我們發現當編碼器替換一個函式樣板產生具現體後, 如果嘗試匹配這個具現體時失敗了, 編碼器並不會直接放棄, 因此也不會直接擲出編碼錯誤. 只有所有的替換以及轉型都不生效, 此時還沒有可以匹配的函式的時候, 才會擲出編碼錯誤. 總結這句話, 也就有了 SFINAE (Substitution failure is not an error). 翻譯成中文 : 替換失敗不是一個錯誤.

現在, 我們通過 SFINAE 來分析 Code 6 中的 f(0) 為什麼會產生編碼錯誤. 我們預想的是編碼器自動找到 Foo, 使用 Foo 替換樣板參數, 最終 typename T::type 被替換為 typename Foo::type, 也就是 int型別. 沒錯, 這樣是說得通的. 但是大家要想到, 不僅僅 Foo 裡面可能會有名稱為 type 的型別別名成員, 萬一別的檔案中也有這樣一個類別, 類別內有一個名稱為 type 的型別別名成員, 編碼器應該選擇哪個作為 T 的最終型別呢? 你可能會說, 哪個 typename T::type 是 int 就選擇哪個. 那要是兩個 typename T::type 都是 int 呢? 顯然編碼器無法選擇. 於是對於這種情況, 編碼器乾脆告訴你 : 如果你不明確 T 的型別, 我就不進行選擇. 最終, 就產生了編碼錯誤. 所以如果遇到類似於 Code 6 的程式碼, 大家一定要記得給出樣板引數.

但是有一種情況我們是不需要明確樣板引數的, 那就是編碼器可以推導的情況下 :

struct Foo {
    using type = int;
};

template <typename T>
void f(typename T::type, T);

int main(int argc, char *argv[]) {
    f(0, Foo {});       // OK
}

編碼器通過 f(0, Foo {}) 的第二個引數, 可以推導得到 T 的實際型別為 Foo, 所以就用 Foo 去替換了 T. 經過替換之後, T 已經明確了, 而且 T 內部也有一個名為 type 的型別別名成員, 而且第一個引數 0 可以精準匹配 (像 0.0 這種可以通過隱含型別轉化匹配), 自然也就不會產生編碼錯誤了.

3. 解決方案

回到對 Code 1 的改進. 根據 Code 8 中的實例, 我們發現即使去掉了 Code 1 中函式 func 的第三個參數, 那麼 func 仍然有兩個參數都和樣板參數有關, 因此我們可以在其中一個參數上加上限制 :

#include <iterator>
#include <iostream>

template <typename T, typename>
struct out {
    using type = T;
};

template <typename RandomAccessIterator>
void func(typename out<RandomAccessIterator, typename std::iterator_traits<RandomAccessIterator>::iterator_category>::type, RandomAccessIterator) {
    std::cout << "random access iterator" << std::endl;
}
void func(unsigned long, const int &) {
    std::cout << "unsigned long, const int &" << std::endl;
}

int main(int argc, char *argv[]) {
    func(static_cast<int *>(nullptr), static_cast<int *>(nullptr));     // 輸出 : random access iterator
    func(0, 0);     // 輸出 : unsigned long, const int &
}

對於 func(0, 0); 這個呼叫, 編碼器會通過第二個 0 推導得到 RandomAccessIterator 應該推導為 int, 然後發現 std::iterator_traits<int>::iterator_category 並不合法. 這個時候根據 SFINAE, 替換失敗之後就會丟掉這個匹配, 然後嘗試去匹配 void func(unsigned long, const int &); 成功. 現在, 我們可以成功區分疊代器和一般型別了.

最開始, 我們的需求是針對不同類型的疊代器特製化多載函式的行為, 那麼我們修改 Code 9 中的超函式 out. 這個超函式的第二個樣板參數並沒有什麼太大用處, 只是負責接受合法的 std::iterator_traits<T>::iterator_category. 現在, 我們實作這樣一個超函式 :

template <bool, typename T>
struct enable_if {
    using type = T;
};
template <typename T>
struct enable_if<false, T> {};

enable_if 若且唯若在第一個樣板引數了為 true 的時候, 才會有名稱為 type 的型別別名成員. 我們可以結合 enable_if 和前面的 is_same, 來解決不同函式處理不同疊代器的需求 :

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

template <typename T, typename U>
struct is_same {
    constexpr static auto value {false};
};
template <typename T>
struct is_same<T, T> {
    constexpr static auto value {true};
};
template <typename T, typename U>
constexpr auto is_same_v {is_same<T, U>::value}

template <bool, typename T>
struct enable_if {
    using type = T;
};
template <typename T>
struct enable_if<false, T> {};
template <bool Value, typename T>
using enable_if_t = typename enable_if<Value, T>::type;

template <typename Iterator>
using category = typename std::iterator_traits<ForwardIterator>::iterator_category;

template <typename ForwardIterator>
void func(enable_if_t<is_same_v<category<ForwardIterator>, std::forward_iterator_tag>, ForwardIterator>, ForwardIterator) {
    std::cout << "forward iterator" << std::endl;
}
template <typename BidirectionalIterator>
void func(enable_if_t<is_same_v<category<BidirectionalIterator>, std::bidirectional_iterator_tag>, BidirectionalIterator>, BidirectionalIterator) {
    std::cout << "bidirectional iterator" << std::endl;
}
template <typename RandomAccessIterator>
void func(enable_if_t<is_same_v<category<RandomAccessIterator>, std::random_access_iterator_tag>, RandomAccessIterator>, RandomAccessIterator) {
    std::cout << "random access iterator" << std::endl;
}

int main(int argc, char *argv[]) {
    std::forward_list<int> flist {1, 2, 3, 4};
    std::list<int> l {1, 2, 3, 4};
    std::vector<int> vec {1, 2, 3, 4};
    func(flist.begin(), flist.end());       // 輸出 : forward iterator
    func(l.begin(), l.end());       // 輸出 : bidirectional iterator
    func(vec.begin(), vec.end());       // 輸出 : random access iterator
    func(0, 0);     // Error
}

Code 11 比較複雜, 我們首先分析 func 的第一個參數. 以 enable_if_t<is_same_v<category<ForwardIterator>, std::forward_iterator_tag>, ForwardIterator> 為例. is_same_v<category<ForwardIterator>, std::forward_iterator_tag> 判斷了疊代器的種類是否為前向疊代器. 如果是, 那麼 enable_if_v<true, ForwardIterator> 就是 ForwardIterator; 否則, enable_if 中就不存在名稱為 type 的型別別名成員. 然後我們來分析 func(flist.begin(), flist.end()) 這個呼叫. 編碼器首先通過第二個引數推導得到樣板參數 ForwardIterator 的型別為 typename std::forward_list<int>::iterator. 顯然, std::forward_list 的疊代器屬於前向疊代器. 那麼它會使得 is_same_v<category<ForwardIterator>, std::forward_iterator_tag> 的值為 true (一旦把 std::forward_iterator_tag 替換成 std::bidirectional_iterator_tag 或者 std::random_access_iterator_tag 就會導致值為 false). 那麼也就是說, 另外兩個 func 中, enable_if_t<false, ForwardIterator> 是不合法的, 它們就會被編碼器遺棄. 對於 func(0, 0) 這個呼叫, 三個 func 中都會產生 enable_if_t<false, ForwardIterator> 這樣不存在的型別, 從而沒有一個函式是替換之後可以匹配的.

在下一篇文章中, 我們將詳細講述哪些行為可能引發 SFINAE.

4. SFINAE 不是函式多載

最後, 我們要明確 SFINAE 不是函式多載. 函式多載要求同名函式的參數列表相異. Code 11 的體現其實不明顯, 我們通過下面這個實例來理解 SFINAE 不是函式多載 :

template <typename T, typename U>
struct is_same {
    constexpr static auto value {false};
};
template <typename T>
struct is_same<T, T> {
    constexpr static auto value {true};
};

template <bool, typename T>
struct enable_if {
    using type = T;
};
template <typename T>
struct enable_if<false, T> {};

template <typename T>
typename enable_if<is_same<T, int>::value, int>::type f();
template <typename T>
typename enable_if<is_same<T, double>::value, double>::type f();

Code 12 可以通過編碼, 並沒有產生編碼錯誤, 所以我們可以斷定 SFINAE 並不是函式多載, 它只是編碼期多型的另外一個體現罷了.