C++模板元编程入门

Posted on | In

前言

 
本文只是针对TMP(Template Metaprogramming)的简单说明，并不涉及模板元编程中的各种黑魔法诸如编译期堆排序，实现反射特性等等。
旨在对TMP做一个入门科普，以及简单介绍TMP在实际业务中存在哪些应用。

前置知识

 
C++模板特化，偏特化的一些匹配原则。（参考C++ Primer相关章节即可）
C++模板类型推导的基本原理，以及模板类型推导的一些常见问题。
具体可见Effective Modern C++ Item1。

模板元编程的基本概念

 
顾名思义，模板元编程就是用模板来实现元编程，它工作于编译期，而非运行期。
开发者尝试使用模板实例化的一些特性和约束来完成一些计算任务，或者实现一些在运行期很难完成的功能。

TMP的简单应用（编译期求值）

abs

abs相当于是TMP内的”hello,world”, 我们通过它来了解最基础的模板元编程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <int N> // use template parameter as a function parameter
struct my_abs{
    static_assert(N != INT_MIN, "N must not be INT_MIN");
    inline static constexpr int value = N < 0 ? -N : N; // use static data member as return value
};

void test_my_abs() {
    static_assert(my_abs<-1>::value == 1, "my_abs<-1>::value == 1");
    static_assert(my_abs<1>::value == 1, "my_abs<1>::value == 1");
    static_assert(my_abs<0>::value == 0, "my_abs<0>::value == 0");
    static_assert(my_abs<-6>::value == 6, "my_abs<-6>::value == 6");
    static_assert(my_abs<INT_MAX>::value == INT_MAX, "my_abs<INT_MAX>::value == INT_MAX");
    // cannot compile
    // static_assert(my_abs<INT_MIN>::value == -INT_MIN, "my_abs<INT_MIN>::value == -INT_MIN");
}

fibonacci

为了展现tmp并非只能完成简单计算求值，有fibonacci的TMP递归实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
template<unsigned int N>
struct Fibonacci {
    inline static constexpr unsigned int value = Fibonacci<N - 1>::value + Fibonacci<N - 2>::value;
};

template<>
struct Fibonacci<0> {
    inline static constexpr unsigned int value = 0;
};

template<>
struct Fibonacci<1> {
    inline static constexpr unsigned int value = 1;
};

unsigned int fibonacci(unsigned int n) {
    // bad impl!!!
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}


void test_fibonacci() {
    cout << "Fibonacci<45>::value = " << Fibonacci<45>::value << endl; // calculates fibonacci(45) at compile time
    cout << "fibonacci(45) = " << fibonacci(45) << endl; // cost too much run time
    cout << "Fibonacci<10000>::value = " << Fibonacci<10000>::value << endl; // error!
}

不过编译期递归并不能为所欲为，其递归深度取决于编译器允许的模板实例化的最大深度，不过可以通过-ftemplate-depth=N进行调整。
（constexpr函数同样存在编译期递归深度限制问题）

TMP的简单应用（操作类型）

到目前为止，给出的2个示例并不能真正体现TMP的优势，毕竟我们完全可以用constexpr函数取代abs<>和fibonacci<>。 TMP的优势在于，它的参数可以是一个类型，而非一个值。实际上，c++内早就有这种函数，例如sizeof。

1
2
3
4
5
6
int main() {
    static_assert(sizeof(int) == 4, "int is not 4 bytes");
    long long ll = 0;
    static_assert(sizeof ll == 8, "long long is not 8 bytes");
    static_assert(sizeof(long long) == 8, "long long is not 8 bytes");
}

输入类型，输出值

假设存在一个场景，我们需要根据指定类型返回一个值，例如根据指定类型，返回该类型的最大值或者最小值(也就是std::numeric_limits)。 那么可以有简单实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template<typename T>
struct max_value {};

template<>
struct max_value<int> {
    inline static constexpr int value = INT_MAX;
};

template<>
struct max_value<long> {
    inline static constexpr long value = LONG_MAX;
};

...

class MY_CLASS {};

void test_max_value() {
    cout << max_value<int>::value << endl;
    cout << max_value<long>::value << endl;
    // cannot compile
    // cout << Max_value<MY_CLASS>::value << endl;
}

可以注意到，对于已经完成特化的部分类型，max_value运行地很好，但对于其他类型，将会直接导致编译报错。
这种技法被称之为SFINAE（Substitution Failure Is Not An Error）。SFINAE是元编程基础组件std::enable_if的重要基础，后续会继续提到。

