摘要訊息 : 入門樣板超編程.

目錄 隱藏
0. 前言
1. 為什麼 template 圖靈完全
2. 型別計算
3. 超函式
4. 統一計算
5. 樣板超編程的用處
5.1 幫助編碼器優化
5.2 省略例外處理
5.3 將計算提前至編碼期
5.4 將運作時的錯誤提升到編碼期
5.5 樣板超編程的缺點
6. find_min

0. 前言

在 C++ 被全世界熟知之前, 它還只是一個帶有類別的 C (C with Class), 當時還沒有引入樣板. 也就是說, 當時的 C++ 僅僅是一個包含了過程式以及物件導向式的程式設計語言. 後來, C++ 引入了樣板. 一開始, 樣板只是給 C++ 帶來了新的一個程式設計範式, 稱它為泛型, 於是 C++ 又是一個泛型式的程式設計語言. 又過了一段時間, 有人發現 template 的威力遠遠超過了人們的想像, 因為人們意外地發現 C++ 的 template 是圖靈完全的. 換句話說, 將樣板作為一門程式設計語言是人們偶然發現的. 因此, C++ 又多了一個新的程式設計範式——超編程式. 然而在 C++ 中, 超編程一直和 template 相結合, 所以又稱它為樣板超編程 (Template Meta-Programming, 簡稱 TMP). 在 C++ 11 引入 Lambda 表達式以及更加強大的 <functional> 標頭檔之後, C++ 的函數式程式設計又得到了加強. 又由於 TMP 與一些函數式程式設計非常相似, 所以有些人也將 TMP 歸入到函數式程式設計範式中.

現在, C++ 中存在五種程式設計範式 :

  • 過程式程式設計;
  • 物件導向式程式設計;
  • 泛型程式設計;
  • 函數式程式設計;
  • 超編程式程式設計 (樣板超編程);

更新紀錄 :

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

1. 為什麼 template 圖靈完全

定義 1. 如果一門程式設計語言具備

  1. 數值運算和符號運算;
  2. 判斷結構;
  3. 迴圈結構

那麼我們稱這門程式設計語言是圖靈完全 (Turning-comlete) 的.

現在我們逐條來對 template 進行核對, 來說明 template 到底是否是圖靈完全的. 對於數值運算和符號運算, 我們可以通過樣板的非型別參數進行 :

template <typename T, T Value1, T Value2>
struct add {
    constexpr static auto value {Value1 + Value2};      // C++ 11
    enum {      // C++ 98/03
        VALUE = Value1 + Value2
    };
};

對於判斷結構來說, 當某個條件判斷式為 true 的時候, 應該啟用某個區塊內的程式碼; 否則, 應該啟用另一個區塊內的程式碼. 那麼樣板特製化就滿足這樣的條件 :

template <bool Value>
struct if_constexpr {
    // if Value is true, do something...
};

template <>
struct if_constexpr<false> {
    // if Value is false, do something...
};

迴圈結構必須存在一個判斷條件, 如果判斷條件為 true, 那麼繼續迴圈; 如果判斷條件為 false, 那麼就應該停止迴圈. 樣板特製化其實也符合這樣的條件. 當判斷條件為 true 的時候, 我們啟用某個特製化, 直到判斷條件為 false 的時候, 就啟用另外一個專門用於停止迴圈的特製化. 但是樣板的迴圈結構和一般的迴圈結構有一些不同. 我們考慮一個函式 :

int sum(int x) {
    auto result {0};
    for(auto i {1}; i <= x; ++i) {
        result += i;
    }
    return result;
}

這個函式用來計算 \sum \limits_{i = 1}^{x}i = 1 + 2 + ... + x. 樣板是不存在 for 和 while 這樣的迴圈的, 因為這兩個關鍵字不會為類別特製化服務. 為此, 如果不用 for 和 while 能把函式 sum 寫出來嗎? 當然可以, 用遞迴就可以了 :

int sum(int x) {
    if(x == 0 or x == 1) {
        return x;
    }
    return x + sum(x - 1);
}

