第八章：模板元编程

模板是在编译时实例化的。C++ 的某些功能可以与实例化过程结合，成为一种原始的递归“编程语言”。C++ 有多种功能来支持编译器编程。

• c98 开始，template 赋予了C++编译期间运算的能力，包括循环和执行分支选择。初步支持了模板元编程，但是语法非常晦涩。

• 通过模板特化可以为不同的参数实现不同的功能

• 通过 SFINAE (Substitution Failure Is Not An Error ) 原则，可以通过匹配模板函数选择不同的实现分支

• c11 引入了 constexpr，可以用于声明函数，简化了模板元编程语法。

• c14 让模板元编程支持 if, for, switch 等语法。

8.1 模板元编程

我们以一个判断一个数是否是质数的函数为例子讲解模板元编程。以下给出了最原始的基于 c98 版本的实现。

基本思路是通过模板特化生成很多个类，每个类的参数是数字以及被除数，并提供一个值 value 来表示是否是质数。

// p: number to test if it is a prime, d: divisor
template<unsigned p, unsigned d>
struct DoIsPrime {
  static constexpr bool value = (p%d != 0) && DoIsPrime<p, d-1>::value;
};

// specialize for d = 2
template<unsigned p>
struct DoIsPrime<p,2> {
  static constexpr bool value = (p%2 != 0);
};


// start recursive process from n/2
// ideally sqrt(n), but not supported in compile time
template<unsigned p>
struct IsPrime {
  static constexpr bool value = DoIsPrime<p, p/2>::value;
};

// end condition
template<>
struct IsPrime<0> {
  static constexpr bool value = false;
};

template<>
struct IsPrime<1> {
  static constexpr bool value = false;
};

template<>
struct IsPrime<2> {
  static constexpr bool value = true;
};

template<>
struct IsPrime<3> {
  static constexpr bool value = true;
};

核心代码是递归调用（生成类型DoIsPrime<p, d-1>），直到终止条件 d = 2。中途发现任何可以整除的数字，即返回不是质数。

// p: number to test if it is a prime, d: divisor
template<unsigned p, unsigned d>
struct DoIsPrime {
  static constexpr bool value = (p%d != 0) && DoIsPrime<p, d-1>::value;
};

这个语法非常晦涩，而且要求使用 struct 而不能使用函数实现。但是揭示了模板元编程的本质。

8.2 使用 constexpr 简化

c++11 引入了 constexpr，可以在编译器计算表达式（甚至函数）的值。但是限制是：无法使用堆、无法抛出异常、仅支持一行表达式。

利用 constexpr，我们可以把上面冗长的代码简化为简单的两个函数：

// c11 introduced constexpr, but supports only 1 statement
// this is the reason of using ternary operator
constexpr bool
doIsPrime(unsigned p, unsigned d)
{
  return d==2 ? (p%d != 0) :
                (p%d != 0) && doIsPrime(p, d-1);
}

constexpr bool
isPrime(unsigned p)
{
  return (p<3) ? p == 2 : doIsPrime(p, p/2);
}

值得注意的是，c11 中 constexpr 只支持一行语句。因此，我们的函数都利用三元操作符? A:B 强行缩减成了一行。

自 c14 开始，constexpr修饰的函数可以使用大部分的控制语句 if，for，switch。因此可以改成更加自然的形式：

// "if" is supported from c14
constexpr bool
doIsPrime(unsigned p, unsigned d)
{
  if (d == 2) {
    return p % 2 == 0;
  }
  return (p%d != 0) && doIsPrime(p, d-1);
}

constexpr bool
isPrime(unsigned p)
{
  if (p < 2) {
    return false;
  }

  if (p == 2 || p == 3) {
    return true;
  }
  
  return doIsPrime(p, p / 2);
}

8.4 SFINAE

C++ 中函数的重载（overload）非常普遍。当编译器处理一个重载函数调用时，它需要分别考虑所有备选项并选择最匹配的一个。

编译器首先需要决定用什么模板参数，然后替换这些参数，并比较匹配程度。但是，替换的过程可能会产生错误的或者无意义的结果。编译器会忽略这种错误。

这就被称为 SFINAE (Substitution Failure Is Not An Error) 原则。