從 C++11 規格學習 C++ Templates — 第一篇

contributed by < jeffrey.w >

Template metaprogramming (TMP) 是一種從 template 的角度開發的 paradigm，也就是說他不是著眼在 int 或是 float 這種特定的 type，而是著眼在形而上的 type。原本我想用 concept 或是 generic 來說明，但由於 concept 和 generic 在 C++ 另有其他的解釋，為避免混淆，所以這裡不會提到 concept 和 generic。

C++11 從規格定義了 template，是學習 template 相當有用的第一手資料。本文是透過規格書學習 templates 的筆記，範圍包含 constexpr、type traits、partial specializations和template constructor，並且對於 compiler 在編譯時產生的 error 給出規格書上的解釋。

透過這份文件 N3377=12-0067，可以知道 N3376 是最接近 C++11 規格的草案，所以這份筆記主要是以 N3376 為主。

預習規格書裡的知識點

先理解 C++11 規格書提到的幾個知識點，對於後續內容的理解會有相當的幫助，例如知道 incomplete type 的定義，有助於在編譯錯誤時發現 incomplete type 的原因。

incomplete object type

[C++11 規格, 3.9.1_9]

The void type is an incomplete type that cannot be completed.

[C++11 規格, 3.9_5]

A class that has been declared but not defined, or an array of unknown size or of incomplete element type, is an incompletely-defined object type.

依 C++11 規格, 3.9 的規範，class C 是 been declared but not defined，屬於 incomplete type。







class C;
C* p;   // a pointer to incomplete type

int main(){
   p++;    // ill-formed: C is incomplete
   return 0;
}

用 -c 來看看操作 incomplete type 在 compile-time 會有什麼結果。

$ gcc -std=c++11 incomplete.cpp -c
incomplete.cpp: In function ‘int main()’:
incomplete.cpp:5:5: error: cannot increment a pointer to incomplete type ‘C’
    p++;
     ^~

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

這個 error 在 C++11 規格書裡是不是有定義？

依 C++11 規格, 3.9 的規範，這個 arr 的 element 是 incomplete type。






class C;

int main(){
   C arr[4];  // ill-formed: incomplete type
   return 0;
}

所以編譯的時候也會產生錯誤

$ gcc incomplete1.cpp -c -std=c++11
incomplete1.cpp: In function ‘int main()’:
incomplete1.cpp:4:6: error: elements of array ‘C arr [4]’ have incomplete type
    C arr[4];  // ill-formed: incomplete type
      ^~~
incomplete1.cpp:4:6: error: storage size of ‘arr’ isn’t known

cv-qualifiers

從 C++11 規格 _[3.9.3] 來看 cv-qualifiers

Each type which is a cv-unqualified complete or incomplete object type or is void(3.9) has three corresponding cv-qualified versions of its type: a const-qualified version, a volatile-qualified version, and a const-volatile-qualified version

也就是說，每一個 cv-unqualified 都有三個相對應的 cv-qualified：

const
volatile
const volatile

同樣的，incomplete object type 和 void 也都會有上面所說的三個對應的 cv-qualified。

constexpr

依 C++11 規格 _[7.1.5/1]，constexpr 可以被用在 定義變數、宣告 function 或是 function template，也可以用在宣告 static data member，這裡先看其中兩個情況：

constexpr functions
constexpr constructors

C++11 規格 [7.1.5/3] 要求 constexpr function 要滿足以下的限制

it shall not be virtual;
its return type shall be a literal type;
each of its parameter types shall be a literal type
its function-body shall be = delete, = default, or a compound-statement that contains only
- null statements
- static_assert-declarations
- typedef declarations and alias-declarations that do not define classes or enumerations
- using-declarations
- using-directives
- and exactly one return statement.

舉一個例子來看最後一個限制 exactly one return statement










constexpr int add(int a, int b){
   a += b;
   return a;
}

int main(){
   int a = 1, b = 2;
   int ret = add(a, b);
   return 0;
}