一個遞迴必須有一個退出條件, 這個樣板特製化是完全可以做到的, 模仿使用遞迴的函式 sum, 我們就可以使用樣板實作出來 :

template <int Value>
struct sum {
    constexpr static auto value {Value + sum<Value - 1>::value};
};
template <>
struct sum<1> {
    constexpr static auto value {1};
};
template <>
struct sum<0> {
    constexpr static auto value {0};
};

綜上所述, 根據 Code 1, Code 2 和 Code 5, 我們可以斷言 C++ template 圖靈完全.

2. 型別計算

我們知道, 樣板特製化不只是可以針對數值, 它還可以針對型別. 型別不是數字, 所以它不可以進行數值計算, 但是判斷結構和迴圈結構. 例如我們在《C++ 學習筆記》Code 94 中實作的 remove_reference 就是一個判斷結構. 現在我們來實作 std::remove_pointer. 當一個型別為 T * 的時候, 我們可以設定型別別名成員 type 為 T; 如果型別不是 T *, 而是普通的 T, 說明它不是指標型別, 那麼就直接把型別別名成員 type 設定為 T 即可 :

template <typename T>
struct remove_pointer {
    using type = T;
};
template <typename T>
struct remove_pointer<T *> {
    using type = T;
};

Code 6 中實作的 remove_pointer 只是支援移除一級指標. 也就是說如果我們傳入 T **, 最終得到的 T * 仍然是指標. 現在我們希望 remove_pointer 強化, 對於放入的多級指標, 將所有指標都移除掉. 也就是不論我們放入 T ** 還是 T***, 甚至級別更深的指標, 我們都希望得到 T. 這樣的話, 就需要借助迴圈結構. 樣板的迴圈結構不好寫, 所以一開始學習樣板超編程的時候, 我們希望借助一些工具. 現在, 我們寫出一個 remove_pointer 使用 for 的虛擬碼 :

template <typename T>
type remove_all_pointer(T) {
    auto n {T.poiner_size()};
    for(auto i {0}; i < n; ++i) {
        T = T.remove_pointer();
    }
    return T;
}

然後我們把 for 改為遞迴 :

template <typename T>
type remove_all_pointer(T) {
    if(T.pointer_size() == 0) {
        return T;
    }
    return remove_all_pointer(T.remove_pointer());
}

這樣我們就很容易地將遞迴改為樣板的版本 :

template <typename T>
struct remove_all_pointer {
    using type = T;
};
template <typename T>
struct remove_all_pointer<T *> {
    using type = typename remove_all_pointer<T>::type;
};

3. 超函式

我們發現, 不論是 Code 5 中採用數值的計算, 還是 Code 7-3 中的採用的型別計算, 類別樣板在其中的表現就像一個函式. 樣板參數就像是函式中的函式參數, 其中的 value 或者 type 就相當於函式的回傳型別. 因此, 很多人都稱樣板超編程中的類別樣板為超函式 (meta function).

習慣上, 針對數值計算的超函式, 我們使用 value 作為這個超函式的回傳值; 對於型別計算的超函式, 我們使用 type 作為這個超函式的回傳型別. 它們分別是類別的靜態成員變數和型別別名成員.

4. 統一計算

既然 template 既支援數值計算也支援型別計算, 為了統一, 我們通常會講數值計算轉換為型別計算. 我們將 Code 5 中的超函式 sum 改為型別計算 :

template <typename T, T Value>
struct value_wrapper {
    constexpr static T value {Value};
};

template <typename T>
struct sum {
private:
    using next_value_wrapper = value_wrapper<int, T::value - 1>;
public:
    using type = value_wrapper<int, T::value + sum<next_value_wrapper>::type::value>;
};
template <>
struct sum<value_wrapper<int, 1>> {
    using type = value_wrapper<int, 1>;
};
template <>
struct sum<value_wrapper<int, 0>> {
    using type = value_wrapper<int, 0>;
};

using number_10 = value_wrapper<int, 10>;
static_assert(sum<number_10>::type::value == 55, "The implement of sum is incorrect!");

我們可以發現, 雖然我們使用 value_wrapper 將一個數值包裹成了一個型別, 但是實際上, sum 的計算仍然使用 value_wrapper 中的 value. 也就是說, 這樣的型別計算本質上還是數值計算.

