C++ Templates(5):编译时编程

1. 模版元编程

        模版在编译期实例化,这使得一些C++模版特性可以在实例化阶段进行一系列递归的语言编程。所以,我们可以使用模版来作为程序计算。

template<unsigned p, unsigned d>
struct DoIsPrime {
  static constexpr bool value =
    (p % d != 0) && DoIsPrime<p, d - 1>::value;
};

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

template<unsigned p>
struct IsPrime {
  static constexpr bool value =
    DoIsPrime<p, p / 2>::value;
};

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$ 会递归地展开表达式。例如:

IsPrime<9>::value

        会展开为:

DoIsPrime<9, 4>::value

        然后按照以下顺序继续展开:

9 % 4 != 0 && DoIsPrime<9, 3>::value

9 % 4 != 0 && 9 % 3 != 0 && DoIsPrime<9, 2>::value

9 % 4 != 0 && 9 % 3 != 0 && 9 % 2 != 0

        从而得到 $false$ ,于是 $9$ 不是质数。
        注意所有的这些运算都会在编译期完成。虽然模版语法很丑,但是它在一些库中被证实是有效的。

2. constexpr

        $constexpr$ 是C++11引入的新特性,极大地简化了多种形式的编译期运算。特别的,如果给予了合适的输入,$constexpr$ 函数可以在编译期就完成计算。在C++11中,$constexpr$ 函数有着严格的限制。在C++14,大部分限制都被移除了。当然,一个有效的 $constexpr$ 函数还是要求所有计算阶段在编译期都是可行且有效的。现阶段,堆分配或者抛出异常等行为还是不允许的。

constexpr bool doIsPrime(unsigned p, unsigned d) {
  return d != 2 ? (p % d != 0) && doIsPrime(p, d - 1)
                : (p % 2 != 0);
}

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

        上面是我们使用 $constexpr$ 函数实现的求质数。因为在C++11中,$constexpr$ 有着只能有一条语句的限制,所以我们只能使用三目运算符来选择分支,通过递归来遍历元素。但是因为它使用的是普通C++函数的代码,所以第一印象要比模版编程好。
        C++14中,$constexpr$ 函数可以使用更多的控制结构,所以与其使用笨重的模版代码或者神秘的一行代码,不如直接使用 $for$ 循环:

constexpr bool isPrime(unsigned int p) {
  for (unsigned int d = 2; d <= p / 2; d++) {
    if (p % d == 0) return false;
  }
  return p > 1;
}

        不管是C++11版本的还是C++14版本的,我们都能在入参是编译时常量的前提下,在编译期就完成计算。但是编译器不一定会这样做。如果上下文需要一个编译期常量 ( 比如数组长度或非类模版参数 ),编译器就会尝试让 $constexpr$ 函数在编译期计算,并且会在无法计算时报错。在其他情况下,如果不需要一个编译期常量,编译期可能会也可能不会在编译期计算,这时如果编译期计算失败,不会产生编译错误,而是变为一个运行时调用。例如:

constexpr bool b1 = isPrime(9);  // 编译期计算
const bool b2 = isPrime(9);  // 如果在命名空间内就在编译期计算

bool isfiftySevenIsPrime() {
  return isPrime(7);  // 编译期计算或者运行时计算
}

int x;
std::cout << isPrime(x);  // 运行时计算

3. 部分特例化的执行分支选择

        像 $isPrime$ 这种函数在编译期测试的一个有趣应用就是使用部分特例化来实现在编译时选择不同的实现版本。例如,我们可以根据模版参数是否是质数来选择:

template<int SZ, bool = isPrime(SZ)>
struct Helper;

template<int SZ>
struct Helper<SZ, false> {
  // ...
};

template<int SZ>
struct Helper<SZ, true> {
  // ...
};

template<typename T, std::size_t SZ>
long foo(std::array<T, SZ> const& coll) {
  Helper<SZ> h;
  // ...
}

        这里我们根据 $array$ 大小是否是质数来选择不同的 $Helper$ 特例化。这种使用部分特例化在一些根据参数属性来决定调用的方式在函数模版中被广泛使用。上面的代码中,我们列出了两种特例化情况。实际上,我们只需要列出一种就行了:

template<int SZ, bool = isPrime(SZ)>
struct Helper {
  // ...
};

template<int SZ>
struct Helper<SZ, true> {
  // ...
};

        由于函数模版不支持部分特例化,你必须使用其他机制来在特定条件下改变函数实现:

4. SFINAE

        对多种参数类型进行函数重载在C++中很常见。当编译期看到对重载函数的调用时,它必须考虑每个候选版本,检查参数然后选择最匹配的版本。如果这些候选版本内存在函数模版,编译期首先要去判断应该使用什么模版参数,然后使用这个参数代替函数参数和返回值类型,最后再将它像普通函数那样检查是否匹配。然而,这个替代的过程可能会产生问题,导致无意义的构造。为了避免这种无意义的构造产生的错误,C++语言规定了这种替代问题产生的错误会被忽略。这就是我们所说的SFINAE ( $substitution$ $failure$ $is$ $not$ $an$ $error$ ) 原则。
        注意这里所说替代过程与按照需求实例化是不同的,替代可能会在实例化的结果是不需要的结果时发生,从而编译器可以根据替代结果判断是需要还是不需要。

template<typename T, unsigned N>
std::size_t len(T (&)[N]) { return N; }

template<typename T>
typename T::size_type len(T const& t) {
  return t.size();
}

        这里我们定义了两个模版函数,它们都是 $len$ 的重载,第一个版本接收一个数组,第二个版本没有约束,但是要求类型具有 $size_-type$ 成员。

int a[10];
std::cout << len(a);  // 匹配数组
std::cout << len("tmp");  // 匹配数组