照 C++11 的限制，add 違反了這個限制 exactly one return statement，所以在 compile-time 就會有 error。這裡使用 -S 這個參數 (Compile only)，來突顯這個 error 是發生在 compile-time。

$ gcc constexpr.cpp -S -std=c++11
constexpr.cpp: In function ‘constexpr int add(int, int)’:
constexpr.cpp:4:1: error: body of constexpr function ‘constexpr int add(int, int)’ not a return-statement
 }
 ^

type traits

type traits 是要用來解決什麼問題的？
在 compile-time 有什麼資訊是 template 需要取得的？
有哪些資訊是在 compile-time 可以取得的？
如何確認哪些資訊己經在 compile-time 取得？
Type Inference

從 C++11 規格書 [20.9] 來看 type traits，規格書是這麼說的：

… and perform type inference and transformation at compile time. It includes type classification traits, type property inspection traits, and type transformations.
…
The type property inspection traits allow important characteristics of types or of combinations of types to be inspected. The type transformations allow certain properties of types to be manipulated.

也就是說，type traits 是用來在 compile time 作型別檢查和型別轉換的。

inspection traits
transformations
從 C++11 規格書 20.9.7.5, Pointer modifications 看一個型別轉換的例子
- remove_pointer
  以下這三種各自代表什麼？

std::remove_pointer<int>::type
std::remove_pointer<int *>::type
std::remove_pointer<int **>::type

C++11 規格書 _[20.9.7.5] 這麼說

template <class T> struct remove_pointer;

If T has type “(possibly cv-qualified) pointer to T1” then the member typedef type shall name T1; otherwise, it shall name T.

依照 C++11 規格書 _[20.9.7.5]，上述的三種 type 各自代表的型別如下：

std::remove_pointer<int>::type    // int (因為 int 不是一個 pointer)
std::remove_pointer<int *>::type  // int (因為 int * 是一個指向 int 的 pointer)
std::remove_pointer<int **>::type // int * (因為 int ** 是一個指向 int * 的 pointer)

Reference

Variadic templates

在 variadic templates 還沒有納入 C++11 規格書之前，如果要模擬 variable-length templates 的效果，主要是透過 overloads 來實現 _[link]。也就是說，先假設 最多會有 N 個 template arguments，然後針對 0 ~ N 個 template arguments 分別撰寫 overloads 的 function templates。

這個方法顯然在維護或是擴充都是很辛苦的，但自從 variadic templates 納入 C++11 規格 _[14.5.3] 後，在維護和擴充上都獲得了顯著的改善，不用再針對不同個數的 template arguments 撰寫各自的版本了。

template parameter pack
如果用 overload，底下的例子就要準備三份 implementions，但是 variadic templates 就只需要一份實作。

template<class ... Types> struct Tuple { };

Tuple<int> a;
Tuple<int, float> b;
Tuple<int, double, float> c;

function parameter pack
同樣地，跟 overload 相比，底下的例子也只需要一份實作。

template<class ... Types> void f(Types ... args) {};

f();
f(1.0);
f(2.0, 3, "string");

Reference

Douglas Gregor & Jaakko Järvi (February 2008). "Variadic Templates for C++0x". Journal of Object Technology. pp. 31–51.
n3270, Variadic Templates: Wording for Core Issues 778, 1182, and 1183.

Type inference and transformation

C++11 規格書在 §20.9 描述了在 compile-time 執行型別推論和型別轉換的 component ^[1]，例如在 compile-time 查詢 type 的 property (§20.9.5)、兩個 type 之間的關係 (§20.9.6)。

舉個例子來實驗看看，這個範例改寫自 C++11 規格書 §20.9.6















#include <type_traits>
#include <cassert>

class B {
};
class B1 : B {
};
class B2 : B {
};
class D : private B1, private B2 {
};

int main(int argc, char **argv) {
    assert((std::is_base_of<B1, D>::value));
}