5. 樣板超編程的用處

我想很多人都在網路上甚至書上 (例如《Effective C++》等書籍) 看到過樣板超編程的兩大用處 :

  • 將運作時的錯誤提升到編碼期;
  • 提升程式的運作效率.

沒錯, 我不否認這兩點, 但是這兩點是空談. 實際上, 就我個人而言, 幾乎沒有用到過樣板超編程. 另外, 談優化首先需要你寫出正確的程式碼. 如果一個程式碼有錯誤, 再優化仍然是錯誤的, 仍然可能需要重寫. 你可能可以看到網路上有些人曬出的編碼錯誤充斥著 a<b<c<d<...>>>...>>>::... 這樣的錯誤, 看起來好像很厲害. 你也可能看到網路上某些人使用樣板超編程實作演算法, 例如快速排序甚至紅黑樹. 他們這些人早就對各種基本的資料結構和演算法瞭如指掌.

我在這裡很負責任地告訴大家, 樣板超編程的最大用處 —— 炫技, 炫耀自己對 C++ 的樣板非常了解. 有什麼用呢? 除了面試, 基本沒用. 學校是不可能教學這些東西的. 當然, 在面試的時候, 面試官通常也不太可能問到這些東西. 只是在面試之前, 面試官可以通過大家編寫的樣板超編程來大致判斷我所要面試的人水平如何.

這裡我寫得稍微有些保守, 用了空談和炫技這些詞, 因為我不希望文章裡面出現不文雅的用詞.

批判完了, 回正題. 樣板超編程並不是完全沒用的, 就如同上面提到的兩大用處. 我們可以利用樣板超編程來幫助編碼器優化和節省一些流程所需要的時間.

5.1 幫助編碼器優化

一個函式是否帶有 noexcept 標識決定了編碼器是否可以對這個函式進行極致的優化. 優化就代表著程式效能會提升. 現在假設函式 construct 用於回傳建構的一個物件, 那麼如果物件對應型別是內建型別或者列舉, 那麼這個函式完全可以標識 noexcept. 但是如果物件是其它用戶自訂型別, 那麼就要取決於類別的建構子是否是 noexcept 的 :

#include <utility>

template <typename T, typename ...Args>
T construct(Args &&...args) noexcept(noexcept(T {std::forward<Args>(args)...})) {
    return T {std::forward<Args>(args)...};
}

閣下可能覺得奇怪 : construct 的 noexcept 只是使用了 noexcept 運算子, 並沒有用到樣板超編程. 那麼我們改一下上面這個版本 :

#include <type_traits>
#include <utility>

template <typename T, typename ...Args>
T construct(Args &&...args) noexcept(std::is_nothrow_constructible_v<T, Args...>) {
    return T {std::forward<Args>(args)...};
}

std::is_nothrow_constructible_v 來自標頭檔 <type_traits>, 它就是通過樣板超編程來實作的. 很多來自 <type_traits> 標頭檔中的類別樣板都是超函式, 都是使用樣板超編程實作的. 如果閣下剛剛入門可以不用去了解它的實作, 但是它確實在 Code 9-2 中參與了 noexcept 的優化.

5.2 省略例外處理

和第 5.1 節類似, 是否擲出例外情況決定了一個函式的某個部分是否需要 try-catch 區塊. 如果某些操作明顯是保證不擲出例外情況的, 那麼就可以省略掉例外處理 :

#include <type_traits>
#include <utility>
#include <new>

template <typename T, typename ...Args>
T *allocate(Args &&...args) {
    auto result {::operator new(sizeof(T))};
    T *p;
    if constexpr(std::is_nothrow_constructible_v<T, Args...>) {
        p = new (result) T(std::forward<Args>(args)...);
    }else {
        try {
            p = new (result) T(std::forward<Args>(args)...);
        }catch(...) {
            ::operator delete(result);
            throw;
        }
    }
    return p;
}