输入类型，输出类型

也许我们不应该仅仅将目光停留在输出数值上，更进一步地，TMP可以输出一个类型，而不仅仅是数值。

type traits

模板函数可以根据输入类型的一些特性，返回特定类型。在某些场景下这种名叫type traits的技法非常有用，例如stl中的大部分泛型算法都基于这种技法。

问题实例

举一个最简单的例子，让某个迭代器移动指定的步长, advance函数声明大致类似于

1
2
3
4
template<class InputIterator, class Distance>
inline void advance(InputIterator &i, Distance n) {
  ... // impl
}

问题分析

众所周知，stl内各容器的迭代器均为具体的类型，并且具备不同的特性，以vector举例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<class T, class Alloc = simpleAlloc<T>>
class vector {
 public:// alias declarartions
  using value_type = T;
  using pointer = value_type *;
  using iterator = value_type *;// iterator is raw pointer
  using const_iterator = const value_type *;
  using const_reference = const value_type &;
  using size_type = size_t;
  using difference_type = ptrdiff_t;

 private:// data member
  // iterator to indicate the vector's memory location
  iterator start;
  iterator finish;
  iterator end_of_storage;
}

对于vector而言，它的迭代器类型为value_type *，单纯的指针类型，支持随机访问。
而list则不然，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
template<class T>
struct list_iterator {
  using self = list_iterator<T>;
  using link_type = list_node<T> *;

  using iterator_category = bidirectional_iterator_tag;
  using value_type = T;
  using pointer = T *;
  using reference = T &;

  using difference_type = ptrdiff_t;

  // data member
  link_type node;// raw pointer link to list_node

  // increasement
  self &operator++() {
    node = node->next;
    return *this;
  }

  self operator++(int i) {
    self temp = *this;
    ++(*this);
    return temp;
  }

  // decreasement
  self &operator--() {
    node = node->prev;
    return *this;
  }

  self operator--(int i) {
    self temp = *this;
    --(*this);
    return temp;
  }
};

list的迭代器显然仅仅支持双向递增递减，并不支持随机访问。
slist（单链表)的迭代器具体实现此处略过不再赘述，不过它的迭代器仅支持前向递增。
显然，枚举出所有迭代器并一一重载是不现实的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename T>
inline void advance(slist<T>::iterator &i, size_t n) {
  while (n--) ++i;
}
template<typename T>
inline void advance(list<T>::iterator &i, int n) {
  if (n >= 0)
    while (n--) ++i;
  else
    while (n++) --i;
}
template<typename T>
inline void advance(vector<T>::iterator &i, int n) {
  i += n;
}

解决方案

stl将迭代器分为以下5种类型，并存在以下继承关系：

1
2
3
4
5
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {}; // 前向迭代器
struct bidirectional_iterator_tag : public forward_iterator_tag {}; // 双向迭代器
struct random_access_iterator_tag : public bidirectional_iterator_tag {}; // 随机访问迭代器

并且定义迭代器type traits为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<class Iterator>
struct iterator_traits {
  using iterator_category = typename Iterator::iterator_category;
  using difference_type = typename Iterator::difference_type;
};

template<class T>
struct iterator_traits<T *> {
  using iterator_category = random_access_iterator_tag;
  using difference_type = ptrdiff_t;
};

// in c++14 style
template<class Iterator>
using iterator_category_t =
    typename iterator_traits<Iterator>::iterator_category;

template<class Iterator>
using difference_type_t = typename iterator_traits<Iterator>::difference_type;

因此，自定义迭代器只需要在内部声明iterator_category和difference_type（为了避免忘记声明，stl提供了一个模板以供继承），即可使用type_traits。 因此，advance函数具体实现为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<class InputIterator, class Distance>
inline void _advance(InputIterator &i, Distance n, input_iterator_tag) {
  while (n--) ++i;
}

template<class InputIterator, class Distance>
inline void _advance(InputIterator &i, Distance n,
                     bidirectional_iterator_tag) {
  if (n >= 0)
    while (n--) ++i;
  else
    while (n++) --i;
}

template<class InputIterator, class Distance>
inline void _advance(InputIterator &i, Distance n,
                     random_access_iterator_tag) {
  i += n;
}