assert 是一個 function-like macro，以上面的 source code 來說明什麼是 function-like macro，像以下兩種 preprocessing token，對 assert 的 argument 來說，是不一樣的

assert(( std::is_base_of<B1, D>::value )) 有加括號，所以整個 (std::is_base_of<B1, D>::value) 是一個 preprocessing token
assert(std::is_base_of<B1, D>::value) 沒有加括號，所以 preprocessing token 就會有兩個，第一個是 std::is_base_of<B1，第二個是D>::value，於是會有以下的 compile error。注意看第二行，因為沒有加括號，所以 std::is_base_of<B1, D>::value 被視為兩個 arguments
```
$ g++ -std=c++11 is_base_of.cpp -S  
is_base_of.cpp:14:41: error: macro "assert" passed 2 arguments, but takes just 1
14 |     assert(std::is_base_of<B1, D>::value);
```

constructor 在 template 是如何運作的？

constructor 有三種： default constructor、copy constructor、move constructor，先看 non-template 的 copy constructor 在 C++11 規格裡怎麼說：
[C++11, §12.8]

A non-template constructor for class X is a copy constructor if its first parameter is of type X&, const X&, volatile X& or const volatile X&, and either there are no other parameters or else all other parameters have default arguments

這是 first parameter 是 const X& 的例子

#include <iostream>

class T {
public:
   T() {};
   T(const T &ref) { 
      std::cout << "copy constructor is called" << std::endl;
   };
};

int main(){
   T t1;
   T t2 = t1;  // copy constructor is called here
   return 0;
}

編譯後，執行時會得到這個結果

$ gcc test2.cpp -std=c++11 -lstdc++ -o test2
$ ./test2
copy constructor is called

如果把 copy constructor 改寫成 template 的話，會是如何運作的？

#include <iostream>

using namespace std;

template <class T>
class X { 
    public:
       X (){ 
          std::cout << "default constructor" << std::endl;
       }   
       // copy constructor
       X (const X<T>& ref){
          std::cout << "template copy constructor" << std::endl;
       }   
};

int main(){
   X<int> a;      // default constructor
   X<int> b = a;  // template copy constructor
   return 0;
}

編譯後，執行時會得到這個結果

$ gcc copy-constructor.cpp -o copy-constructor -std=c++11 -lstdc++
$ ./copy-constructor 
default constructor
template copy constructor

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

雖然編譯會通過，但在 C++11 規格裡，有沒有規範到 template copy constructor？

Curiously Recurring Template Pattern (CRTP)

這裡寫一段 code 實驗一下 C++ 常見的 template pattern - Curiously Recurring Template Pattern (CRTP)，這個 pattern 是由 James Coplien 在 1996 年的 C++ Gems 裡初次提出。

static_cast and dynamic cast

dynamic cast
C++11 5.2.7/1 對 dynamic_cast 有限制不能對 const 作轉型

The dynamic_cast operator shall not cast away constness

所以，這段 code 在 compile-time 會有 error
```
class Base {
};

class Derived : public Base {
};

int main(){
    const Derived d;
    dynamic_cast<Base&>(d);
    return 0;
}
```
compile-time 所產生的 error conversion casts away constness 就是 C++11 規格 [5.2.7/1] 所說的 shall not cast away constness
```
$ gcc cast.cpp -S -std=c++11
cast.cpp: In function ‘int main()’:
cast.cpp:9:26: error: cannot dynamic_cast ‘d’ (of type ‘const class Derived’) to type ‘class Base&’ (conversion casts away constness) dynamic_cast<Base&>(d);
```
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
不過，為什麼 dynamic_cast 不是在 run-time 的時候才作 cast？

Polymorphic

C++11 規格 [10.3 Virtual functions] 是這樣定義多型的：

A class that declares or inherits a virtual function is called a polymorphic class

所以，class Base 和 class Derived 都屬於 polymorphic class

#include <iostream>

using namespace std;

