C++ TMP

https://www.jianshu.com/p/b56d59f77d53

模板基础

模板的模板参数

可以接受模板作为参数的类模板：

#include <iostream>
#include <vector>
#include <queue>
#include <stdexcept>

template<typename T,
         template<typename U, typename Allocator = std::allocator<U>> class Container = std::vector>
struct Stack {
    void push(const T& elem) {
        elems.push_back(elem);
    }

    T pop() {
        if(empty()) throw std::out_of_range("Stack<>::pop: empty!");

        auto elem = elems.back();
        elems.pop_back();
        return elem;
    }

    bool empty() const {
        return elems.empty();
    }

private:
    Container<T> elems;
};

int main() {
    Stack<int, std::vector> intStack;
    intStack.push(1);
    std::cout << intStack.pop() << std::endl;

    Stack<double, std::deque> doubleStack;
    doubleStack.push(2.2f);
    std::cout << doubleStack.pop() << std::endl;

}

第二个模板参数要求支持 back，push_back，pop_back 等接口，对模板参数的约束后来演变出了概念库。

模板的特化

我们自定义一个容器 Array，但它只有 put 和 get 接口：

template<typename T, typename Allocator = std::allocator<T>>
struct Array {
    Array(size_t _size) : capacity{_size} {
        elems = new T(capacity * sizeof(T));
    }

    void put(size_t index, const T& t) {
        if (index >= capacity) throw std::out_of_range("Array<>::put: index out of range!");
        elems[index] = t;
    }

    T get(size_t index) {
        if (index >= capacity) throw std::out_of_range("Array<>::get: index out of range!");
        return elems[index];
    }

    ~Array() {
        delete[] elems;
        elems = nullptr;
    }

private:
    size_t capacity;
    T *elems;
};

为了让 Array 也能参与实现 Stack，我们可以对 Stack 进行（偏）特化：

template<typename T>
struct Stack<T, Array> {
    Stack(size_t _size = 0) : size{0}, elems{_size}
    {}

    void push(const T& elem) {
        elems.put(size++, elem);
    }

    T pop() {
        if(empty()) throw std::out_of_range("Stack<Array>::pop: empty!");
        return elems.get(--size);
    }

    bool empty() const {
        return size == 0;
    }

private:
    size_t size;
    Array<T> elems;
};

对于模板的特化，只需要其签名（模板名和模板参数）和主模板保持一致，即 typename T, typename Allocator = std::allocator<T>>。而对于其实现，和主模板以及其它特化版本的实现没有任何关系，完全可以根据该特化版本的需要进行定制。

若为全特化，由于不再存在非具体类型，所以尖括号中为空，但是不能省略，皆以 template <> 开头。

模板可以被嵌套地定义在一个类中或模板中，但是模板的特化不可以。

非类型参数

模板的参数支持以下类型：

类型参数：使用 typename 或者 class 指示
非类型参数：整型常量（包括 enum），或者指向外部链接的指针（包括函数指针、类的成员函数指针，以及具有外部链接的字符串常量指针）
模板参数：使用 template<...> class XXX 的形式指示

编译时计算

数值计算

为了验证计算发生在编译时，而编译器又无法操控输入输出，我们需要设法让编译器将计算结果在编译信息中打印出来：

#include <iostream>

template <int X, int Y>
struct Plus {
    enum { Value = X + Y };
};

template<int Value>
struct Print {
    operator char() {
        return Value + 0xFF; // INVOKE OVERFLOW WARNNING LOG !
    }
};

#define __print(...) char UNIQUE_NAME(print_value_) = Print<__VA_ARGS__>()

#define __DO_JOIN(x, y) x##y
#define _JOIN(x, y) __DO_JOIN(x, y)
#define UNIQUE_NAME(prefix) _JOIN(prefix, __LINE__)

__print(Plus<3, 4>::Value);

int main() {
    std::cout << Plus<1, 2>::Value << std::endl;
}

可以看到编译器的警告信息：

/home/vgalaxy/Templates/cpptest/main.cpp: In instantiation of ‘Print<Value>::operator char() [with int Value = 7]’:
/home/vgalaxy/Templates/cpptest/main.cpp:19:1:   required from here
/home/vgalaxy/Templates/cpptest/main.cpp:9:22: warning: overflow in conversion from ‘int’ to ‘char’ changes value from ‘262’ to ‘'\006'’ [-Woverflow]
    9 |         return Value + 0xFF; // INVOKE OVERFLOW WARNNING LOG !
      |                ~~~~~~^~~~~~

