CPP-Templates-2nd--第 23 章元编程

23.1 现代 C++元编程的现状

2.3.1.1 值元编程（Value Metaprogramming）

23.1.2 类型元编程

23.1.3 混合元编程

23.1.4 将混合元编程用于“单位类型”

23.2 反射元编程的维度

23.3 递归实例化的代价

23.3.1 追踪所有的实例化过程

23.4 计算完整性

23.5 递归实例化和递归模板参数

23.6 枚举值还是静态常量

参考：GitHub - Walton1128/CPP-Templates-2nd--: 《C++ Templates 第二版》中文翻译，和原书排版一致，第一部分（1至11章）以及第18，19，20，21、22、23、24、25章已完成，其余内容逐步更新中。个人爱好，发现错误请指正

元编程的意思是“编写一个程序”。也就是说，我们构建了可以被编程系统用来产生新代码的代码，而且新产生的代码实现了我们真正想要的功能。通常名词“元编程”暗示了一种自反的属性：元编程组件是其将要为之产生一部分代码的程序的一部分（比如，程序中一些附加的或者不同的部分）。

为什么需要元编程？和其它编程技术一样，目的是用尽可能少的“付出”，换取尽可能多的功能，其中“付出”可以用代码长度、维护成本之类的事情来衡量。元编程的特性之一是在编译期间（at translation time，翻译是否准确？）就可以进行一部分用户定义的计算。其动机通常是性能（在 translation time 执行的计算通常可以被优化掉）或者简化接口（元-程序通常要比其展开后的结果短小一些），或者两者兼而有之。

23.1 现代 C++元编程的现状

2.3.1.1 值元编程（Value Metaprogramming）

比如在 C++14 中，一个在编译期计算平方根的函数可以被简单的写成这样：

template<typename T>
constexpr T sqrt(T x)
{
// handle cases where x and its square root are equal as a special
case to simplify
// the iteration criterion for larger x:
if (x <= 1) {
return x;
}// repeatedly determine in which half of a [lo, hi] interval the square
root of x is located,
// until the interval is reduced to just one value:
T lo = 0, hi = x;
for (;;) {
auto mid = (hi+lo)/2, midSquared = mid*mid;
if (lo+1 >= hi || midSquared == x) {
// mid must be the square root:
return mid;
}
//continue with the higher/lower half-interval:
if (midSquared < x) {
lo = mid;
} else {
hi = mid;
}
}
}

上面介绍的值元编程（比如在编译期间计算某些数值）偶尔会非常有用，但是在现代 C++中还有另外两种可用的元编程方式（在 C++14 和 C++17 中）：类型元编程和混合元编程。

23.1.2 类型元编程

在第 19 章中实现的例子只会计算很初级的类型操作。通过递归的模板实例化-- 这也是主要的基于模板的元编程手段--我们可以实现更复杂的类型计算。

考虑如下例子：

// primary template: in general we yield the given type:
template<typename T>
struct RemoveAllExtentsT {
using Type = T;
};
// partial specializations for array types (with and without bounds):
template<typename T, std::size_t SZ>
struct RemoveAllExtentsT<T[SZ]> {
using Type = typename RemoveAllExtentsT<T>::Type;
};
template<typename T>
struct RemoveAllExtentsT<T[]> {
using Type = typename RemoveAllExtentsT<T>::Type;
};
template<typename T>
using RemoveAllExtents = typename RemoveAllExtentsT<T>::Type;

这里 RemoveAllExtents 就是一种类型元函数（比如一个返回类型的计算设备），它会从一个类型中移除掉任意数量的顶层“数组层”。就像下面这样：

RemoveAllExtents<int[]> // yields int
RemoveAllExtents<int[5][10]> // yields int
RemoveAllExtents<int[][10]> // yields int
RemoveAllExtents<int(*)[5]> // yields int(*)[5]

元函数通过偏特化来匹配高层次的数组，递归地调用自己并最终完成任务。