我們首先要了解, try-catch 區塊是會產生額外消耗的. 在 Code 10 中, 一旦可以保證建構操作是不擲出例外情況的, 我們就可以直接省略例外處理來提升程式效能. 其中, 我們採用了 if constexpr 可以參考《C++ 17 Proposal 導讀合集 (三)》.

5.3 將計算提前至編碼期

有一些變數的情況是編碼期就已經知道的, 對於一些比較複雜的計算 (例如矩陣計算或者求導數計算), 它們沒有辦法簡單地使用 cosntexpr 標識變數, 特別是在 C++ 11 中. 因此, 我們可以借助樣板超編程直接在編碼期完成計算, 提升程式的運作效能.

5.4 將運作時的錯誤提升到編碼期

在第 5.3 節中, 我們提到了將計算提升至編碼期. 實際上, 在計算中, 我們特別容易產生錯誤. 比如輸入的時候, 不小心加了一個點, 導致一個整型型別輸入成了一個浮點數型別. 最終, 編碼器在推導型別的時候, 可能會把我們想要的整數型別提升到了浮點數型別. 這樣的錯誤在運作期難以發現. 但是在編碼期中, 一旦我們在樣板參數中放入了一個浮點數, 那麼編碼器就會立馬擲出編碼錯誤提示我們.

5.5 樣板超編程的缺點

樣板超編程也帶來了一些問題, 例如編碼時間延長和程式碼的可讀性變差. 另外, 在樣板超編程中我們可能用到一些編碼器專供特性, 這些使用了專供特性的程式碼在更換編碼器之後可能需要重新實作.

6. find_min

在本文修改之前, 提供了在一堆數值中尋找最小的那個數值的樣板超編程版本, 讓大家自行理解. 在修正的時候本來想把這部分刪掉, 但是最終仍然決定保留下來.

template <typename T, T ...>
struct find_min;
template <typename T, T Value1, T Value2, T ...Values>
struct find_min<T, Value1, Value2, Values...> {
    constexpr static auto value {find_min<T, find_min<T, Value1, Value2>::value, Values...>::value};
};
template <typename T, T Value1, T Value2>
struct find_min<T, Value1, Value2> {
    constexpr static auto value {Value1 < Value2 ? Value1 : Value2};
};
template <typename T, T Value>
struct find_min<T, Value> {
    constexpr static auto value {Value};
};

#define ASSERT_TIP "The implement of find_min is incorrect!"

static_assert(find_min<int, 1, 2, 3, 4, 5, 0>::value == 0, ASSERT_TIP);     // OK
static_assert(find_min<char, '1', '3', 'd', ' '>::value == ' ', ASSERT_TIP);        // OK
constexpr auto value {find_min<int, 1, 2, 3.0>::value};     // compile error, the type of 3.0 is double
static_assert(find_min<wchar_t, L'1'>::value, ASSERT_TIP);      // OK
template <typename T, T Value>
struct constant_value {
    constexpr static auto value {Value};
};

template <bool, typename T, typename>
struct if_constexpr {
    using result = T;
};
template <typename T, typename U>
struct if_constexpr<false, T, U> {
    using result = U;
};

template <typename, typename>
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>
struct operator_less {
    static_assert(is_same<decltype(T::value), decltype(U::value)>::value, "Invalid template arguments, the types must be same!");
    using result = typename if_constexpr<(T::value < U::value), T, U>::result;
};

template <typename ...>
struct find_min;
template <typename T, typename U, typename ...Args>
struct find_min<T, U, Args...> {
    using result = typename find_min<typename find_min<T, U>::result, Args...>::result;
};
template <typename T, typename U>
struct find_min<T, U> {
    using result = typename operator_less<T, U>::result;
};
template <typename T>
struct find_min<T> {
    using result = T;
};

#define ASSERT_TIP "The implement of find_min is incorrect!"

static_assert(find_min<constant_value<int, 5>, constant_value<int, 9>, constant_value<int, 99>>::result::value == 5, ASSERT_TIP);
static_assert(find_min<constant_value<wchar_t, L'3'>, constant_value<wchar_t, L'l'>>::result::value == L'3', ASSERT_TIP);
static_assert(find_min<constant_value<int, 0>>::result::value == 0, ASSERT_TIP);