为了触发这个警告信息，我们需要将 Plus<3, 4>::Value 作为 Print 的模板参数，赋值给一个唯一的 char 型变量（通过宏实现），从而触发隐式类型转换函数，其中通过加上 char 的最大值触发 char 类型值溢出。

这里宏的连接套了两层，可以参见下面的例子：

#include <stdio.h>

#define __DO_JOIN(x, y) x##y
#define _JOIN(x, y) __DO_JOIN(x, y)

#define ID 201250012
const int PREFIX_ID = 201250012;
const int PREFIX_201250012 = 201250013;

int main() {
    printf("%d\n", _JOIN(PREFIX_, ID));
    printf("%d\n", __DO_JOIN(PREFIX_, ID));
}

其输出为：

201250013
201250012

类型计算

模板的类型计算结果如果保存在模板内部定义的嵌套类型中，这将会为模板计算提供封装性和信息隐藏的能力。

#include <iostream>

template<typename T>
struct PointerOf {
    using Type = T*;
};

int main() {
    PointerOf<const char>::Type p = "Hello";
    std::cout << p << std::endl;
}

using / typedef

应熟悉这种范式

递归计算

通过模板特化来终止递归

#include <iostream>

template<int N>
struct Factorial {
    enum { Value = N * Factorial<N - 1>::Value };
};

template<>
struct Factorial<1> {
    enum { Value = 1 };
};

int main() {
    std::cout << Factorial<10>::Value << std::endl;
}

当然也可以通过函数模板来实现，将参数信息转移到编译时的模板中，而不是运行时的栈中：

template <int N>
constexpr int factorial() {
    if constexpr (N == 0) {
        return 1;
    } else {
        return N * factorial<N - 1>();
    }
}

使用上述的 __print 来验证

模板元编程

元函数

我们演化之前类型的计算的例子，通过 PointerOf 构造 Pointer2Of

#include <iostream>

template<typename T>
struct PointerOf {
    using Result = T*;
};

template<typename T>
struct Pointer2Of {
    using Result = typename PointerOf<typename PointerOf<T>::Result>::Result;
};


int main() {
    PointerOf<const char>::Result p = "Hello";
    std::cout << p << std::endl;
    Pointer2Of<const char>::Result q = &p;
    std::cout << *q << std::endl;
}

一旦 PointerOf 后面的尖括号中存在非具体类型的话，那么 PointerOf 的内部类型 Result 就是一个推导类型。C++ 标准要求使用推导类型前面必须使用 typename 关键字显示指明这是一个类型。

后续我们将一直把这种在编译期进行计算，靠 Result 返回计算结果的类模板看作是编译期的函数，它的目的是为了支持 C++ 模板元编程。为了和 C++ 运行时函数进行区分，后文中我们统一将其称作元函数。

元函数和普通函数的对应关系：

参数：
- 元函数 <>
- 普通函数 ()
调用：
- 元函数 ::Result
- 普通函数 ()

若不调用，元函数类似于运行时的函数指针，仅用做保存和传递用，但并不求值。

高阶函数

我们想要一种能够任意指定指针层数的元函数

下面我们实现了一个通用的 Times 元函数，它可以对一个指定类型 T 反复调用另一个元函数 N 次：

template<int N, typename T, template<typename> class Func>
struct Times {
    using Result = typename Func<typename Times<N - 1, T, Func>::Result>::Result;
};

template<typename T, template<typename> class Func>
struct Times<1, T, Func> {
    using Result = typename Func<T>::Result;
};

可以这样使用 Times

template<int N, typename T>
using PointerNOfRes = typename Times<N, T, PointerOf>::Result;

也可以这样

template<int N, typename T>
using PointerNOf = Times<N, T, PointerOf>;

也可以这样

template<typename T>
using Pointer3Of = Times<3, T, PointerOf>;

某种程序上这正是对元函数 Times 的 Currying 操作

记住推导类型需要加上 typename 关键字

高阶函数除了允许函数的参数是函数，还允许函数的返回值也是函数。对于 C++，我们利用可以在类或者模板里面嵌套定义模板的特性，来实现元函数的返回值是元函数。

