C++ 17 折疊表達式

C++ 11 引入了 Variadic Template，讓我們得以宣告任意個數的樣版參數。C++ 標準函式庫的 std::make_tuple 就是一個典型的例子：

#include <tuple>

int main() {
  auto a = std::make_tuple("a");
  auto b = std::make_tuple(1, "a");
  auto c = std::make_tuple(1.0, 1, "a");
}

如果我們想要編寫一個 sum() 函式累加所有的參數，我們該怎麼作呢？更具體的說，我們要怎麼改寫以下 sum() 函式，使它們能接收任意個數、任意型別的參數：

int sum(int x0) {
  return x0;
}
int sum(int x0, int x1) {
  return x0 + x1;
}
int sum(int x0, int x1, int x2) {
  return x0 + x1 + x2;
}

這個問題可以分為二個部分：

如何定義 Variadic Template
如何編寫「將各個參數加總的表達式」

本文會先介紹 C++ 17 折疊表達式並用它實作 sum() 函式。作為對照，本文之後會探討 C++ 14 或 C++ 11 的替代寫法。

C++ 17 折疊表達式

折疊表達式（Folding Expression）是 C++ 17 引入的新功能。它讓我們能簡單地編寫將 Variadic Template 的 Function Parameter Pack 折疊為一個「值（Value）」。

Variadic Template

在介紹折疊表達式之前，先快速地複習 Variadic Template：

#include <utility>

template <typename... Types>
void call(Types&&... xs) {
  func(std::forward<Types&&>(xs)...);
}

上面的程式碼之中，call() 函式是一個 Variadic Template：

Types 是 Type Template Parameter Pack（型別樣版參數序列）。它是用來指稱各個參數的型別。
xs 是 Function Parameter Pack（函式參數序列）。它是用來指稱被傳入的參數值。
以 ... 結尾而且包含 Type Template Parameter Pack 與 Function Parameter Pack 的 std::forward<Types&&>(xs)... 是 Pack Expansion（參數序列展開式）。當編譯器具現化（Instantiate）一個 Variadic Template 的時候，編譯器會依據 Pack Expansion 展開 Parameter Pack（參數序列）裡面的參數。

舉例來說，如果我們呼叫 call()，則 call 樣版會被具現化為：

// Types = []
void call() {
  func();
}

如果我們呼叫 call(0, 1)，則 call 樣版會被具現化為：

// Types = [int, int]
void call(int&& x0, int&& x1) {
  func(std::forward<int&&>(x0), std::forward<int&&>(x1));
}

折疊表達式（Folding Expression）與 Pack Expansion（參數序列展開式）相似，兩者都是對參數序列（Parameter Pack）施行某種操作。兩者的相異之處在於折疊表達式會將各個參數以指定的運算子折疊成一個值，而 Pack Expansion 則是一對一對應。如果以函數語言（Functional Programming Language）的術言解釋，折疊表達式是對參數序列施行 reduce/foldl 或 reduceRight/foldr 運算，而 Pack Expansion 則是施行 map 運算。

折疊表達式的文法

折疊表達式包含三個部分：

作為運算元被展開的 Function Parameter Pack
運算子

+ - * / % ^ & | << >>

+= -= *= /= %= ^= &= |= <<= >>= =

== != < > <= >= && ||

, .* ->*
初始值（可選）

依照表達式的結合性（Associativity）與初始值，折疊表達式可以再細分為以下四種寫法：

		左結合	右結合
有初始值		( init-value op ... op pack )	( pack op ... op init-value )
	範例	`(0 + ... + xs)`	`(xs + ... + 0)`
	展開	`((((0 + x0) + x1) + ...) + xN)`	`(x0 + (x1 + (... + (xN + 0))))`
無初始值		( ... op pack )	( pack op ... )
	範例	`(... + xs)`	`(xs + ...)`
	展開	`(((x0 + x1) + ...) + xN)`	`(x0 + (x1 + (... + xN)))`

另外，以下表格是 &&、|| 與 , 運算子的預設初始值。如果我們不指定初始值且參數序列是空的，折疊表達式的計算結果就是預設初始值：

運算子	預設初始值
`&&`	`true`
`\|\|`	`false`
`,`	`void()`

除了上述運算子，若我們不指定初始值且參數序列是空的，編譯器會在具現化樣版的時候回報錯誤。

範例：實作 sum 函式

回到文章一開始提出的問題，以下程式碼實作了一個能接收任意數量且任意參數型別的 sum 函式：

#include <utility>

template <typename... Types>
auto sum(Types&&... xs) {
  return (... + std::forward<Types&&>(xs));
}

首先，為了能接收任意個數的參數，我們使用了 Variadic Template。其次，為了能同時處理左值參考（Lvalue Reference）與右值參考（Rvalue Reference），我們以 Forward Reference（即 Types&&）接收參數，並且以 std::forward<Types&&>(xs) 施行適當的型別變換。最後，我們以 (... + std::forward<Types&&>(xs)) 折疊表達式展開 xs。我們沒有指定初始值，因為 sum 函式要能接收任意參數型別。此外，當 xs 為空的時候，產生編譯錯誤也是合理的。

以下是 sum() 函式的使用範例：

#include <iostream>
#include <string>

int main() {
  std::cout << sum(1) << std::endl;
  std::cout << sum(1, 2) << std::endl;
  std::cout << sum(1, 2, 3) << std::endl;
  std::cout << sum(1, 2, 3, 4) << std::endl;

  std::cout << sum(std::string("a")) << std::endl;
  std::cout << sum(std::string("a"), "b", "c") << std::endl;
}

以下是執行結果：

1
3
6
10
a
abc

範例：左結合性與右結合性