如果数值计算的功能只适用于标量，那么其应用会很受限制。幸运的是，几乎有所得语言都至少有一种数值容器，这可以大大的提高该语言的能力（而且很多语言都有各种各样的容器，比如 array/vector，hash table 等）。

对于元编程也是这样：增加一个“类型容器”会大大的提高其自身的适用范围。幸运的是，现代 C++提供了可以用来开发类似容器的机制。第 24 章开发的 Typelist类模板，就是这一类型的类型容器。

23.1.3 混合元编程

通过使用数值元编程和类型元编程，可以在编译期间计算数值和类型。

但是最终我们关心的还是在运行期间的效果，因此在运行期间的代码中，我们将元程序用在那些需要类型和常量的地方。不过元编程能做的不仅仅是这些：我们可以在编译期间，以编程的方式组合一些有运行期效果的代码。我们称之为混合元编程。

下面通过一个简单的例子来说明这一原理：计算两个 std::array 的点乘结果。

template<typename T, std::size_t N>
auto dotProduct(std::array<T, N> const& x, std::array<T, N>
const& y)
{
T result{};
for (std::size_t k = 0; k<N; ++k) {
result += x[k]*y[k];
}
return result;
}

如果对 for 循环进行直接编译的话，那么就会生成分支指令，相比于直接运行如下命令，这在一些机器上可能会增加运行成本：（如果对 for 循环进行直接编译，生成的汇编代码可能会包含分支指令。这是因为在每次迭代中，循环的条件（k < N）需要进行比较，以确定是否继续执行循环体。在某些机器上，这种分支指令可能会增加运行成本。）

result += x[0]*y[0];
result += x[1]*y[1];
result += x[2]*y[2];
result += x[3]*y[3]; …

这将消除循环的条件判断和迭代过程，从而避免了分支指令。在某些情况下，这样的代码可能在某些机器上执行得更快，因为它可以更好地利用流水线和指令级并行性。

下面重新实现一版不需要 loop 的 dotProduct():

template<typename T, std::size_t N>
struct DotProductT {
static inline T result(T* a, T* b)
{
return *a * *b + DotProduct<T, N-1>::result(a+1,b+1);
}
};
// partial specialization as end criteria
template<typename T>
struct DotProductT<T, 0> {
static inline T result(T*, T*) {
return T{};
}
};
template<typename T, std::size_t N>
auto dotProduct(std::array<T, N> const& x,
std::array<T, N> const& y)
{
return DotProductT<T, N>::result(x.begin(), y.begin());
}

新的实现将计算放在了类模板 DotProductT 中。这样做的目的是为了使用类模板的递归实例化来计算结果，并能够通过部分特例化来终止递归。注意例子中 DotProductT 的每一次实例化是如何计算点乘中的一项结果、以及所有剩余结果的。对于 std::arrat，会对主模板进行 N 次实例化，对部分特例化的模板进行一次实例化。为了保证效率，编译期需要将每一次对静态成员函数 result()的调用内联（inline）。

这段代码的主要特点是它融合了编译期计算（这里通过递归的模板实例化实现，这决定了代码的整体结构）和运行时计算（通过调用result()，决定了具体的运行期间的效果）。

（

递归替代循环：代码使用递归而不是显式的循环来计算点积。通过递归调用模板特化的结构体，它能够在编译期间展开，并在每次递归中计算部分点积。这种递归的方式可以避免循环中的分支指令，并且在某些情况下可能具有更好的性能。
在 DotProductT 结构体模板中，点积计算通过递归调用 DotProductT 的 result 静态成员函数来实现。在每次递归调用中，它计算当前元素的乘积，并将其与下一个元素的乘积相加，以逐步计算点积。这个递归过程在编译期间展开，并在编译期间完成点积的计算。
在 dotProduct 函数中，它通过调用 DotProductT<T, N>::result 来触发编译期计算。该函数接受两个 std::array 的引用作为参数，并将它们的迭代器传递给 DotProductT 的 result 函数。这个函数调用发生在运行时，并返回已计算的点积结果。