template<typename T>
struct MakePointerNOf {
    template<int N>
    using Result = PointerNOf<N, T>;
};

template<int N>
using PointerNOfConstChar = MakePointerNOf<const char>::template Result<N>;

可以这样使用：

    PointerNOfConstChar<3>::Result r = &q;
    std::cout << **r << std::endl;

其中 q 的类型为 const char **

不过这相当于显式展开了部分应用的过程，并且限制了部分应用的顺序。比如下面无法通过编译：

template<typename T>
using Pointer3Of = MakePointerNOf<T>::template Result<3>;

猜测：因为外层元函数还没有求值好，无法保存内层元函数的非类型参数

由于 C++ 标准不允许在类或者模板的内部定义模板的特化，一旦我们定义的内部元函数使用了模板特化，那么就必须定义在外面，再由原来的外层元函数引用

一切都是类型

下面我们实现一个能够判断两个类型是否相等的元函数：

#include <iostream>

template<typename T, typename U>
struct IsEqual {
    enum {Result = false};
};

template<typename T>
struct IsEqual<T, T> {
    enum {Result = true};
};

#define __is_eq(x, y) IsEqual<x, y>::Result

int main() {
    std::cout << __is_eq(int * const, const int *) << std::endl;
}

使用宏优化一下，效果和 C++ 中的 type_traits 库已经殊无二致了

原理：使用模式特化，当两个类型相等时，选择特化版本，否则选择非特化版本。

然而，若要判断两个数值是否相等，由于元函数不支持函数重载，所以必须得为这两个元函数起不同的函数名称。

另外，我们之前一直用 Result 表示返回类型，现在又用它返回数值。这种返回型别上的差异，会让我们在函数组合的时候碰到不少问题。

为此，我们需要用类型来表示数值，从而统一元函数的参数和返回值。

template<int V>
struct IntType {
    enum { Value = V };
    using Result = IntType<V>;
};

template<bool V> struct BoolType;

template<>
struct BoolType<true> {
    enum { Value = true };
    using Result = BoolType<true>;
};

template<>
struct BoolType<false> {
    enum { Value = false };
    using Result = BoolType<false>;
};

using TrueType = BoolType<true>;
using FalseType = BoolType<false>;

目前我们只考虑非类型参数为整型和布尔型

得益于上述统一，IsEqual 只需要如下一份实现就够了：

template<typename T, typename U>
struct IsEqual {
    using Result = FalseType;
};

template<typename T>
struct IsEqual<T, T> {
    using Result = TrueType;
};

#define __is_eq(x, y) IsEqual<x, y>::Result

我们还需要输出这些类型信息：

template <bool V>
std::ostream &operator<<(std::ostream &os, BoolType<V> const &) {
    return os << "BoolType<" << ((V == true) ? "true" : "false") << ">";
}

template <int V>
std::ostream &operator<<(std::ostream &os, IntType<V> const &) {
    return os << "IntType<" << V << ">";
}

int main() {
    std::cout << IntType<1>() << std::endl;
    std::cout << __is_eq(IntType<1>, IntType<2>)() << std::endl;
    std::cout << __is_eq(BoolType<true>, TrueType)() << std::endl;
    std::cout << __is_eq(const char *, char * const)() << std::endl;
}

需要注意的是，由于 Result 实际上是一个构造函数，所以我们需要加上 () 来构造相应的对象，这可能会影响性能。需要构造什么样的对象在编译期已经决定了，只不过需要在运行期构造对象来触发 << 的重载，从而输出相应的信息。

统一的 Print 元函数（编译期）会报 Floating point exception

一切都是函数

我们定义一些宏简化表述：

#define __int(value)   typename IntType<value>::Result
#define __bool(...)    typename BoolType<__VA_ARGS__>::Result
#define __true()       typename TrueType::Result
#define __false()      typename FalseType::Result
#define __is_eq(...)   typename IsEqual<__VA_ARGS__>::Result

为了取得类型里的实际数值，我们需要一个元函数专门用来对类型求值：

template<typename T> struct Value {
    enum { Result = T::Value };
};

#define __value(...)    Value<__VA_ARGS__>::Result

Value 元函数是整个 TLP 库中仅有的一个用 Result 表示非类型的元函数，它一般使用在一个元编程表达式的最后，用于将整个表达式进行求值，然后将值传递给运行期 C++，所以并不会对元函数的组合造成问题。

