C++ template-meta programming

我今天又看了 10 MB 的错误信息

# 第 0 节 - 前言

# 为什么要写这个?

近日沉迷实现一个类型安全的 EventEmitter (opens new window)

alt

某日晚上突然顿悟了一些东西,想要写下来。

什么?可能看不懂?0.5 分警告

前排提示:这套文章十分主观,绝大部分都来自于笔者自己的编码经验。所以,如果你不喜欢,那你来打我啊,反正我也不会改。

# 前言

本文假设读者已经有如下的 C++ 语言基础:

  • class/struct/template 等关键字的拼写
  • 知道啥是模版,啥是继承,啥是多态
  • 有一个支持 C++11/14/17 的编译器(不用 clang 的都踢了)
  • 爱思考,会谷歌,能面向 StackOverflow 编程(用百度的都踢了)
  • 没了

# 计划的内容

  • 模板基础知识
  • 模板类型推导
  • 模板匹配规则
  • 模板元编程中的函数式思想
  • 编译期计算
  • 模板类型擦除
  • 写出优雅的模板元编程代码(很重要!!!)
  • 实战项目包括
    • 编译期斐波那契数列
    • 实现一个最 naive 的 std::any
    • 编译期快速排序
    • 类型列表
    • Event Emitter

按照预期设想: 这些内容会被均匀(可能?)分散在每个文章中,她们之中蕴含的思想将会贯穿本系列的所有文章。

# 作者联系方式

# 致谢

# 模版元编程是什么?有什么用?

断句:模版/元编程


所谓「元编程」,就是一种「抽象的编程」。我认为,对程序的抽象其实就是找出程序之间的相似之处,然后用统一的逻辑将其表示出来,而对于程序之间的不同之处,我们用一种手段将他们隐藏起来。在 C++ 中,这种手段就叫做「模版」,表示统一的逻辑的方式就叫「元编程」。


C++ 标准库是「泛型编程(Generic Programming)」的实践,这意味着数据和算法是分开的。算法最终需要的不过就是数据的比大小而已,所以我们需要用模版将算法的逻辑「抽象化」,比如我们知道标准库里有这样的算法:

template <class T>
const T& min(const T& a, const T& b)
{
    return a < b ? a : b;
}

这里的 T 我们不用管是什么,我们只要知道,这个算法会返回二者中较小的一个,而至于怎么比较 ab,那跟我 min 有什么关系?


所以在我的理解中,「模版」给了我们抽象算法的能力,算法是通用的,但仅仅只靠「模版」来抽象具体类型却不足以帮助我们写出通用的算法逻辑,我们还需要更强大的功能,来帮我们设计出更通用、更友好、更健壮、错误信息更可读的代码,于是就有了「元编程」。

# 花费大量时间学习模版元编程,值得吗?

不值得,你可以关掉这个页面了。

那我为什么要学?我只是觉得好玩罢了。

# 为什么歧视 MSVC?

我不是,我没有,你不要乱说啊。

# 模版参数命名约定

模版参数是指 template <typename T> 里的 T,其定义域所有类型。 给这个参数取个好名字禁用 Windows 自动更新一样重要。

所以对于特定的一些模版参数,我的习惯是这样

  • 普通的类型: T, U, A, B, C, From, To, ...
  • Callable 类型 (opens new window): F, Callable, Handler, ...
  • 函数参数类型: Args, ArgsT, ...
  • 函数返回值类型: R, RetType, ReturnType, ...
  • 变长参数: Ts..., As..., Xs..., ...
  • 其他的看心情

# 暴论一:模版元编程是另一门编程语言

模版元编程是借助了 C++ 语法的另一门运行在编译期的编程语言, 它的作用是辅助 C++ 程序设计。

说 TMP (Template MetaProgramming, 模版元编程) 是另一门编程语言,是因为你可以在 TMP 中见到一些好康的语法,以及神似函数式语言的一些写法。

# 暴论二:类型即数值

作为一门编程语言,那么就有这门语言操作的数据。在 C++ 中我们操作的数据有各种类型,比如 int, float, std::string;类似的,在 TMP 中,我们操作的数据就是上面提到的那些类型,比如下面的代码:

template <typename T>
using S = std::remove_reference_t<T>;

这里先解释一下,上面这段代码的意思是:

S 是一个类型,T 也是一个类型,并且 S 取决于 T

  • 如果 T任意一个类型 U 的引用类型 U & (即 T == U &),则 SU
  • 如果不是,则 ST

举几个更直观的例子,

T S
int & int
const int & const int
... ...
U & U

这个像不像我们小学二年级时学过的函数值表?

不妨更深入一步,之前已经说过 TMP 是一门编程语言,那么我们就可以认为上面那个 S 是一个函数,S 需要一个参数 T,其返回值记为 S<T>

写成伪代码的形式就是这样

S<T> {
    return std::remove_reference_t<T>;
}

或者写作

S<T> {
    if (T == U &) {
        return U;
    } else {
        return T;
    }
}

有内味了,有内味了。

(什么?你说要把尖括号换成圆括号你才看得出这是个函数?踢了!

在一些资料书中,上面的模版 S 也被叫做元函数 (metafunction), 可见我的暴论都没说错。

但是在后续的文章中,我依然会把类型和数值分开称呼(原因就在下面),但你得知道 TMP 是能把类型当作数值一样来做运算的


那么 TMP 能不能操作 C++ 里的那些 int, flaot... 呢?当然可以!比如:

/* 接受一堆类型作为参数 */
template <typename ... Ts>
struct T {};

/* 接受一堆 int 作为参数 */
template <int ... Is>
struct I {};

void foo() {
    using t1 = I<1, 2, 3, 4>;
    using t2 = T<int, char, short>;
}

怎么样?现在看出那个 typename 的意思了吗? 是不是相当于「类型的类型」呢?


怎么样?那个 using 是不是觉得很微妙? 像不像是在定义一个「常量」? (using 定义出来的是类型,which is immutable)

# 暴论三:TMP 没有停机性检查

啥叫停机性检查?我们写个代码来看看:

template <size_t A, size_t B>
struct Add {
    static constexpr size_t result = Add<A + 1, B - 1>::result;
};

template <size_t A>
struct Add<A, 0> {
    static constexpr size_t result = A;
};

Add<A, B> 可以在编译期计算 A + B,比如

static_assert(Add<1, 2>  ::result == 3,   "You wrote a bug");
static_assert(Add<50, 99>::result == 149, "You wrote a bug");

但是如果你试着把终止条件去掉,让 Add<A, B> 成为一个死循环,让代码长这样:

template <size_t A, size_t B>
struct Add {
    static constexpr size_t result = Add<A + 1, B - 1>::result;
};

我们再试着运行同样的代码,编译器会给出这样的错误:

fatal error: recursive template instantiation exceeded maximum depth of 1024

看到没?C++ 编译器不会检查上面的代码是否能停机,而是限制模版展开次数。

事实上,从错误信息可以看出,就算终止条件存在,当 Add<A, B> 展开次数超过 1024 次时,编译器一样会报错。

这也限制了一些特定的需求用 TMP 是无法完成的。(后文会详细讨论) 但这也让一些骚操作成为可能。

# 暴论四:TMP 是 duck-typing

啥是 duck-typing(鸭子类型)?你 tnd 不会谷歌吗?

简单的说,如果有这样的代码

template <typename Duck>
void meow(Dock &&duck) {
    duck->meow();
}

相信大家都能看出来,不管这个 Duck 在实例化的时候被替换成了什么类型,只要这个类型提供了 meow() 的成员方法,这段代码就能通过编译。


这就是所谓的

当看到一只鸟走起来像鸭子、游泳起来像鸭子、叫起来也像鸭子,那么这只鸟就可以被称为鸭子

# 暴论五:TMP 是动态类型和静态类型的混合语言

举个例子就行啦:

template <typename T>
struct happy {
    using type = int;
};

template <>
struct happy<float> {
    static constexpr int type = 1;
};

上面的例子里,我们为 happy 特化(下一章会讲)了 float 类型,于是只有 happy<float>::type 本身是一个值,而不是一个类型,其余的 happy<...>::type 都是一个类型。

那么现在我们有一个元函数如下定义:

template <typename T>
using get_happy = typename happy<T>::type;

乍一看没什么问题,但当你把 float 作为参数传递给 get_happy 的时候,编译器无疑会抛出一个编译错误。

error: no type named 'type' in 'struct happy<float>'

这个问题的原因我们会在后续的文章中慢慢解释...这里只能说是因为:每个特化的分支中的定义是独立的

其次还能从此处需要手动指定 typename 看出来,如果编译器能从 happy 的泛化版本中推断出 happy<...>::type 是类型而不是值,那么在 get_happy 中就不需要手动指定了,因为泛化版本中的 type 和 特化版本中的 type 应该是同样的东西(都是类型或者都是值),但实际上并不是。所以我们可以知道:TMP 在对待类型参数上跟动态类型类似(实际上就是)。

那么静态类型表现在何处呢?

自然是直接将数值作为模板参数传递的时候啊!

# 技巧一:using 可以少打一按一堆键盘

这也是 C++ STL 里广泛采用的方法,我们知道 std::remove_reference 要这样用:

using type = typename std::remove_reference<T>::type;

着看着很不爽,因为 typename::type 完全就是多余的,体现不出核心要素, 所以我们可以为这个函数写一个额外的辅助函数,比如:

template <typename T>
using remove_reference_t = typename std::remove_reference<T>::type;

这样就可以直接:

using type = remove_reference_t<T>;

同理,如果是值,我们可以这样:

template <typename T, typename U>
static constexpr bool is_same_v = std::is_same<T, U>::value;

秒啊!

切记,请保持「一致性」:

  1. 如果为类型取别名,请使用 _t 后缀
  2. 如果为值取别名,请使用 _v 后缀

# 技巧二:统一「返回值」的名字

就像上面的 std::remove_reference 一样,它的返回值的名字叫做 type

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

这里 identity 函数返回的是一个类型,所以我们给返回值取名叫做 type, 同理,如果我们有一个函数返回的是一个值,我们一般给它取名 value

template <typename T, T t>
struct identity_value {
    static constexpr T value = t;
};

所以,这里也需要保持「一致性」

  1. 如果返回的是一个类型,请使用 type 作为名字
  2. 如果返回的是一个值,请使用 value 作为名字

我最不推荐使用那种有歧义的名字,比如 result,因为 TMP 是动态类型的语言, 而 result 这个词太过于笼统,不能从名字看出返回的东西到底是个类型还是一个值。

不过嘛,你要想用,我也没办法啊。我总不能顺着网线去打你吧!

# 总结

在与 TMP 打交道的过程中,请一定要记住这几点暴论,尤其是「类型即数值」, 这点真的很!重!要!

# 参考文献

# 第 1 节 - 「泛化」和「特化」

# 前言

上一篇文章 (opens new window)讲了一些基础前提以后,这里开始进入 TMP 真正有趣的地方。

# 泛化

我们有一个做除法的静态成员函数(别问我为什么是静态成员函数而不是全剧函数):

class Div {
    static double doit(double lhs, double rhs) {
        return lhs / rhs;
    }
}

但是这个函数只能对 double 类型做除法,现在我们需要将其中的算法逻辑抽象出来,让它能对所有类型都做除法,于是我们引入模版参数 T,来代表一个任意类型

template <typename T>
class Div {
    static T doit(T lhs, T rhs) {
        return lhs / rhs;
    }
}

好了,现在我们的 Div::doit 就能应用到任意支持「除法」运算的类型上了。(这里强调支持「除法」运算是因为如果 T 不是原始数据类型并且也没有重载正确的 operator/ 时,编译器会报错)。


如你所见,上面的过程就叫做「泛化」。我们说泛化后的模版类 Div 是「原型」,也叫 Div 的「泛化版本」。


(其实我非常不想扯名词的,但后文需要,没办法

# 特化

在上面的例子中,当 Tint 的时候,而 rhs 又恰好为 0,那么上面的代码就会出现运行时异常。

所以我们可以int 类型特化 Div 来处理这种特殊情况:

template <>
class Div<int> {        /* 为 int 类型特化 */
    static int doit(int lhs, int rhs) { 
        if (rhs == 0) {
            printf("Divide by zero\n");
            return 0;
        }
        return lhs / rhs;
    }
}

void foo() {
    Div<int>::doit(1, 0);    /* Divide by zero */
    Div<double>::doit(1, 2); /* 0.5            */
}

等等!那个 template <> 是什么玩意?! 你哪来这么多问题!,在模版匹配规则的地方会详细讲这个东西。

现在可以理解为 「Div 在为 int 特化后,不再需要额外的模版参数」, 那既然不需要模版参数了,那能不能去掉这一行呢?

答案是不行,因为这个特化依赖于原型。关键字 template 相当于告诉编译器:这是一个模版类的特化版本,不是独立存在的一个类。


让「原型」在遇到不同的类型时执行不同的代码,从而做到处理特殊情况。这种方法就叫做「特化」,更准确的说,

特化(specialization)是根据一个或多个特殊的整数或类型,给出模板实例化时的一个指定内容。

特化,就是处理特例。我们在数学中学过「斐波那契数列」,这个数列满足下面的关系:

F(0) = 1
F(1) = 1
F(n) = F(n - 1) + F(n - 2), n >= 2

它有两个特例,当 n == 0 或 n == 1 时,F(n) 的值恒为 1。

显然, F(0) 和 F(1) 就是在处理斐波那契数列中的特例,这就是「特化」。

# 实战:编译期斐波那契数列

真就说什么来什么,我们来整一个利用 TMP 特性实现的编译期斐波那契数列。

我们先把一般情况写出来,也就是「原型」:

/* 这里有疑惑的自觉看上一章 */
template <int N>
struct Fib {
    /* 递归调用元函数 Fib 计算第 N 项的值 */
    /* constexpr 会「请求」编译器在编译期试着对这个值求值 */
    static constexpr int value = 
        Fib<N - 1>::value + Fib<N - 2>::value;
};

然后再处理 N 为 1 和 2 时的特殊情况,注意!!!我要特化了!!!

处理 $F_{0} = 1$

template <>
struct Fib<0> {
    static constexpr int value = 1;
};

处理 $F_{1} = 1$

template <>
struct Fib<1> {
    static constexpr int value = 1;
};

然后我们来测试一下:

static_assert(Fib<20>::value == 10946, "You wrote a bug");

嗯!我没写出 bug!

# 偏特化

后面讲到模版匹配规则的时候会再详细来说。 可以先看参考文献里的资料。

# 参考文献

# 第 2 节 - 模板匹配规则

# 导入

上篇里讲到了特化,那么这里我们就从特化的更多应用开始吧~

比如我们需要实现这样的一个功能,我们需要为类型编号. 即将类型映射到一个整数上, 比如 int 类型编号为 0float 类型编号为 1double 类型编号为 2,指针类型编号为 3 ...

看下面的代码:

template <typename T>
struct id;

这是我们简单的 id 函数,现在它还没有实现。 但别担心,下一步我们就要为我们支持的类型进行特化了。

比如,将 int 类型编号为 0

template <>
struct id<int> {
    static constexpr size_t value = 0;
};

以此类推,我们能特化更多:

template <>
struct id<float> {
    static constexpr size_t value = 1;
};

template <>
struct id<double> {
    static constexpr size_t value = 2;
};

这时候,你可能就问了,如果我要映射 int * 怎么办? 好说!特它!

template <>
struct id<int *> {
    static constexpr size_t value = 3;
};

问题似乎解决了。

但你有一天忘记了你的具体实现,你只记得你曾经写过一个元函数,可以将类型映射为整数,于是你写下了 id<double *>::value 这样的代码。最后你得到了这样的错误

error: no member named 'value' in 'id<double *>'

你一看~原来是没有为 double * 特化实现,于是你又写下了这样的代码

template <>
struct id<double *> {
    static constexpr size_t value = 3;
};

然后你仔细一想,发现事情不简单:难道我要为所有指针类型都手动特化吗?

当然不用!还记得之前我们说过 所有类型 这一概念吗?没错,这可以用一个模板参数来表达!此处不妨命名为 P 吧(P 表示 pointer),于是你拿起键盘,手起刀落,写下这样的代码:

template <>
struct id<P *> {
    static constexpr size_t value = 3;
};

嗯!我们为所有类型 P 的指针类型 P * 特化了 id 函数,让 id 函数对所有指针类型的参数都返回 3.

但是...编译器可不这么认为:

error: 'P' was not declared in this scope

嗯?P 没有定义是什么回事?难道编译器不知道这个 P 表示所有类型吗?

你想的没错,编译器还真不知道!

在这里,编译器认为这个 P 应该是某个实际存在的类型,比如 struct P {} 这样的。但是我们的意思是让 P 表示所有类型,所以我们需要这里的 P 是类型参数,which 我们必须手动告诉编译器,就像这样:

template <typename P>
struct id<P *> {
    static constexpr size_t value = 3;
};

在上面的 template 里面加上一条 typename P 就行了,这就像在做一个声明:我这里需要用到一个参数 P,这个 P 是一个类型名。

然后我们再把代码放一起来看:

template <typename T>
struct id;

template <>
struct id<int *> {
    static constexpr size_t value = 3;
};

template <typename P>
struct id<P *> {
    static constexpr size_t value = 3;
};

然后我们再写一点测试代码

static_assert(id<int *>::value == 3);      /* ok */
static_assert(id<char *>::value == 3);     /* ok */
static_assert(id<double *>::value == 3);   /* ok */

嗯,都正确。

现在问题又来了,如果我想细化指针类型的 id 怎么办呢? 比如现在我们需要这样操作,让 id<P *> = id<P> + 100, 即下面这样的断言恒真(伪代码):

static_assert(id<P *>::value == id<P>::value + 100, "FUCK");

要解决这个问题,我们需要先明白模板匹配规则。

# 模板匹配规则

注意看上面的那个对指针类型的特化,我们说 P 是一个类型名,然而诸如像 int *, double * 之类的都是类型名。那么为什么还会匹配到 P * 呢?或者说,用 P * 匹配了 double * 后,P 是什么呢?

我们不妨试一试

template <typename T>
struct what;

template <typename P>
struct what<P *> {
    using type = P;
};

template <typename T>
using what_t = typename what<T>::type;

然后再写一个辅助函数用来打印类型的名字:

template <typename T>
struct show {
    show() = delete;
};

然后我们来看看 P 到底是个什么鬼:

show<what_t<double *>>();

编译这段代码,我们能从编译错误信息中看到这样一句:

[with T = 'double']

所以,我们尝试用 P * 去匹配 double *,如果匹配成功,那么 P 就变成了 double。 有没有觉得像什么?模式匹配!

没错,模板匹配规则,就是模式匹配。

# 元编程中的模式匹配

上面已经有了一个很生动的例子,用 P * 匹配 double *,所以 P 是 double。 那么能不能说的更笼统一点呢?

当然可以,不然我还能自己把自己问死了?

Pattern Matching:compare something with its construction form 模式匹配:将一个东西,按照其「构造的方式」进行对比

当然上面这个版本需要进一步阐述:

# 1. 构造?

比如你有一个基本类型 int,我们就可以这个类型的基础上构造出 int * 类型。

这里可以说 * 是一个构造器,它接受一个类型,返回一个新类型。 不妨用 Star 来代替 *,于是就可以说:Star 接受一个类型 T,返回新的类型 Star(T)。 用伪代码表示如下:

Type Star(T) {
    return T *;
}

同理,用 Const 代替 const 关键字,我们说:Const 接受一个类型 T,返回新的类型 Const(T)。 用伪代码表示如下:

Type Const(T) {
    return const T;
}

这就是构造。我真的只能解释成这样了,呜哇啊啊啊啊啊啊啊啊

# 2. 匹配?

我们有一个值/类型 T,我们可以尝试用一个「表达式」(表达式中可以包含类型) 去跟 T 的「构造形式」做对比,这就叫「匹配」。 匹配过程中,尽可能地让 T 的「构造形式」中没有被被匹配的部分最少

于是,我们就可以用 P * 尝试去匹配尽可能符合条件的 P。

类型 P
int * int
int ** int *
int **** int ***
int(*)(int) int(int)

用上面的 ConstStar 举例子,如果写成伪代码:

match (T) { /* 对 T 进行匹配 */
    case Star(U)  => /* T 是 U * */
    case Const(U) => /* T 是 const U */
    case _        => /* T 两种都不是 */
}

这就是匹配。我真的只能解释成这样了,呜哇啊啊啊啊啊啊啊啊

# 具体例子?

光说概念可能不好理解,我们直接上代码来看。

我们知道,C++ 中的模板类并不是类型,而是类型构造器(即:模板类本身不能作为对象的类型,只有在实例化以后才可以)。 就是这样:

/* 错误,std::vector 不是类型,而是类型构造器 */
std::vector v1;

/* 正确,std::vector 接受一个类型参数 int,构造出(实例化)了类型 std::vector<int> */
std::vector<int> v2;

所以我们这里就可以看出,std::vector 是类似于上面的 Star, Const 之类的构造器。 于是我们就可以进行模式匹配:

template <typename V>
struct vector_value_type;

template <typename ValueType>
struct vector_value_type<std::vector<ValueType>> {
/*                       ^^^^^^^^^^^^^^^^^^^^^^   */
    using type = ValueType;
};

注意看代码中标出来的地方,这里我们用跟上面一样的伪代码写出来就是这样:

match (V) {
    case std::vector<ValueType> => return ValueType;
    case _                      => fuck;
}

快!自己理解!我真的只能解释成这样了,呜哇啊啊啊啊啊啊啊啊

# 来吧!解决问题!

问题是啥来着?

现在问题又来了,如果我想细化指针类型的 id 怎么办呢? 比如现在我们需要这样操作,让 id<P *> = id<P> + 100, 即下面这样的断言恒真(伪代码):

static_assert(id<P *>::value == id<P>::value + 100, "FUCK");

很简单啊:

template <typename P>
struct id<P *> {
    static constexpr size_t value = 100 + id<P>::value;
};

你说是吧?

# 实战:TypeList

戳这里 (opens new window)

# 实战:Function Parser

我们要从一个 Callable 的类型中,解析出返回类型,和参数类型。 Callable 类型就是可以支持「函数调用语法」的类型,比如本身就是个函数, 或者重载了 operator()(即 Functor 类型)。

我们不妨先参照上面的伪代码,写出 Function Parser 的伪代码:

/* 模式匹配 Callable 类型 */
match (Callable) {
    case R(Args...)             => /* 是函数,或者类静态函数 */
    case R(Class::*)(Args...)   => /* 是成员函数 */

    /* 不是函数/函数指针,那么是 Functor 吗?*/
    case _ => match (decltype(&Callable::operator())) {
                  case R(Class::*)(Args...) => /* 是 Functor */
                  case _                    => /* 不是,滚    */
              }
}

# 分析

TMP 的常用套路之一就是:先实现一个通用版本,然后在这个通用版本的基础上进行特化。

template <typename Callable>
struct function_parser {
    /* 什么都不做 */
};

接着看上面的第一个匹配式子: case R(Args...),我们这样匹配它

template <typename R, typename ...Args>
struct function_parser<R(Args...)> {
    using return_type = R;
    using arg_types = TypeList::List<Args...>;
    using function_type = std::function<R(Args...)>;
};

再强调一次,特化处的 template <typename R, typename ...Args> 是用于声明需要用到哪些参数的, 也就是声明模式匹配表达式 case R(Args...) 里的 RArgs

通用版本里的模板参数声明的意义与特化中的完全不同,千万不要弄混淆了!!


然后是第二个匹配表达式: case R(Class::*)(Args...)

template <typename Class, typename R, typename ...Args>
struct function_parser<R(Class::*)(Args...)> {
    using return_type = R;
    using arg_types = TypeList::List<Class&, Args...>;
    using class_type = Class;
    using function_type = std::function<R(Class&, Args...)>;
};

注意这里的 arg_typesfunction_type,他们的第一个参数都多了一个 Class &, 这是因为,现在匹配的是成员函数,而成员函数都需要一个 this,这个 this 自然就是 Class &.


现在我们已经完成了前两个模式匹配了,但第三个是一个通配符(即前两个都没匹配到), 那么在 TMP 里应该怎么对应呢?

没错,就是我们一开始写的那个通用版本,我们再搬出来看看:

template <typename Callable>
struct function_parser {
};

我们需要在这个地方对 decltype(&Callable::operator()) 再进行一次模式匹配, 所以现在我就要祭出 TMP 中常用的第二个法宝:继承


这里我们应该进行的模式匹配中,也会包含 case R(Class::*)(Args...) 这个模式, 而这个模式的处理我们已经实现过了,所以我们让 function_parser 的通用版本继承自己的某个特化版本, 这样,在所有模式都匹配不到的时候,重新匹配第二次,这样不就行了嘛?

template <typename Callable>
struct function_parser : public function_parser<decltype(&Callable::operator())> {
};

这样,就完成了整个模式匹配的过程。但值得一提的是, 上面这样的写法存在不足之处:匹配到 lambda 表达式 的具体类型无法转换。 比如:

auto lambda = []() { printf("yes"); };
using FT = typename function_parser<decltype(lambda)>::function_type;
FT f = lambda; /* error! */

为啥呢?


这就要讲一下 Functor 和一般的成员函数的不同了。 Functor 是重载了 operator() 的对象,而这个函数正好是个成员函数, 所以我们直接匹配 Callable::operator() 这个函数的类型的时候, 我们一定会进入到 R(Class::*)(Args...) 这个分支中,但是这个分支中, 我们必须让参数列表的第一个参数是 thisFunctor 是不需要的, 这便是冲突的原因。


那怎么解决呢?

很简单,我们单独为 Functor 做一个 Functor Parser 就行了。

template <typename F>
struct functor_parser : public functor_parser<decltype(&F::operator())> {
};

template <typename Class, typename R, typename ...Args>
struct functor_parser<R(Class::*)(Args...)> {
    using function_type = FunctionAlias<R(Args...)>;
    using return_type = R;
    using class_type = Class;
};

然后我们让 Function Parser 的通用版本继承自 Functor Parser:

template <typename Callable>
struct function_parser : public functor_parser<Callable> {
};

大功告成!

# 工业化版本

实际的版本中,需要考虑的情况还有 const 和函数指针,由于本篇文章只是讲解核心部分, 所以这些不那么重要的就忽略了。


这里是一份跑在生产环境的 Function Parser:[libmozart/function.hpp](https://github.com/libmozart/core/blob/bd432a29d9e56cecb4b89e7a8cdb7280981814fc/mozart%2B%2B/mpp_core/function.hpp#L58)

也许会有帮助!

# 第 3 节 - TypeList

# TypeList 是什么?

List 是什么?自然是列表。 TypeList,顾名思义,就是类型列表。 只不过列表里的元素不是数据,而是一个个的类型。 所以我们需要将类型视为一种数据。

而在 C++ 中,能将类型作为数据处理的只有元编程。 所以这部分涉及到大量元编程的前置知识:

  1. 前言 (opens new window)
  2. 「泛化」和「特化」 (opens new window)
  3. 模板匹配规则 (opens new window)

# 可变参数模板

一个列表,里面存放的元素个数可以是任意的,所以我们需要一种「容器」 能包装「任意个数」的类型。

这种东西,叫做「可变参数模板」(variadic templates):

template <typename ...Ts>
struct Fuck {};

那么这个 Ts... 就叫做「参数包」(parameter pack), 我们可以用 sizeof...(Ts) 得到参数包中元素的个数。

这里需要提一下参数包的解包规则,当 ... 出现在一个语法单元的末尾时, 代表这个表达式中的参数包将按照这个语法单元的格式进行展开。

比如:

template <typename ...Ts>
void fuck(Ts &&...ts) {
    use(std::forward<Ts>(ts)...);
}

所以,当你这样使用 fuck 函数的时候:

T t;
U u;
fuck(t, u);

里面的 use 函数调用处包含一个 std::forward<Ts>(ts) 这样的语法单元, 所以这里就会展开成:

use(std::forward<T>(t), std::forward<U>(u));

又比如:

template <typename ...Ts>
class son : public Ts... {};

所以当你这样使用 son 的时候:

son<A, B, C, D>

由于这里包含一个 public Ts 的语法单元, 所以这里会展开成

class son : public A, public B, public C, public D {};

Wow, awesome!

# 先来一个容器!

看看上面的可变参数模板,是不是跟我们要的容器很相似? 我们要的是这样的:

List<int, bool, char, List<int>, std::string>

是吧?

于是我们有了容器了:

template <typename ...Ts>
struct List {};

但是为了代码的整洁,我们可以考虑把这部分放到一个结构体里去(具体原因后面会体现):

struct TypeList {
    /* 列表元素的容器 */
    template <typename ...Ts>
    struct List {};

    /* 为了少打几个字,为空列表 List<> 取个别名 */
    /* 这不是显而易见的嘛 ? */
    using Nil = List<>;
};

# 容器有了,然后呢?

所以你最后的成果就是纯理论的,就像欧氏几何一样, 先设定几条简单的不证自明的公理, 再在这些公理的基础上推导出整个理论体系。

我们不妨思考一个列表的「最小行为集合」,在这个集合里的操作我们认为是「公理」。 然后其他的操作都可以使用这些「公理」实现。

对于一个列表,首先有的必须是往容器中添加内容,所以这个集合里必定包含「cons」。

然后我们需要能对这个列表进行遍历,不然,我要个列表只能存,不能读,那还玩个🔨。

所以,这个集合里还需要包含「head」和「tail」。

head: 取出这个列表的头部元素。

tail: 去除这个列表的头部元素。

那么,足够了吗?足够了。

# 我们先来实现 cons

这里需要用到特化,因为特化可以给我们使用「模式匹配」的能力。

/* I 后缀代表 Implementation(实现)*/
template <typename T, typename L>
struct consI;

template <typename T, typename ...Ts>
struct consI<T, List<Ts...>> {
    using type = List<T, Ts...>;
};

请注意这里的特化形式 consI<T, List<Ts...>>,这里要求我们传给 cons 的第二个参数必须是 列表容器,否则这个特化就无法匹配。

同时,还需要注意特化内部的 using type = List<T, Ts...>,这里就完成了添加操作: 把 T 添加到了原有列表的头部。

现在我们需要往列表里添加元素,就要这样用:

using my_list = List<int, char>;
using new_list = typename consI<bool, my_list>::type;

淦!typename consI<bool, my_list>::type 这一点都不像在调用一个函数! 我们可以多写一步,把后面那个 type 省略掉。

template <typename T, typename L>
using cons = typename consI<T, L>::type;

于是我们就能写:

using new_list = cons<bool, my_list>;

Wow, awesome!

# 然后是 head 和 tail

有了 cons 的实现经验,我们实现 headtail 就很简单了。

先来实现 head:

template <typename L>
struct headI;

template <typename T, typename ...Ts>
struct headI<List<T, Ts...>> {
    using type = T;
};

template <typename L>
using head = typename headI<L>::type;

然后是 tail,这不过就是 head 的另一种情况罢了:

template <typename L>
struct tailI;

template <typename T, typename ...Ts>
struct tailI<List<T, Ts...>> {
    using type = List<Ts...>;
};

template <typename L>
using tail = typename tailI<L>::type;

这里故意没有对 headtail 函数特化空列表,因为, 对空列表做 headtail,难道不是非法的吗(笑 ?

# 其他操作?

其他操作都可以通过 cons, head, tail 三种基本操作组合出来,不信你试试?

# 参考资料