std::vector<int> v;
std::cout << len(v);  // 匹配size_type

int* p;
std::cout << len(p);  // 错误

std::allocator<int> x;
std::cout << len(x);  // 错误

        当我们传入数组时,虽然数组也能匹配 $T$ ,但无法匹配 $size_-type$ ,如果实例化会产生错误。对于原始指针,因为哪个模版都无法匹配,所以会产生一个错误。$std::allocator$ 虽然也具有 $size_-type$ 成员,但是因为没有 $size$ 函数,所以也会产生错误。
        忽略一个候选版本可能会导致编译期选择另一个更差匹配的版本,例如:

template<typename T, unsigned N>
std::size_t len(T (&)[N]) { return N; }

template<typename T>
typename T::size_type len(T const& t) {
  return t.size();
}

std::size_t len(...) { return 0; }

        我们提供了一个通用版本,有着最差的匹配,但是总是可以匹配,理论上这种后备函数应该抛出异常或者声明一个静态断言,输出有效的错误信息。这时,对于原始数组和 $vector$ ,有着更优的匹配。但是对于指针,只能匹配到通用版本。$allocator$ 会匹配第二版本和第三个版本,但是第二个版本是更优匹配,所以它还是会匹配第二个版本,虽然它会产生一个错误。
        随着时间的推移,SFINAE在模版设计中变得越来越重要和流行,并且这个缩写也变成了动词。如果我们想要通过SFINAE机制来确保一个函数模版会在特定条件下产生错误代码从而被忽略,我们会说"我们SFINAE了这个函数“。并且无论何时当你在C++标准库中读到某个函数模版注释着”最好不要作为重载函数解析除非…“时,意味着这个函数模版在特定条件下被SFINAE了。
        例如,$std::thread$ 声明了一个构造函数:

namespace std {
  class thread {
  public:
    template<typename F, typename... Args>
    explicit thread(F&& f, Args&&... args);
  // ...
  };
}

        这段代码有着以下的注释:

注释:如果 $decay_-t$<$F$> 的类型与 $std::thread$ 相同,这个构造函数最好不要作为重载函数解析。

        这意味着如果将 $std::thread$ 作为第一个模版参数传入,这个模版构造函数会被忽略。因为有时候这种类似的成员函数比起预定义的拷贝或者移动构造函数有着更优的匹配。通过SFINAE $thread$ 的模版构造函数,我们可以确保在接收另一个 $thread$ 作为参数的情况下预定义的拷贝或者移动构造函数总是会被调用。
        在这种就事论事的情况下使用这项技术可能显得有些笨重。幸运的是,标准库提供了更方便的禁用模版的工具。这些工具中,我们最熟悉的就是 $std::enable_-if$ 了。因此,$std::thread$ 构造函数的一个典型声明为:

namespace std {
  class thread {
  public:
    template<typename F, typename... Args,
             typename = enable_if_t<!is_same_v<decay_t<F>,
                                    thread>>>
    explicit thread(F&& f, Args&&... args);
    // ...
  };
}

4.1 使用decltypeSFINAE表达式

        编写一条在特定条件下正确SFINAE函数模版的表达式是不简单的。例如,我们想要确保函数模版 $len$ 在模版参数具有 $size_-type$ 成员但是没有 $size$ 函数成员时忽略,从而避免类似于 $allocator$ 的错误。有一个通用模版可以处理这种情况:

        例如:

template<typename T>
auto len(T const& t)
-> decltype((void)(t.size()), T::size_type()) {
  return t.size();
}

        $decltype$ 使用逗号分离的表达式列表,最后一个表达式 $T::size_-type(\ )$ 表示真正的返回类型,而在最后一个逗号之前的表达式必须是有效的。我们将第一个表达式的运算结果转为 $void$ ,用于避免用户重载逗号运算符带来的问题。
        注意 $decltype$ 参数是一个没有计算的操作,这意味着我们可以创建一个不调用构造函数的虚拟对象。

5. 编译时if

        部分特例化、SFINAE和 $std::enable_-if$ 一起使用,可以让我们启用或禁用模版。C++17额外引入了编译时 $if$ 语句,允许根据编译时条件来启用或者禁用某些特定语句。使用 $if$ $constexpr$ ,编译器可以在编译期通过表达式确定进入 $then$ 分支还是 $else$ 分支。

template<typename T, typename... Types>
void print(T const& firstArg, Types const&... args) {
  std::cout << firstArg << '\n';
  if constexpr(sizeof...(args) > 0) {
    print(args...);
  }
}

        这里如果 $print$ 只接收了一个参数,那么 $if$ 表达式将为 $false$ ,从而不会继续递归,并且代码也不会实例化。
        代码不会实例化意味着只会进行第一个翻译阶段 ( 定义阶段 ),这时检查不依赖于模版参数的代码正确性。

template<typename T>
void foo(T t) {
  if constexpr(Std::is_integral_v<T>) {
    if (t > 0) foo(t - 1);
  } else {
    undeclared(t);  // 如果没有声明并且进入else分支,错误
    undeclared();  // 如果没有声明,即使未进入else分支也会错误
    static_assert(false, "no integral");  // 总是会判断,即使未进入else分支
    static_assert(!std::is_integral_v<T>, "no integral");
  }
}

        注意 $if$ $constexpr$ 语句可以在任何函数中使用,不局限于模版。

int main() {
  if constexpr(std::numeric_limits<char>::is_signed) {
    foo(42);
  } else {
    undeclared(42);  // 如果没有声明,错误
    static_assert(false, "unsigned");  // 即使未进入else分支也会判断
    static_assert(!std::numeric_limits<char>::is_signed,
                  "char is unsigned");
  }
}

C++ Templates(5):编译时编程