这样就不需要重载 << 了：

int main() {
    std::cout << __value(__int(3)) << std::endl;
    std::cout << __value(__is_eq(__int(1), __int(2))) << std::endl;
    std::cout << __value(__is_eq(const char *, char * const)) << std::endl;
}

现在可以看到，构成整个计算的似乎都是函数。在这种表述下，函数和类型其实是一致。

我们还可以将数值计算的过程提前到编译期，只不过这里的数值使用类型来表述：

对 IntType 进行数值运算，对 BoolType 进行逻辑运算

template<typename T1, typename T2> struct Add;

template<int V1, int V2>
struct Add<IntType<V1>, IntType<V2>> {
    using Result = IntType<V1 + V2>;
};

#define __add(...)    typename Add<__VA_ARGS__>::Result

调用如下：

int main() {
    std::cout << __value(__add(__int(1), __int(2))) << std::endl;
}

前面介绍的了 Value 元函数的定义，它假设 <> 里面定义了名为 Value 的数值成员，我们自定义的 IntType 和 BoolType 都满足这个约束。而通过对 Value 的模板特化，可以无侵入性地对不满足这一约束的类型进行扩展：

C++ traits

struct EmptyType
{};

#define __empty() EmptyType

template<>
struct Value<EmptyType> {
    enum { Result = 0 };
};

这样就可以对 EmptyType 调用 Value 元函数了 __value(__empty())

模式匹配

编译器对模板的特化版本选择相当于是在做模式匹配。下面我们借助这一特性实现一个在模板元编程中最常使用的基础元函数 IfThenElse，使用它可以完成类型选择的功能：

template<typename Condition, typename Then, typename Else> struct IfThenElse;

template<typename Then, typename Else>
struct IfThenElse<TrueType, Then, Else> {
    using Result = Then;
};

template<typename Then, typename Else>
struct IfThenElse<FalseType, Then, Else> {
    using Result = Else;
};

#define __if(...) typename IfThenElse<__VA_ARGS__>::Result

除了模板特化，还有一个工具可以用来在模板元编程中完成模式匹配的功能，那就是 C++ 编译器对重载函数的选择。我们可以实现 IsConvertible 来识别一个类型是否能够向另一个类型默认转型：

template<typename T, typename U>
struct IsConvertible {
private:
    struct Yes { char dummy; }; // using Yes = char;
    struct No  { char dummy[2]; };

    static Yes test(U);
    static No  test(...);
    static T   self();

public:
    using Result = BoolType<sizeof(test(self())) == sizeof(Yes)>;
};

#define __is_convertible(...) typename IsConvertible<__VA_ARGS__>::Result

这里的关键在 sizeof(test(self())) == sizeof(Yes)。self 作为静态函数，返回类型 T，这避免了直接创建 T 的对象。将 T 传入 test 后，若 T 可以默认转型到 U，就会调用 static Yes test(U);，否则调用 static No test(...);。而 Yes 和 No 的大小不同，使用编译期运算符 sizeof 即可判断调用了哪个函数。

我们还可以实现一个判断两个类型是否能够互相转型的元函数：

#define __is_both_convertible(T, U) __and(__is_convertible(T, U), __is_convertible(U, T))

通过函数组合，我们还能实现出 __is_base_of()，用来判断一个类型是否是另一个的父类：

#define __is_base_of(T, U) __and(__is_convertible(const U*, const T*),\
                                 __and(__not(__is_eq(const T*, const void*)),\
                                       __not(__is_eq(const T, const U))))

不过似乎和标准库中不太一致：https://zh.cppreference.com/w/cpp/types/is_base_of

递归

函数式语言依赖模式匹配和递归完成类似命令式语言里分支选择和循环迭代的功能。

我们演化之前递归计算的例子，实现一个可以对任意个 IntType 进行求和的元函数 Sum：

template<typename ...Numbers> struct Sum;

template<typename Number, typename ...LeftNumbers>
struct Sum<Number, LeftNumbers...> {
    using Result = typename Add<Number, typename Sum<LeftNumbers...>::Result>::Result;
};

template<> struct Sum<> {
    using Result = IntType<0>;
};

#define __sum(...)  typename Sum<__VA_ARGS__>::Result

