[譯] C++中帶狀態元編程黑科技（二）：實現常量表達式計數器

介紹

在上一篇文章中，我們了解了向 constexpr 的世界添加狀態的基本方法，也就是說，在翻譯階段加入狀態。

這個技術引入了一種類似於 bool 的類型，但它可以在程序編譯時改變它的值（而不僅僅是運行時）。

我們提出並解決了以下問題：

// <在這裡填入你的答案>nint main() {n constexpr int a = f();n constexpr int b = f();n static_assert(a != b, "fail");n}n

註：使得上面的代碼能夠通過編譯的一種方法是 #define f() __LINE__，但顯然這不是本文所要介紹的內容（即使這是一個非常聰明的方法）。

所以，接下來做什麼？

在本文中，我們會繼續將這個概念發揚光大，使得下面這段代碼能夠通過編譯（不觸發 static_assert）：

// <在這裡填入你的答案>nint main() {n constexpr int a = next();n constexpr int b = next();n constexpr int c = next();n static_assert(a == 1 && b == a + 1 && c == b + 1, "try again");n}n

我們也會介紹這種技術背後所包含的原理，以及如何使得代碼符合ISO C++標準（N3290，即C++11）。

必備知識

除了上一篇文章所介紹的知識之外，你需要了解下列概念才能夠完全理解下面的實現：

• 參數依賴查找（ADL）
• 默認參數的求值
• SFINAE的要領
• 表示數值的原理

註：這個部分的內容是對於文末的答案中涉及到的技術要點的介紹，所以這個部分可以被有經驗的（或者渴望答案的）讀者跳過。

想直接看答案的，請往下跳到答案↓↓↓

參數依賴查找的語義

當編譯器看到函數調用中作為函數名的無修飾的標識符（unqualified-id，即不包含域操作符 :: 的名稱）時，C++的規則說編譯器應當尋找更多可能不在這個函數調用的當前上下文中的函數。

尋找更多函數的過程會被函數調用本身的參數所影響，並且為了尋找到最佳匹配的函數，每一個參數都可能會增加搜索的作用域。

考慮下面的例子：