）

我们之前提到过，“类型容器”可以大大提高元编程的能力。我们同样看到固定长度的 array 在混合元编程中也非常有用。但是混合元编程中真正的“英雄容器”是 tuple（元组）。Tuple 是一串数值，且其中每个值的类型可以分别指定。C++标准库中包含了支持这一概念的类模板 std::tuple。比如：

std::tuple<int, std::string, bool> tVal{42, "Answer", true};

定义的变量 tVal 包含了三个类型分别为 int, std::string 和 bool 的值。因为 tuple 这一类容器在现代 C++编程中非常重要，我们将在第 25 章对其进行更深入的讨论。tVal 的类型和下面这个简单的 struct 类型非常类似：

struct MyTriple {
int v1;
std::string v2;
bool v3;
};

既然对于 array 类型和（简单）的 struct 类型，我们有比较灵活的 std::array 和 std::tuple 与之对应，那么你可能会问，与简单的 union 对应的类似类型是否对混合元编程也很有益。答案是“yes”。C++标准库在 C++17 中为了这一目的引入了 std::variant 模板，在第 26 章中我们会介绍一个类似的组件。

由于 std::tuple 和 std::variant 都是异质类型（与 struct 类似），使用这些类型的混合元编程有时也被称为“异质元编程”。

23.1.4 将混合元编程用于“单位类型”

另一个可以展现混合元编程威力的例子是那些实现了不同单位类型的数值之间计算的库。相应的数值计算发生在程序运行期间，而单位计算则发生在编译期间。

下面会以一个极度精简的例子来做讲解。我们将用一个基于主单位的分数来记录相关单位。比如如果时间的主单位是秒，那么就用 1/1000 表示 1 微秒，用 60/1 表示一分钟。因此关键点就是要定义一个比例类型，使得每一个数值都有其自己的类型：

#include<iostream>
using namespace std;
template<unsigned N, unsigned D = 1>
struct Ratio {static constexpr unsigned num = N; // numeratorstatic constexpr unsigned den = D; // denominatorusing Type = Ratio<num, den>;
};
// implementation of adding two ratios:
template<typename R1, typename R2>
struct RatioAddImpl
{
private:static constexpr unsigned den = R1::den * R2::den;static constexpr unsigned num = R1::num * R2::den + R2::num *R1::den;
public:typedef Ratio<num, den> Type;
};
// using declaration for convenient usage:
template<typename R1, typename R2>
using RatioAdd = typename RatioAddImpl<R1, R2>::Type;
int main() {using R1 = Ratio<1, 1000>;using R2 = Ratio<2, 3>;using RS = RatioAdd<R1, R2>; //RS has type Ratio<2003,2000>std::cout << RS::num << "/" << RS::den <<"\n"; //prints 2003/3000using RA = RatioAdd<Ratio<2, 3>, Ratio<5, 7>>; //RA has type	Ratio<29, 21>std::cout << RA::num << '/' << RA::den << '\n'; //prints 29/21return 0;
}

然后就可以为时间段定义一个类模板，用一个任意数值类型和一个 Ratio<>实例化之后的类型作为其模板参数：

// duration type for values of type T with unit type U:
template<typename T, typename U = Ratio<1>>
class Duration {
public:using ValueType = T;using UnitType = typename U::Type;
private:ValueType val;
public:constexpr Duration(ValueType v = 0): val(v) {}constexpr ValueType value() const {return val;}
};
// adding two durations where unit type might differ:
template<typename T1, typename U1, typename T2, typename U2>
auto constexpr operator+(Duration<T1, U1> const& lhs,Duration<T2, U2> const& rhs)
{// resulting type is a unit with 1 a nominator and// the resulting denominator of adding both unit type fractionsusing VT = Ratio<1, RatioAdd<U1, U2>::den>;// resulting value is the sum of both values// converted to the resulting unit type:auto val = lhs.value() * VT::den / U1::den * U1::num +rhs.value() * VT::den / U2::den * U2::num;return Duration<decltype(val), VT>(val);
}