如果参数个数为 0，则选择特化版本；否则递归展开参数，用当前参数和剩余参数的总和进行相加。

注意声明变长参数时 ... 在参数名前面，而对其使用时 ... 在参数名后面。

不可变性

C++ 中可以参与编译期计算的主要是类型和编译期常量，它们都是不可变的。

从这个角度来说，C++ 模板元编程是一种纯函数式语言，遵循引用透明性。

函数没有状态，所以函数的返回值只依赖于其参数

没有真正意义上的变量，所谓变量只是一个类型的别名符号

由于函数没有状态，所以可以保存参数然后延迟计算，这使得语言层面的惰性计算变得容易。

代价是编译速度变慢和占用大量内存。

惰性

C++ 对模板的实例化采用尽量惰性的原则。

parallel101 中已经有了一个惰性的例子，我们再看一个：

template<typename T, bool isClonable>
struct Creator {
    static T* create(const T* instance) {
        if (isClonable)
            return instance->clone();
        else
            return new T(*instance);
    }
};

我们希望有一个工厂类，用来创建 T 类型的对象。如果 T 支持 clone 方法，则采用从一个现有对象 clone 出新对象，否则调用拷贝构造函数 new 出来一个新对象。isClonable 用于指示 T 是否支持 clone 方法。

这里的关键是分离两个分支，不让其同时编译，否则传入一个不支持 clone 方法的 T，也会编译到 instance->clone();，作者的解决方案是使用编译期的 __if 显式进行分离：

template<typename T>
struct ClonableCreator {
    static T* create(const T* instance) {
        return instance->clone();
    }
};

template<typename T>
struct UnclonableCreator {
    static T* create(const T* instance) {
        return new T(*instance);
    }
};

template<typename T, bool isClonable> using Creator = __if(__bool(isClonable), ClonableCreator<T>, UnclonableCreator<T>);

C++ 17 引入了 if constexpr，所以可以简单的改为：

template<typename T, bool isClonable>
struct Creator {
    static T* create(const T* instance) {
        if constexpr (isClonable)
            return instance->clone();
        else
            return new T(*instance);
    }
};

鸭子类型

模板为 C++ 提供了鸭子类型的特性：关注的不是对象的类型本身，而是它被如何使用的。

对模板参数的约束通过对其使用方式来隐式体现，概念库的提出可以将约束显式化。

对于 Haskell 而言，有类型约束的概念：

max :: (Ord a) => a -> a -> a

鸭子类型为程序的书写带来了很多便利性，基本上动态语言（Python、Ruby）以及拥有类型推导的静态语言（C++、Haskell、Scala）都有这个特性。区别在于动态语言一般是在运行期发现类型不满足约束，而静态语言通过强大的类型推导可以在编译期就发现错误。

然而，模板元编程本身是不支持鸭子类型的，为此我们将所有的数值也封装成了类型。我们统一模板元编程的计算对象类型，就相当于把一切都变成了鸭子，间接地也得到了鸭子类型的好处。

SFINAE

元组的运行期索引

https://changkun.de/modern-cpp/zh-cn/04-containers/

#include <variant>
#include <tuple>
#include <iostream>
#include <stdexcept>

template <size_t n, typename... T>
constexpr std::variant<T...> _tuple_index(const std::tuple<T...>& tpl, size_t i) {
    if constexpr (n >= sizeof...(T))
        throw std::out_of_range("out of range");
    if (i == n)
        return std::variant<T...>{ std::in_place_index<n>, std::get<n>(tpl) };
    return _tuple_index<(n < sizeof...(T) - 1 ? n + 1 : 0)>(tpl, i);
}

template <typename... T>
constexpr std::variant<T...> tuple_index(const std::tuple<T...>& tpl, size_t i) {
    return _tuple_index<0>(tpl, i);
}

template <typename T0, typename ... Ts>
std::ostream & operator<< (std::ostream & s, std::variant<T0, Ts...> const & v) {
    std::visit([&](auto && x){ s << x; }, v);
    return s;
}

int main() {
    auto t = std::tuple<int, double, std::string>{1, 2.2f, "3"};
    int i;
    std::cin >> i;
    std::cout << tuple_index(t, i) << std::endl;
}

非类型参数递归，人傻了

C++ Template Metaprogramming

TOC