因為對於大多數的型別加法有結合律，所以上一小節的 sum 函式比較難看出「左結合性」與「右結合性」的差異。以下程式碼改以減法展示兩者的差異：

#include <iostream>
#include <utility>

template <typename... Types>
auto diff_left_assoc(Types&&... xs) {
  return (... - std::forward<Types&&>(xs));
}

template <typename... Types>
auto diff_right_assoc(Types&&... xs) {
  return (std::forward<Types&&>(xs) - ...);
}

int main() {
  std::cout << diff_left_assoc(1, 2, 3, 4, 5) << std::endl;
  std::cout << diff_right_assoc(1, 2, 3, 4, 5) << std::endl;
}

以上程式碼的執行結果如下：

-13
3

這是因為 diff_left_assoc(1, 2, 3, 4, 5) 會被展開為 ((((1 - 2) - 3) - 4) - 5) 而 diff_right_assoc(1, 2, 3, 4, 5) 會被展開為 (1 - (2 - (3 - (4 - 5))))。

替代寫法

如果你不能使用 C++ 17，本節會簡單地介紹如何使用「函式重載（Function Overloading）」或「類別樣版特化（Class Template Specialization）」實作類似的功能。

C++ 14

如果你只能使用 C++ 14 實作 sum 函式，你必須定義三個重載函式（Overload Function）分別處理一個參數、二個參數、三個參數（或以上）。這是因為我們希望 sum 函式有左結合性，所以我們必須先計算前二個參數的和，再將結果作為遞回呼叫的第一個參數。程式碼節錄如下：

#include <utility>

template <typename Type0>
Type0 sum(Type0&& x0) {
  return std::forward<Type0&&>(x0);
}

template <typename Type0, typename Type1>
auto sum(Type0&& x0, Type1&& x1) {
  return std::forward<Type0&&>(x0) + std::forward<Type1&&>(x1);
}

template <typename Type0, typename Type1, typename... Types>
auto sum(Type0&& x0, Type1&& x1, Types&&... xs) {
  return sum(std::forward<Type0&&>(x0) + std::forward<Type1&&>(x1),
             std::forward<Types>(xs)...);
}

C++ 11

隨著參數型別的不同，+ 運算子可能也會回傳不同的型別，因此上一小節的實作使用了 C++ 14 引入的「回傳型別推導」（以 auto 關鍵字作為回傳型別）。C++ 11 標準要求我們以 auto 與 decltype 編寫回傳型別，例如：

template <typename Type0, typename Type1>
auto sum(Type0&& x0, Type1&& x1)
    -> decltype(std::forward<Type0&&>(x0) + std::forward<Type1&&>(x1)) {
  return std::forward<Type0&&>(x0) + std::forward<Type1&&>(x1);
}

然而在實作「三個參數（或以上）」的重載函式會遇到問題。因為當我們編寫 decltype 的時候能接收三個參數（或以上）的函式還沒有被定義，decltype 裡面的 sum 只會將「一個參數」與「二個參數」的重載函式作為候選函式。當我們傳入四個參數並且想要遞迴地呼叫 sum 函式的時候，編譯器會回報錯誤：

template <typename Type0, typename Type1, typename... Types>
auto sum(Type0&& x0, Type1&& x1, Types&&... xs)
    -> decltype(sum(std::forward<Type0&&>(x0) + std::forward<Type1&&>(x1),
                    std::forward<Types>(xs)...)) {
  return sum(std::forward<Type0&&>(x0) + std::forward<Type1&&>(x1),
             std::forward<Types>(xs)...);
}

int main() {
  sum(1, 2, 3);     // OK
  sum(1, 2, 3, 4);  // XX: compilation error
}

因此在 C++ 11 我們必需改用「類別樣版特化（Class Template Specialization）」繞開這個限制。程式碼節錄如下：

template <typename... Types>
class Helper {};

template <typename Type0>
class Helper<Type0> {
public:
  static Type0 sum(Type0&& x0) {
    return std::forward<Type0&&>(x0);
  }
};

template <typename Type0, typename Type1>
class Helper<Type0, Type1> {
public:
  static auto sum(Type0&& x0, Type1&& x1) -> decltype(
      std::forward<Type0&&>(x0) + std::forward<Type1&&>(x1)) {
    return std::forward<Type0&&>(x0) + std::forward<Type1 &&>(x1);
  }
};

template <typename Type0, typename Type1, typename... Types>
class Helper<Type0, Type1, Types...> {
public:
  static auto sum(Type0&& x0, Type1&& x1, Types&&... xs)
      -> decltype(Helper<decltype(x0 + x1), Types...>::sum(
          std::forward<Type0&&>(x0) + std::forward<Type1&&>(x1),
          std::forward<Types&&>(xs)...)) {
    return Helper<decltype(x0 + x1), Types...>::sum(
      std::forward<Type0&&>(x0) + std::forward<Type1&&>(x1),
      std::forward<Types&&>(xs)...);
  }
};

template <typename... Types>
auto sum(Types&&... xs)
    -> decltype(Helper<Types&&...>::sum(std::forward<Types&&>(xs)...)) {
  return Helper<Types&&...>::sum(std::forward<Types&&>(xs)...);
}

參考資料

N4191, N4295: Folding expressions
Unary Folds and Empty Parameter Packs (revision 1)

Note

如果你喜歡這篇文章，請追蹤羅根學習筆記粉絲專頁。最新文章都會在粉絲專頁發佈通知。

`+`	`-`	`*`	`/`	`%`	`^`	`&`	`\|`	`<<`	`>>`
`+=`	`-=`	`*=`	`/=`	`%=`	`^=`	`&=`	`\|=`	`<<=`	`>>=`	`=`
`==`	`!=`	`<`	`>`	`<=`	`>=`	`&&`	`\|\|`
`,`	`.*`	`->*`