template<class InputIterator, class Distance>
inline void advance(InputIterator &i, Distance n) {
  _advance(i, n, iterator_category_t<InputIterator>());
}

拓展

事实上，type traits在stl泛型算法中的应用随处可见（这也与stl的设计理念有关），例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
template<class T>
inline void destroy(T *p) {
  p->~T();
}

template<class ForwardIterator>
inline void destroy(ForwardIterator beg, ForwardIterator end) {
  using is_POD_type = typename type_traits<ForwardIterator>::is_POD_type;
  destroy_aux(beg, end, is_POD_type());
}

// 如果元素的value_type不存在non—trivial destructor
template<class ForwardIterator>
inline void destroy_aux(ForwardIterator beg, ForwardIterator end,
                         false_type) {
  for (; beg != end; ++beg) destroy(&*beg);// 毕竟迭代器不是真正的地址
}

// 存在trivial destructor
// 如果对象的析构函数无关痛痒，那么反复调用它是一种效率上的巨大浪费
template<class ForwardIterator>
inline void destroy_aux(ForwardIterator, ForwardIterator, true_type) {}

// 针对char*、wchar_t*的特化
inline void destroy(char *, char *) {}
inline void destroy(wchar_t *, wchar_t *) {}

不胜枚举。

构建模板元编程的基础组件

模板元编程中的代码复用

问题实例

假设存在一个场景，开发者需要对输入的类型添加或删除某种属性。
先从最简单的例子开始———擦除某种类型的const属性：

1
2
3
4
5
6
7
8
9
10
11
12
template<typename T>
struct remove_const {
    using type = T;
};

template<typename T>
struct remove_const<const T> {
    using type = T;
};

template<typename T>
using remove_const_t = typename remove_const<T>::type;

移除volatile也是类似的，如：
1
2
3
4
5
6
7
8
9
template<typename T>
struct remove_volatile {
    using type = T;
};

template<typename T>
struct remove_volatile<volatile T> {
    using type = T;
};

擦除reference也是类似的，如：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename T>
struct remove_reference {
    using type = T;
};

template<typename T>
struct remove_reference<T&> {
    using type = T;
};

template<typename T>
struct remove_reference<T&&> {
    using type = T;
};

显然，add_lreference，add_rrefernce的实现也并不复杂，此处不再赘述。

问题分析

前文所提及的所有模板元案例，要么基于xxx::value，要么基于xxx::type（表示TMP的返回是一个类型还是一个值）。
每一次模板元编程都写一次using type = xxx是一次非常磨人的行为，类似的代码理论上应该被复用。因此，我们有必要实现一些基础组件，并根据这些基础组件来完成模板元编程的开发工作。

TMP基础组件

证同的实现与应用

证同操作是一个单纯的投射，输入一个T类型，返回一个T类型。

1
2
3
4
template<typename T>
struct identity {
    using type = T;
};

通过identity，remove_xxx的实现可以更加优雅：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename T>
struct remove_const: identity<T> {};

template<typename T>
struct remove_const<const T>: identity<T> {};

template<typename T>
struct remove_reference : identity<T> {};

template<typename T>
struct remove_reference<T&>: identity<T> {};

template<typename T>
struct remove_reference<T&&>: identity<T> {};

编译期数值的实现与应用

1
2
3
4
5
6
7
8
9
10
11
12
template<typename T, T val>
struct integral_constant {
    inline static constexpr T value = val;
    using value_type = T;
    using type = integral_constant;
    constexpr operator value_type() const noexcept {
        return value;
    }
    constexpr value_type operator()() const noexcept {
        return value;
    }
};

根据integral_constant，开发者可以使用integral_constant<T, val>来创建和使用编译期数值，例如：

1
2
3
4
5
template<bool val>
using bool_constant = integral_constant<bool, val>;

using true_type = bool_constant<true>;
using false_type = bool_constant<false>;

how to impl is_same?

is_same，顾名思义，返回两个类型是否相同，其具体实现如下：

1
2
3
4
5
template<typename T, typename>
struct is_same : false_type {};

template<typename T>
struct is_same<T, T> : true_type {};

how to impl is_void ?

操作类型的基础是了解当前传入的类型，在泛型编程中，我们时常需要类似于is_int,is_float,is_pointer等等诸如此类的类型判断。
本文并不关注描述如何实现以上工具，只是试图表明以上工具均可以通过前文已有所涉及的基础组件加以实现。
还是从最简单的例子开始，尝试通过几种方法来实现 is_void。