// declares a virtual function
class Base {
   public:
      virtual void f(){}
};

// inherits a virtual function
class Derived : virtual public Base {
    void f(){
       std::cout << "derived" << std::endl;
    };
};

int main(){
   Derived derived;
   Base *ptr = &derived;
   ptr->f();    // derived
   return 0;
}

Barton and Nackman trick

N1758 這份 proposal 並沒有採用 Barton & Nackman trick，直到 C++20 才再被提出。
Barton & Nackman trick 和 CRTP 是不一樣的 pattern。

CRTP

CRTP 和 Barton & Nackman trick 有一個不一樣的地方，就是 CRTP 的 derived class 是不需要 friend declarations 的。
綜合一下上述提到的 static_cast，舉一個例子來看 CRTP


























#include <iostream>

using namespace std;

template<typename T>
class Base {
   public:
      void func() {
         static_cast<T*>(this)->func();
      }
};

class Derived : public Base<Derived>
{
   public:
      void func(){
         std::cout << "derived" << std::endl;
      }
};

int main(){
    Derived d;
    Base<Derived> *b = &d;
    b->func();    // derived
    return 0;
}

從 C++11 規格來看以上這個例子在 compile-time 發生了什麼事？

Reference

Partial specializations

以下這段 code 在直覺上會以為 a2.f() 是呼叫到 template<class T, int I> void A<T, I>::f() { };
















template<class T, int I> struct A {
   void f();
};

template<class T, int I> void A<T, I>::f() { };

template<class T> struct A<T, 2> {
   void f();
};

int main()
{
   A<char, 2> a2;
   a2.f();    // 不會呼叫 template<class T, int I> void A<T, I>::f() { };
   return 0;
}

但這個直覺是錯的，因為 C++11 規格, 14.5.5.3 這麼說

A class template specialization is a distinct template. The members of the class template partial specialization are unrelated to the members of the primary template.

也就是說，A<T, I>::f() 和 A<T, 2>::f() 是 unrelated。
所以，不會因為 A<T, 2>::f() 沒有定義就呼叫 A<T, I>::f()，a2.f() 仍然是需要 A<T, 2>::f() 的定義。因此，上面那段 code 在 compile 的時候會出現以下的 error：

$ gcc -std=c++11 test.cpp -o test
/tmp/ccw9gLnA.o: 於函式 main:
test.cpp:(.text+0x1f): 未定義參考到 A<char, 2>::f()
collect2: error: ld returned 1 exit status

這是兩個不一樣的 template，這兩個 template 彼此之間沒有關係

A<T, I>
A<T, 2>

所以，A<T, I>::f() 有定義實作，不表示 A<T, 2>::f() 也有定義實作

實驗環境

OS：

Ubuntu 18.04.2 LTS

Compiler：

gcc version 7.3.0 (Ubuntu 7.3.0-27ubuntu1~18.04)
Target: x86_64-linux-gnu

Reference

tags: `c++11` `c++` `N3376` `c++ templates` `compile-time` `Template Metaprogramming` `TMP` `type traits` `constructor template` `partial specializations`

從 C++11 規格 學習 C++ Templates — 第一篇

預習規格書裡的知識點

incomplete object type

Reference

Reference

Type inference and transformation

constructor 在 template 是如何運作的？

Curiously Recurring Template Pattern (CRTP)

static_cast and dynamic cast

Reference

實驗環境

Reference

tags: c++11 c++ N3376 c++ templates compile-time Template Metaprogramming TMP type traits constructor template partial specializations

Read more

I/O ordering 學習紀錄

Experiments on Concurrency - Happens-before

Design patterns 筆記 - Strategy pattern on C++

Notes on Java8 Stream and Lambda expression

從 C++11 規格學習 C++ Templates — 第一篇

tags: `c++11` `c++` `N3376` `c++ templates` `compile-time` `Template Metaprogramming` `TMP` `type traits` `constructor template` `partial specializations`