这里参数所属的单位类型可以不同，比如分别为 U1 和 U2。然后可以基于 U1 和 U2 计算最终的时间段，其类型为一个新的分子为 1 的单位类型。基于此，可以编译如下代码：

int x = 42;
int y = 77;
auto a = Duration<int, Ratio<1,1000>>(x); // x milliseconds
auto b = Duration<int, Ratio<2,3>>(y); // y 2/3 seconds
auto c = a + b; //computes resulting unit type 1/3000 seconds//and
generates run-time code for c = a*3 + b*2000

此处“混合”的效果体现在，在计算 c 的时候，编译器会在编译期决定结果的单位类型 Ratio，并产生出可以在程序运行期间计算最终结果的代码（结果会被根据单位类型进行调整）。

由于数值类型是由模板参数决定的，因此可以将 int 甚至是异质类型用于 Duration 类：

auto d = Duration<double, Ratio<1,3>>(7.5); // 7.5 1/3 seconds
auto e = Duration<int, Ratio<1>>(4); // 4 seconds
auto f = d + e; //computes resulting unit type 1/3 seconds
// and generates code for f = d + e*

而且如果相应的数值在编译期是已知的话，编译器甚至可以在编译期进行以上计算（因为上文中的 operator+是 constexpr）。

23.2 反射元编程的维度

无论如何，我们已经看到元编程的计算引擎可以有多种潜在的选择。但是计算不是唯一的一个我们应该在其中考虑相关选项的维度。

一个综合的元编程解决方案应该在如下 3 个维度中间做选择：

 计算维度（Compution）

 反射维度（Reflection）

 生成维度（Generation）

反射维度指的是以编程的方式检测程序特性的能力。生成维度指的是为程序生成额外代码的能力。

来自gpt：

计算维度（Computation）：计算维度涉及在编译期间执行计算操作的能力。这意味着能够在编译时进行常量表达式求值、类型推导、类型转换等运算，以生成在运行时可直接使用的结果。计算维度的元编程解决方案可以通过模板元编程、constexpr 函数、编译期函数求值等实现。
反射维度（Reflection）：反射维度涉及在编译期间获取和操作程序的类型信息的能力。这意味着能够查询类型的成员变量、成员函数、基类、派生类等信息，并对其进行动态调用、修改、创建等操作。反射维度的元编程解决方案可以通过模板元编程、类型 traits、编译期类型信息收集等实现。
生成维度（Generation）：生成维度涉及在编译期间生成代码的能力。这意味着能够根据特定的规则和模板，生成新的类型、函数、类成员等代码，并将其编译为可执行的程序。生成维度的元编程解决方案可以通过模板元编程、代码生成技术、宏展开等实现。

虽然一些可用的类型萃取使得某些高端的模板技术变得可能，但是这远没有包含所有的、我们所期望能够从反射机制中获得的特性。比如给定一个类，一些应用总是倾向于在程序中访问其某些成员。

来自gpt:

(反射机制通常指的是在程序运行时获取和操作类型信息的能力，包括动态查询和调用成员、动态创建对象、修改类型结构等。这种能力通常需要语言本身提供支持，例如C++的运行时类型信息（RTTI）机制。

因此，尽管类型萃取技术在某些情况下可以实现类似于反射的功能，但它们并不能代替完整的反射机制所提供的所有特性。对于某些特定的需求和场景，我们可能仍然需要使用其他的反射机制，或者采用额外的工具和库来实现更全面的反射功能。)

23.3 递归实例化的代价

23.3.1 追踪所有的实例化过程