namespace N {n struct X {};n void func(X, int); // (1)n}nnvoid func(int, int);// (2)nnnamespace M {n struct Y {n operator int();n };n void func(N::X, int); // (3)n}nnint main() {n N::X x;n M::Y y;n n func(x, 0); // OK，通過ADL找到(1)n (func)(x, 0); // 不正確，會調用(2)n func(x, y); // 有歧義，通過ADL找到(1)和(3)n M::func(x, y); // 有修飾的操作符，調用(3)n}n

註：(func) 不是一個名稱而是一個表達式，所以不會使用ADL。

類型為 T 的參數會增加搜索哪些作用域？

註：在ISO C++標準的 [basic.lookup.argdep]p2 有完整的列表，但下面的列表足以應對大部分的常見情況下的ADL。

如果參數類型 T 是：

• 一個內置類型，則不會增加任何作用域。
• 一個指向 U 的指針或 U 的數組，則增加的作用域會和 U 有關。
• 一個函數類型，則增加的作用域有：
• 和它的參數類型相關的作用域；
• 和它的返回類型相關的作用域。
• 一個枚舉類型，則增加的作用域有：
• 它所在命名空間；
• 以它為成員的類（如果有的話）。
• 一個類（或者指向它的指針），則增加的作用域有：
• 和它的每一個模板參數相關的作用域（如果它是一個模板特化）；
• 類本身；
• 以它為成員的類（如果有的話）；

• 它的直接或間接的基類（如果有的話）；
• 它和它的基類（如果有的話）聲明所在的作用域。

參考：[basic.lookup.argdep]p1-3

默認參數的求值

C++有兩種緊密聯繫著的默認參數：模板默認參數和函數默認參數。雖然它們的使用範圍大相徑庭，但它們有著許多共同的規則。

默認參數是：

• 一個表達式（不是值）；
• 每次需要的時候都會進行求值；
• 不能為模板參數包（template parameter pack）指定；
• 如果它引用了一個依賴名稱，則在被使用前這個名稱不會實例化。

默認參數會在每次使用時被求值這個事實可能不會讓任何人驚訝。在下面的代碼中，我們可以預料到 "hello, worldn" 會被輸出三次：

int g() {n std::cout << "hello worldn";n return 0;n}nnvoid f(int = g()) { /* 故意留空 */ }nnint main() {n for (int i = 0; i < 3; ++i) f();n}n

進一步地說，即使它在某些太年輕的C++開發者眼中很可笑，下面是一段合法的C++代碼：

template <int N>nstruct A {n int arr[-N];n};nntemplate <int N>nvoid f(int arg = A<N>{}) { /* 故意留空 */ }nnint main() {n f<123>(0);n}n

註：默認參數 arg 不會被求值，也不會被實例化，這意味著不會有產生不存在的 A<123> （這裡 A<123>::arr 的大小會是負的）的實例的問題。

SFINAE的要領

對於類或函數模板有一系列的特化，我們希望對於滿足特定條件模板參數，模板會產生不同的行為。

讓我們來考慮下面這個不太自然的小例子：

namespace detail {n template<class T, class = char[(sizeof(T) > 4 ? 1 : -1)]> // 檢查 n constexpr bool is_big(int) {n return true;n }n n template<class T>n constexpr bool is_big(float) {n return false;n }n}nntemplate<class T>nconstexpr bool is_big() {n return detail::is_big<T>(0); // 調用最匹配的函數n}nnint main() {n static_assert(is_big<char>() == false, "!!"); // OKn static_assert(is_big<double>() == true, "!!"); // OKn}n

在上面的例子中有兩個重要的概念：

1. 重載決議

先不考慮模板所做的事，我們可以看到命名空間 detail 中的兩個名為 is_big 的函數，其中一個接受一個類型為 int 的參數，另一個接受一個類型為 float 的參數。

bool overloaded(int); // (1)nbool overloaded(float); // (2) n

重載決議是說，當編譯器遇到有多個重載的函數調用時，編譯器會通過函數的參數找到最佳候選函數。

簡單地說，最佳候選是指傳遞的參數需要最少的工作（轉換、類型推導等等）就能用於調用的重載。

overloaded(0); // 調用(1)n

如果有多個合適程度相同的函數（例如參數需要相同量的工作來用於調用），則程序是不正確的。

overloaded(0); // 不正確，在重載(1)和(2)中有歧義n

2. 匹配失敗不是錯誤

在使用模板時，我們可能會遇到特定的模板特化只能為特定的模板參數實例化的情況。

如果在模板參數的推導或匹配的過程中遇到錯誤時停止整個編譯過程的話，我們就不能寫出下面這樣的代碼：

template <class T>nvoid print(T const& val) { // (1)n std::cout << val << std::endl;n}nntemplate <class T>nvoid print(T* ptr) { // (2)n print(*ptr);n}nnint main() {n const int x = 123;n const int* p = &x; n n print(x); // 調用(1)n print(p); // 調用(2)n} n

在用 (2) 特化 main 中的 print(x) 時，即使編譯器沒有辦法形成指向 const T 的指針，ISO C++標準並不認為程序是不正確的——編譯器會簡單地丟棄這個特化，並使用更合適的選擇。

進一步說，標準明確規定了數組的大小不能為負，這意味著 detail::is_big<T>(int) 只能在 sizeof(T) > 4 時被實例化：

namespace detail {n template<class T, class = char[(sizeof(T) > 4 ? 1 : -1)]> // 檢查 n constexpr bool is_big(int) {n return true;n }n n template<class T>n constexpr bool is_big(float) {n return false;n }n}n

當這個實現在尋找 detail::is_big<T>(0) 中的函數時，它會試圖實例化每一種可能的選擇，並且丟棄不可行的選擇。

對於 detail::is_big<T>(0)， 有兩種選擇（依賴於 T）：

• 如果兩個模板在模板參數匹配之後都是可行的話，以 int 為參數的函數對於以 float 為參數的函數是更好的匹配：重載決議會選擇前者。
• 如果只有後者可以被實例化，重載決議會簡單地選擇以 float 為參數的函數（即使在調用時需要進行轉換）——因為只有這一種選擇。

參考：[over.match]、[dcl.array]p1、[temp.deduct]p1-9、[temp.deduct.call]p1-6

表示數值的原理

註：這個部分簡單介紹了使用多個無法直接裝下數值的實體來表示數值的方法。

請不要將這個「數值表示」和ISO C++中的數值表示相混淆（即使兩者有相似點）。

內置類型 bool 可以在兩個狀態間切換，它可以為 false 或是 true，這和我們在上一篇文章中介紹的「變數」很類似。

但是，它們有一個很重要的不同點：bool 可以在兩個狀態間任意切換，但我們的「變數」只能從一個狀態變為另一個狀態，反過來就不行。

如果我們想在這些實體中存儲數值，我們需要使用多個實體來達到我們想要的效果——由於它們的不同點，實現的方法也不同。

使用多個 bool 表示 N 個狀態

如果我們要表示 N 個不同的狀態（N > 0），那麼就需要使用至少 log2(N) 個 bool。

N = 4nSET = { bool A, bool B } // size = log2(N) => 2nn A Bn ----- -----n0 => { false, false }n1 => { false, true }n2 => { true, false }n3 => { true, true }n

使用多個 constexpr 函數表示 N 個狀態

上面部分中的 B 需要在兩個狀態中切換，但正如前面所說的，我們的「變數」是沒有辦法進行切換的。

為了通過有條件地定義 constexpr 函數（下面用 cexprf 簡寫）來表示 N 個不同的狀態，我們需要至少 N - 1 個函數。

N = 4nSET = { cexprf X, cexprf Y, cexprf Z } // size = N-1 => 3nn X Y Zn --------- --------- ---------n0 => { undefined, undefined, undefined }n1 => { defined, undefined, undefined }n2 => { defined, defined, undefined }n3 => { defined, defined, defined }n

答案

實現

template <int N>nstruct flag {n friend constexpr int adl_flag(flag<N>);n};nntemplate <int N>nstruct writer {n friend constexpr int adl_flag(flag<N>) {n return N;n }n static constexpr int value = N;n};nntemplate <int N, int = adl_flag(flag<N>{})>nint constexpr reader(int, flag<N>) {n return N;n}nntemplate <int N>nint constexpr reader(float, flag<N>, int R = reader(0, flag<N-1>{})) {n return R;n}nnint constexpr reader(float, flag<0>) {n return 0;n}nntemplate<int N = 1>nint constexpr next(int R = writer<reader(0, flag<32>{}) + N>::value) {n return R;n}nnint main() {n constexpr int a = next();n constexpr int b = next();n constexpr int c = next();n static_assert(a == 1 && b == a + 1 && c == b + 1, "try again");n}n

註：因為 vc++（微軟的Visual C++）的bug，這段代碼的行為會是不正確的。用於 vc++ 的解決方案在附錄中。

詳細介紹

「變數」

在「表示數值的原理」部分中，我們快速地了解了用上一篇文章中的技術表示 N 個不同狀態的方法：使用多個變數。

如果在實現計數器時，我或者開發者需要顯式地寫出 N 個作為「變數」的名稱的話會顯得很枯燥。所以我們用類模板來讓編譯器為我們生成它們——這省去了我們打一大堆字的功夫。

template <int N>nstruct flag {n friend constexpr int adl_flag(flag<N>);n};n

當這個基本類模板被實例化時，編譯器會有效地引入名為 int adl_flag(flag<N>) 的函數，它只能通過參數依賴查找找到。

寫入器

有了多個「變數」，我們當然需要多個「寫入器」。和與上面的方法的邏輯一樣，我們用類模板來創建 adl_flag(flag<N>) 的定義。

template <int N>nstruct writer {n friend constexpr int adl_flag(flag<N>) {n return N;n }n static constexpr int value = N;n};n

因為我們需要強制 writer<N> 的實例化，每一個 writer<N> 的特化都有一個 static constexpr 的數據成員，它會簡單地存下不是類型的模板參數 N 的值。

讀取器

這是這個實現中最有技術含量的部分，但它其實沒有看上去那麼複雜。

為了查詢函數是否有定義來獲取計數器當前的計數，我們需要遍歷 adl_flag 的不同重載並檢查它們的狀態。如果使用重載決議的話，這會是一個很簡單的任務。

reader 的不同重載總是會用兩個參數進行調用，第一個是 int（0），第二個是 template<int>struct flag 的一個特化，如下所示：

reader(0, flag<N>{});n

• 匹配

template <int N, int = adl_flag(flag<N>{})>nint constexpr reader(int, flag<N>) {n return N;n}n

如果不顯式地將模板參數傳遞給上面的模板，那麼特化只會在 adl_flag(flag<N>{}) 在常量表達式中可用時才可行：只有在 adl_flag 已經被定義之後才可以被調用。

• 搜索器

template <int N>nint constexpr reader(float, flag<N>, int R = reader(0, flag<N-1>{})) {n return R;n}n

搜索器接受 int 作為第一個參數，而它的第一個參數類型為 float。因為重載決議，我們能夠很快地看出當0作為第一個參數時，如果前面一種重載可用的話重載決議就會選擇前面的重載，否則就會選擇後面這個重載。

如果搜索器被選中的話，默認參數 R 會被求值。這可以有效地向下遍歷不同的重載，直到找到停止遞歸的函數——並返回當前的計數。

• 基礎

int constexpr reader(float, flag<0>) {n return 0;n}n

由於我們的搜索器是向下遍歷不斷尋找小於 N 的值，我們必須提供一個基礎來防止陷入無限遞歸（在這種情況下 reader(int, flag<N>) 永遠不會被實例化）。

幫助類

reader 給予了我們讀取當前計數的能力，所以現在我們只需要一個根據當前計數實例化下一個 writer<N> 的函數——這可以有效地增加計數值。

template<int N = 1>nint constexpr next(int R = writer<reader(0, flag<32>{}) + N>::value) {n return R;n}n

我們使得 reader 從32開始搜索，並向下遍歷至0，這意味著我們計數器的最大值為32.。

註：你可以反過來實現從0開始數到無窮大——這使得編寫一個「無窮」的計數器成為可能。

因為這樣的實現會更加麻煩一些，我將這個問題留給讀者作為練習。

注意事項

很重要的一點是要記住我們正在對付與C++中的一些相當複雜的規則有關的東西。最重要的是，這當中的某些規則本意並不是讓我們這樣（濫）用它們。

當處理這些複雜的規則時，如果沒有仔細思考標準保證了什麼，以及沒有保證什麼的話，我們很容易就會引發一些問題。

模板實例化順序

在上一篇文章中我們花了相當多的時間討論模板的實例化位置，以及函數模板是如何擁有多個實例化位置的。

我們沒有明確指出的事實是：因為函數模板可以有多個實例化位置，兩個不同的實體的代碼生成順序是沒有保證的。

template <class, int Dummy = 1>nconstexpr int indirection() {n return next<Dummy>();n}nnint main() {n constexpr int a = indirection<bool>(); // (1)n constexpr int b = indirection<void>(); // (2)n static_assert(a < b, "!!"); // 沒有保證 n static_assert(a != b, "!!"); // OK n}n

註：即使 (2) 在 (1) 之後，編譯器可以以任何它認為合適的順序來生成特化的函數體的代碼。

通常情況下代碼生成的順序是觀察不到的，但是當我們能夠改變常量表達式的全局狀態之後，它就顯得非常重要了，這主要是因為我們依賴一些改變的順序。

總的來說上面這段代碼不保證 a < b 會返回 true，因為代碼生成的順序是實現定義的（implementation-defined）。

如何規避這個問題

解決的方法非常簡單：不要在函數模板的函數體中依賴全局狀態的改變，只在求職順序有保障的上下文中使用它們，例如：

• 作為模板或函數的默認參數；
• 直接在類模板特化之內（它最多有一個實例化位置）；
• 在函數模板聲明中；
• 在非模板函數的聲明或定義中。

模板參數匹配的順序

在C++11中模板參數匹配的順序（在沒有依賴的表達式間）是實現定義的，這意味著我們可能會遇到一些順序與想像中不相符的情況。

在C++14中不同實現的順序變成了統一的，我寫了一份 Q&A 來解釋為什麼模板參數匹配的順序是重要的（不僅僅是因為本文中提到的技術）：

• Why does the order of template argument substitution matter?

翻譯單元

如果在多個翻譯單元（Translation Unit，TU）中在使用本文中的技術的話，很容易會破壞單個單個定義原則（One Definition Rule，ODR）。

這個問題歸結為：這個技術依賴於通過檢查在當前翻譯單元中是否定義了某一函數，有條件地提供函數的定義。

因為函數最多只能有一個定義（ODR），並且沒有辦法檢查一個函數是否在其它編譯單元中有定義，所以當你在使用這種技術之前應當仔細考慮。

用 inline 怎麼樣？

除了使用匿名命名空間之外，可以依賴與標準中所說的：只要 inline 函數的定義在不同編譯單元中一樣，就可以有多個定義。

3.2p3 One definition rule [basic.def.odr]p3

Every program shall contain exactly one definition of every non-inline function or variable that is odr-used in that program; no diagnostic required. The definition can appear explicitly in the program, it can be found in the standard or a user-defined library, or (when appropriate) it is implicitly defined (see 12.1, 12.4 and 12.8). An inline function shall be defined in every translation unit in which it is odr-used.

儘管這是一個合適的解決方案，但我有希望方法越簡單越好。

如何規避這個問題

只在當前翻譯單元的局部上下文中使用這種技術，例如將代碼放在匿名命名空間中來防止與其它翻譯單元中相同名稱的定義產生衝突。

拓展閱讀：

• http://stackoverflow.com——c++ - Inline Function Linkage
• http://msdn.com——Unnamed Namespaces

總結

本文講解了在常量表達式中使用計數器的技術，以及在實現背後的一些注意事項（如果你沒有恰當地考慮它的副作用的話（這是個雙關語））。

和上一篇文章一起，它有力地展示了常量表達式並不是「無狀態」的，並且我們可以通過狀態的改變來解決「不可能解決」的問題。

下一步做什麼？

我們可以將我們現在的計數器實現當做一個可以在全局範圍內增加的計數器。在下一篇文章中我們將展示如何任意的值與任意的狀態相關聯——這使得編寫下面的代碼成為可能：

using LX = ...;nnLX::push<void, void, void, void>();nLX::set<0, class Hello>();nLX::set<2, class World>();nLX::pop();nnLX::value<> x; // type_list<class Hello, void, class World>n

附錄

用於 vc++ 的解決方法

vc++ 對於本文中原始解決方法的處理存在問題：

• vc++ 沒有很好地支持表達式SFINAE
• vc++ 不支持常量表達式中的聚合初始化（aggregate-initialization）
• vc++ 不會重新對用於函數參數的默認參數中的模板參數的表達式進行求值

template <int N>nstruct flag {n friend constexpr int adl_flag(flag<N>);n};nntemplate <int N>nstruct writer {n friend constexpr int adl_flag(flag<N>) {n return N;n }n n static constexpr int value = N;n};nntemplate <int N, class = char[noexcept(adl_flag(flag<N>())) ? +1 : -1]>nint constexpr reader(int, flag<N>) {n return N;n}nntemplate <int N>nint constexpr reader(float, flag<N>, int R = reader(0, flag<N-1>())) {n return R;n}nnint constexpr reader(float, flag<0>) {n return 0;n}nntemplate <int N = 1, int C = reader(0, flag<32>())>nint constexpr next(int R = writer<C + N>::value) {n return R;n}nnint main() {n constexpr int a = next();n constexpr int b = next();n constexpr int c = next();n static_assert(a == 1 && b == a + 1 && c == b + 1, "try again");n}n

感謝閱讀~

特邀嘉賓：@bhuztez@vczh