通过特化穷举所有可能
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename T>
struct is_void: false_type {};

template<>
struct is_void<void>: true_type {};

template<>
struct is_void<void const>: true_type {};

template<>
struct is_void<void volatile>: true_type {};

template<>
struct is_void<void const volatile>: true_type {};
use is_same && remove_cv
1
2
template<typename T>
struct is_void : is_same<remove_cv_t<T>::type, void> {};
use is_one_of

is_one_of，顾名思义，返回一个类型是否存在于类型列表中（not in std)，其具体实现如下

1
2
3
4
5
6
7
8
template<typename T, typename  ...Args>
struct is_one_of; // only a declaration

template<typename T>
struct is_one_of<T> : false_type {}; // 递归基

template<typename T, typename U, typename ...Args>
struct is_one_of<T, U, Args...> : bool_constant<is_same<T, U>::value || is_one_of<T, Args...>::value> {};

如何使用is_one_of来实现is_void是非常显然的：
1
2
template<typename T>
struct is_void: is_one_of<T,void, const void, volatile void, const volatile void> {};

以上关于is_void的实现充分说明，类似于普通函数，模板元编程在实现过程中同样存在多种方案可供选择，并非仅有单一实践。

编译期判断

conditional

编译期同样存在if判断的需求与使用场景，例如某个模板类需要根据泛型参数T的具体属性来决定继承基类B1或B2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class B1 {
  ...// sth
};

class B2 {
  ...// sth
};

template<bool val, typename T, typename U>
struct conditional {
    using type = xxx;
};


template<typename T>
class D : public conditional<std::is_void<T>::value, B1, B2>::type {

};

其中conditional是一个标准的元编程实现，其作用为:val为true，则type == T，否则type == U。
显然，conditional的实现并无特别：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<bool val, typename T, typename>
struct conditional {
    using type = T;
};

template<typename T, typename U>
struct conditional<true, T, U> {
    using type = T;
};

template<typename T, typename U>
struct conditional<false, T, U> {
    using type = U;
};

enable_if

enable_if的实现基础来自于SFINAE，在TMP中使用非常广泛。
在实际开发工作中经常存在某种场景，即当前泛型函数仅应该支持符合条件的某些类型，其余类型应当在编译期触发报错，例如:

1
2
3
4
5
6
7
8
9
10
// 该模板函数接受参数：整形，浮点，string_view， xxx库提供的数组与字典结构
template <typename T,
          typename std::enable_if<
              std::is_same<T, std::string>::value ||
              std::is_same<T, xxx::string_view>::value || std::is_integral<T>::value ||
              std::is_floating_point<T>::value || std::is_same<T, xxx::Values>::value ||
              std::is_same<T, xxx::Dictionary>::value>::type * = nullptr>
void process(const std::string &s, const std::string &t, const T &val) {
  ... // do sth
}

enable_if有实现如下:
1
2
3
4
5
6
7
template<bool val>
struct enable_if {}; // nothing in struct

template<>
struct enable_if<true> {
    using type = void; // dont need use this type
};

模板元编程的实际应用

 

判断类型是否存在某个对外暴露的符号

简单介绍一下TMP在实际工程中的应用情况，例如：判断当前类型是否内含有某public member function或者pulic data member，思路和enable_if思路大致类似。
这里仅以如何判断当前类型存在拷贝赋值函数举例。

先验知识

decltype 与 declval
https://xander.wiki/2018/06/25/%E4%BA%86%E8%A7%A3decltype%E6%8A%80%E6%9C%AF/
https://stdrc.cc/post/2020/09/12/std-declval/
void_t
https://blog.csdn.net/ding_yingzi/article/details/79983042

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template<typename T>
using copy_assignment_t = decltype(std::declval<T &>());

template<typename T, typename = void>
struct has_copy_assignment : std::false_type {};

// in c++17 style
template<typename T>
struct has_copy_assignment<T, std::void_t<copy_assignment_t<T>>> : std::is_same<copy_assignment_t<T>, T &> {}; // 特化最优匹配

class A {};

class B {
    B &operator=(const B &) = delete;
};

int main() {
    static_assert(has_copy_assignment<A>::value, "A has copy assignment");
    static_assert(!has_copy_assignment<B>::value, "B has no copy assignment");
}

显然，如需检验某个类是否具备public data member，只需要更改decltype内的判断条件即可。