上文中主要分析了被用来计算 16 的平方根的实例化过程。但是当编译期计算：

(16<=8*8) ? Sqrt<16,1,8>::value
: Sqrt<16,9,16>::value

的时候，它并不是只计算真正用到了的分支，同样也会计算没有用到的分支

（Sqrt<16,9,16>）。

而且，由于代码试图通过运算符::访问最终实例化出来的类的成员，该类中所有的成员都会被实例化。

仔细分析以上过程，会发现最终会实例化出很多的实例，数量上几乎是 N的两倍。

幸运的是，有一些技术可以被用来降低实例化的数目。为了展示其中一个重要的技术，我们按照如下方式重写了 Sqrt 元程序：

#include "ifthenelse.hpp"
// primary template for main recursive step
template<int N, int LO=1, int HI=N>
struct Sqrt {
// compute the midpoint, rounded up
static constexpr auto mid = (LO+HI+1)/2;
// search a not too large value in a halved interval
using SubT = IfThenElse<(N<mid*mid),
Sqrt<N,LO,mid-1>,
Sqrt<N,mid,HI>>;
static constexpr auto value = SubT::value;
};
// partial specialization for end of recursion criterion
template<int N, int S>
struct Sqrt<N, S, S> {
static constexpr auto value = S;
};

代码中主要的变化是使用了 IfThenElse 模板，在第 19.7.1 节有对它的介绍。回忆一下， IfThenElse 模板被用来基于一个布尔常量在两个类型之间做选择。如果布尔型常量是 true，那么会选择第一个类型，否则就选择第二个类型。一个比较重要的、需要记住的点是：为一个类模板的实例定义类型别名，不会导致 C++编译器去实例化该实例。因此使用如下代码时：

using SubT = IfThenElse<(N<mid*mid),
Sqrt<N,LO,mid-1>,
Sqrt<N,mid,HI>>;

既不会完全实例化 Sqrt<N,LO,mid-1> 也不会完全实例化 Sqrt<N,mid,HI>。

在调用 SubT::value 的时候，只有真正被赋值给 SubT 的那一个实例才会被完全实例化。和之前的方法相比，这会让实例化的数量和 log2N 成正比：当 N 比较大的时候，这会大大降低元程序实例化的成本。

23.4 计算完整性

从以上的 Sqrt<>的例子可以看出，一个模板元程序可能会包含以下内容：

 状态变量：模板参数

 循环结构：通过递归实现

 执行路径选择：通过条件表达式或者偏特例化实现

 整数运算

如果对递归实例化的数量和使用的状态变量的数量不做限制，那么就可以用之来计算任何可以计算的事情。尽管这样做可能不是很方便。而且，由于模板实例化需要大量的编译器资源，大量的递归实例化会很快地降低编译器地编译速度，甚至是耗尽可用地硬件资源。C++标准建议最少应该支持 1024 层的递归实例化，但是并没有强制如此，但是这应该足够大部分（当然不是全部）模板元编程任务使用了。

23.5 递归实例化和递归模板参数

template<typename T, typename U>
struct Doublify {
};
template<int N>
struct Trouble {
using LongType = Doublify<typename Trouble<N-1>::LongType,
typename Trouble<N-1>::LongType>;
};
template<>
struct Trouble<0> {
using LongType = double;
};
Trouble<10>::LongType ouch;

在组织递归实例化代码的时候，最好不要让模板参数也嵌套递归。

23.6 枚举值还是静态常量

不过在 C++中，引入了 constexpr 静态数据成员，并且其使用不限于整型类型。这并没有解决上文中关于地址的问题，但是即使如此，它也是用来产生元程序结果的常规方法。其优点是，它可以有正确的类型（相对于人工的枚举类型而言），而且当用 auto 声明静态成员的类型时，可以对其类型进行推断。C++17 则引入了 inline 的静态数据成员，这解决了上面提到的地址问题，而且可以和 constexpr 一起使用。