深入学习C++中的多态

吼姆桑

一个完全脱离高级趣味的人

感谢 @lothario 在评论区的指正，虚函数重写时返回类型可以改变，只要和基类虚函数的返回类型满足协变关系，参考我下一篇文章：

前言中举的例子已经更改为一个更妥当的例子。

促使我深入学习多态理论是我在读《Effective C++》时偶然发现的一个叫CRTP（Curiously Recursive Template Pattern）的模板编程技巧，当时对这种将递归和继承相结合的用法感到既惊奇又困惑。举个CRTP的应用例子：编写一个多态函数，它能作用于任何具有 bool isEqual(const T &) 公有成员方法的类型 T 上，怎么实现？

乍一看我们可以通过定义一个基类来限定传入的对象类型具有这个接口：

struct Comparable {
    virtual bool IsEqual(const Comparable &) = 0;

然后在派生类中重写这个接口：

struct Integer : public Comparable {
    bool IsEqual(const Integer &other) override {
        return a_ == other.a_;
private:
    int a_;
struct Float : public Comparable {
    bool IsEqual(const Float &other) override {
        return a_ == other.a_;
private:
    float a_;
// somewhere else ...
Comparable *p1 = new Integer;
Comparable *p2 = new Float;
p1->IsEqual(*p2);   // woops, runtime error

你会发现编译是无法通过的。一个直观的解释是当我们用一个指向 Integer 对象的 Comparable 指针调用 IsEqual 时，编译器只要求实参类型是 Comparable 的派生类引用即可，我给你传入一个 Float 对象那岂不是会出现运行时错误？所以为了避免这种潜在的错误编译器是不会让你过的。

那把形参类型改成 Comparable 行吗？也不行，因为 Comparable 里面没有任何派生类的细节，你又怎么去重写一个依赖于派生类具体实现的 IsEqual 函数呢？所以不行。

但是用CRTP可以做到：

template <typename T>
struct Comparable { 
    bool IsEqual(const T &other) {
        return static_cast<T *>(this)->isEqual_impl(other);
private: 
    ... // ctors, dtors declared here to avoid base class object instantiation
    bool isEqual_impl(const T &) {	// default advance_impl to avoid infinetly recursive invocation 
        return false;
struct Integer : public Comparable<Integer> {
    ... // ctors, dtors, ...
private:
    bool isEqual_impl(IntPointer &other) { 
        return a_ == other.a_; 
    int a_;
    friend class Comparable<Integer>;
// There are no two identical leaves in the world
struct Leave {
    ... // ctors, dtors, ...
private:
    // bool isEqual_impl(const Leave &); // no such implementation for leave
template <typename T>
bool IsIdentical(Comparable<T> &lhs, Comparable<T> &rhs) {
    return lhs.IsEqual(rhs);
// somewhere else ...
Integer integer1(1), integer2(2);
Leave leave1(), leave2();
IsIdentical(integer1, integer2);		// ok, Integer satisfies Comparable
IsIdentical(leave1, leave2);	        // error, Leave does not satisfy Comparable

在这里我们实际上是通过模板类 Comparable<T> 来限制传入的类型参数 T 必须有 bool IsEqual(const T &) 这个方法。这里面的 IsIdentical 所表现出的多态行为叫F-bounded多态（F-bounded polymorphism），它描述了参数型多态（parametric polymorphism）里面对类型参数的一种约束。这种多态不同于受限多态（bounded polymorphism）———一种用来描述基于子类型实现的多态。这两种多态形式我在后面会详细讨论，举上面这个例子仅仅是想说明C++中实际上存在着形式相当丰富的多态。实际上，要实现对 IsIdentical 类型参数的约束，C++里面还有Concept和SFINAE这两种工具。

这篇文章的剩余部分会先介绍重载型多态（overloading polymorphism）和强制型多态（coercion polymorphism），然后再讨论它们作为特设型（ad-hoc）多态的局限性。随后会重点介绍实现通用型多态（universal polymorphism）两种重要方式：参数型多态和包涵型多态（inclusion polymorphism），其中参数型多态可以对类型参数进行约束，不同类型的约束用不同的量词描述，常见的有全称量化（universal quantified）、存在量化（existential quantified）、受限量化（bounded polymorphism）、F-受限量化（F-bounded polymorphism）。在讨论上述多态类型时，我都会用C++中相应的工具来描述它们。

多态类型

在汇编语言出现之前，程序员编写的都是由二进制串组成的代码。那个时代的编程语言并不存在所谓的类型，二进制串的含义完全取决于外部如何对它进行解读。

然而对事物进行分类是人类的本能， 我们会将行为一致的事物归类到一个子集并称其为一个类型 。例如说早期的编程语言中最早划分出来的两种类型是整型和浮点型，因为它们都有不同的表示方法和计算用途。

这种简单的按事物共性进行划分并不是类型的一个严谨定义，它会导致未定义的行为：例如说我们对一个浮点数和一个布尔值执行按位与操作，得到的表达式代表什么类型，如何解释这种操作？所以类型还必须具有 一组操作上的限制，以保护它的底层表示不被非法操作 。

类型的出现使得编程语言具有更好的表达世界的能力，这相当于在无类型世界上进行了一层抽象，让我们的算法能应用到所有类型相同的对象上。对代码中每个对象都归类到一个确定类型的编程语言称为 单态编程语言（monomorphic programming language） ，例如说早期的Pascal语言。

然而对事物进行抽象是人类的第二个本能，我们发现有些算法并不只能应用到某个具体的类型，而是能够应用到一个范围的类型上——也许它只依赖于对象的某些特有性质，也许什么性质都不依赖。单态编程语言不能够表达这种行为，但 多态编程语言（polymorphic programming）可以，后者可以描述一个值在不同的程序上下文中具有不同的类型这种行为，而这种行为也称为多态（polymorphism） 。我们也可以认为在多态编程语言中一个可以具有多种类型的值具有 多态类型（polymorphic type） 。

多态使得我们可以更抽象地描述算法的本质，而不用太过依赖于对象的具体性质。不过并非所有多态都需要多态编程语言才能实现，有些多态在单态编程语言中也能实现，虽然它们的实用性并不是太强：-)

特设型多态

特设型多态可以视为单态语言中实现多态的一种work around手段，它可以让某个对象在某些特定的程序上下文展现出表面上的多态，但并不能描述忽略对象具体类型细节的算法行为。特设型多态包含 重载型多态和强制型多态 ，它们均用来描述函数对象的多态性。

重载型多态

重载型多态是指一个函数对于不同的参数类型具有不同的实现版本，举个例子：

bool lessThanZeroAfterAdd(int a, int b) {
    return a + b < 0;
bool lessThanZeroAfterAdd(float a, float b) {
    return a + b < 0;
bool lessThanZeroAfterAdd(string a, string b) {
    string c = "";
    for (int i = 0; i < a.size(); ++i) {
       	if (i < b.size()) {
        	c.push_back((char)(((int)a[i] + (int)b[i]) % 256));    
        } else {
         	c.push_back(a[i]);   
    return c < a;
// somewhere else ...
int a = 1, b = -2;
float c = -1.5, d = 2.0;
string e = "abcd", f = "efg";
int g[4], h[4];
lessThanZeroAfterAdd(a, b);	// ok, return true
lessThanZeroAfterAdd(c, d);	// ok, return false
lessThanZeroAfterAdd(e, f);	// ok, return false
lessThanZeroAfterAdd(g, h);	// error

lessThanZeroAfterAdd 这个函数在入参为 int 、 float 、 string 时会具有不同的函数类型，并且在参数为 int 和 float 时函数行为是一致的。

但是要注意， lessThanZeroAfterAdd 只能应用在上面三种类型上表现出多态，当我们向 lessThanZeroAfterAdd 传入的参数类型没有被重载，那么就无法通过编译。此外， lessThanZeroAfterAdd 对于不同的参数类型并不能保证一致的行为，例如说在参数类型为 string 时， lessThanZeroAfterAdd 执行的算法和传入 int 或 float 时完全不一样。

强制型多态

强制型多态依赖于编程语言的强制类型转换机制，它表现为即便给函数传入的参数类型和形参类型不一致，但只要它们之间的强制类型转换是合法的，函数的调用就可以发生。这样的话函数就能对不同的类型具有多态：

struct Floatable {
	operator float() { return 0.0; }
bool lessThanZeroAfterAdd(float a, float b) {
    return a + b < 0;
bool lessThanZeroAfterShift(int a, size_t n) {
    return (a << n) < 0;
// somewhere else ...
int a = 1, b = -2;
float c = 2.0, d = -3.0;
Floatable e, f;
lessThanZeroAfterAdd(c, d);	// ok, match float
lessThanZeroAfterAdd(a, b);	// ok, can be converted to float
lessThanZeroAfterAdd(e, f);	// ok, can be converted to float
lessThanZeroAfterShift(a, 1);	// ok
lessThanZeroAfterShift(c, 1);	// ok, but have no meaning

这里我们定义了两个函数： lessThanZeroAfterAdd 和 lessThanZeroAfterShift ，前者接受两个 float 型参数，后者接受一个 int 型和一个 size_t 型参数。我们看到 lessThanZeroAfterAdd 除了接受 float 类型之外，还能接受任何重载了 operator float() 的类型，因此 lessThanZeroAfterAdd 表现出了一种多态性，也就是所谓的强制多态性。

但是这种多态不仅取决于强制类型转换是否合法，还取决于强制类型转换 是否有意义 。 lessThanZeroAfterShift 就是我想举的一个说明强制类型转换是否有意义的例子，我们知道 int 类型的底层表示，所以我们知道移位操作是有意义的，但问题在于 float 类型的底层表达使得移位运算并没有任何意义，也就是说我们将 float 转成了 int 后再做移位运算，实际上得出来的结果对原类型毫无意义。

现在我们知道特设型多态在实现时是多么依赖于具体的应用场景和上下文。我们如何才能表达出一个函数具有一种非常general的行为，不过多依赖于参数类型的具体细节呢？具有这种多态称为通用型多态，也是下一节要重点讨论的话题。

通用型多态

通用型多态被认为是真正意义上的多态，它赋予我们描述“一个函数对无穷多种类型都适用”这种行为的能力。打个比方，特设型多态就像我们只能通过枚举来描述一个集合：

{\rm UIntLessThanTen} = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}

但通用型多态让我们可以用更简洁的方法描述一个集合：

{\rm UIntLessThanTen} = \{x\ |\ x\in {\rm N}^{+},\ x < 10\}

当然，这未必是一个在各方面都合适的比喻，但它抓住了特设型多态和通用型多态在能力上的差别。下面我们重点讨论实现通用型多态的最重要的方式：参数型多态。

参数型多态

参数型多态是将函数的参数类型进行了参数化（有点绕，但意思就是类型也作为函数的一个可变参数了），当函数的类型参数在程序上下文中被确定后，就会呈现出相应的函数类型。举个简单的例子：

template <typename T>
bool lessThanZeroAfterAdd(const T &a, const T &b) { return a < b; }

这里实际上给出了上一节介绍的 lessThanZeroAfterAdd 函数的参数型多态版本。它不再局限于 float 和 int 类型了，而是只要 a < b 表达式有意义，且表达式的类型可以转换为 bool 类型就能实例化。虽然 lessThanZeroAfterAdd 可以运用到无穷多种类型上了，但是对类型参数还是有约束的，这种约束称为对类型参数的量化。

不过这里对类型参数使用的是隐式接口约束，这种约束方式不仅出错时不好debug，更重要的是会出现意象不到的错误，但可能依然会编译通过，因为它是通过检查模板表达式是否合法来确定类型参数的接口约束（参考《Effective C++》中的条款41）。所以在描述类型参数的约束时，我会避免使用隐式接口约束，而是使用一些显式的接口约束工具。

全称量化

对类型参数进行全称量化，意味着模板对类型参数没有任何要求。模板函数可以在不知道任何类型细节的情况下完成任务。举个例子：

template <typename T>
T &identity(T &&item) { return item; }

在现实的程序中我们几乎见不到使用了全称量化的模板函数，因为全称量化存在不少局限性，它对类型参数没有任何约束，几乎描述不了任何有意义的算法。全称量化虽然在描述函数多态性的能力上欠缺，但在描述容器多态性时还是有用的。例如说标准库里面的 vector ，它就不会对类型参数有任何约束（说没有其实是假的，至少它得有一个public的构造/析构函数吧，但你懂我的意思），但不妨碍它是一个被广泛应用的模板类。

存在量化

对类型参数进行存在量化，意味着对模板的类型参数存在要求，但这个要求并没有明确说明，只是说存在某个类型，使得这个模板能实例化。C++里面并没有描述存在量化的工具，这里暂时用形式化的方式去描述：

\rm type\ SomeType\ =\ \exists t. p(t)

其中 \rm t 是类型参量， \rm p(t) 是定义在类型参量上的算符，它输出一个类型定义。举个例子：

\rm type\ T\ =\ \exists t. \{ t\times (t\to Int) \}

这里定义了多态类型 \rm T ，我们并不知道什么样的类型 \rm t 会让 \rm T 实例化成一个合法的类型，但是我们知道如果一个对象 \rm obj 它具有多态类型 \rm T ，那它必然可以通过 \rm obj.second(obj.first) 来获得一个 \rm Int 型结果。这就是用存在量化所描述的多态的作用：它隐藏了类型的底层实现，只暴露出类型的结构和行为。

一个用来说明存在量化所描述的多态的最好例子是C++标准库里面的 stack<T, Container> 模板。它容纳的元素类型参数 T 是用全称量化进行描述，而 Container 则是用存在量化进行描述。这里面的含义就是说当我们使用一个由 stack 模板实例化成的栈时，我们不关心它的底层实现是什么样子的：是数组，队列，还是链表？我们只需要知道它提供了实现push、pop、top等栈独有的操作的底层支持即可。举个例子：

template <typename T, typename Container>
void traverseStack(stack<T, Container> &s) {
    while (!s.empty()) {
        // do something with s.top() ...
        s.pop();
// somewhere else ...
stack<int, deque<int>> s0;
stack<int, vector<int>> s1;
stack<int, list<int>> s2;
traverseStack(s0);
traverseStack(s1);
traverseStack(s2);

C++的编译器会自动帮我们推导出 stack 的具体类型、装载了什么类型的元素、使用了什么底层容器。但是作为模板函数的编写者，我们完全无需理会这一点：我知道这个 stack 肯定有一个合法的底层容器，但我不关心。这就是存在量化的好处，起到了信息隐藏的特点。

受限量化

前面我们说了，不对类型参数进行约束的话，模板函数几乎干不了什么有用的事情；只用存在量化对参数类型进行约束的话，我们又不知道约束的条件是什么，编写模板函数的时候依然没什么用。是时候给类型参数给予明确的约束了，受限量化就是这样一种有用的约束方式。

在讨论受限量化之前我们需要知道什么是超类型（supertype）和子类型（subtype），我们可以先把它理解为C++中的继承关系，但实际上并不一定要以继承的方式实现。我们这里只讨论记录类型（record type），也就是形如

\rm type\ T\ =\ \{x: Int,\ y: Float,\ f: Int\times Float \to Int\}

的类型。

好了，假如我们说类型 \rm T 是一个超类型，那么它的子类型应该长什么样？答案是必须包含 \rm T 所包含的所有成员，但可以拥有 \rm T 没有的成员，一般写成这样：

\rm type\ T1\ =\ \{..., x: Int, y: Float, f: Int\times Float\to Int, ...\}

我们用 \rm T1 \le T 来表示 \rm T1 是 \rm T 的一个子类型。但实际上如果我们有 \rm Int 和 \rm Float 的子类型 \rm SubInt 和 \rm SubFloat ，以及它们的超类型 \rm SuperInt 和 \rm SuperFloat 那么如下的类型也是 \rm T 的一个子类型：

\rm type\ T2\ =\ \{..., x: SubInt, y: SubFloat, f: SuperInt\times SuperFloat\to SubInt, ...\}

因此如果一个类型中如果存在一组与超类型所有成员重名的成员，并且这些成员所拥有的类型是超类型对应成员的类型的子类型，那么它也是合法的子类型。(这里大家可能不理解为什么函数类型 \rm SuperInt\times SuperFloat \to SubInt 是函数类型 \rm Int\times Float \to Int 的子类型，可以参考我下一篇文章： 编程语言中的协变与逆变 )。

类型参数 \rm T 的受限量化是指给定一个类型 \rm T0 ， \rm T 必须是 \rm T0 的一个子类型。受限量化约束既描述了类型参数在接口上的限制，也描述了在成员上的要求。

那么C++中怎么表达这种受限量化对应的多态呢？最规范的方式是用继承来实现，但是这个我打算放到最后一小节来说，因为这一节是关于参数型多态，我还是希望用模板的方式来表达。所以这里我用Concept这个工具来描述受限量化，因为Concept这个工具可以表达非常丰富的类型参数约束。不过要注意的是，Concept严格来说是不能表达受限量化的，在下面的例子中我会提到。我先用上面举的 \rm T 和 \rm T1 之间的关系作为例子：

template <typename T>
concept SuperType = requires(T t) {
    { t.x } -> int;
    { t.y } -> float;
    { t.f(t.x, t.y) } -> int;
template <SuperType T>
void doProcess(T &t) {
    t.x = t.f(t.x, t.y);
struct SubType1 {
    int x;
    float y;
    int f(int, float) { return 0; }
    bool isSubType;
struct NotSubType {
    int x[10];
    float y;
    int f(int, float) { return 0; }
struct NotSubTypeButCanCompile {
	float x;
    double y;
    int f(float, double) { return 0; }
// somewhere else ...
SubType s;
NotSubType ns;
NotSubTypeButCanCompile nsbc;
doProcess(s);	// ok, satisfy concept SuperType
doProcess(ns);	// error, not satisfy concept SuperType
doProcess(nsbc);	// ok, though nsbc is not a subtype of SuperType

这里面的定义了一个concept： SuperType ，任何满足 SuperType 这个concept的类型必须有 x 和 y 两个成员，并且类型分别为 int 和 float 。此外还必须有一个成员函数 int f(int, float) 。那么在定义模板函数时，如果想对类型参数进行受限量化，那直接在模板参数前加入 SuperType 就可以对参数进行受限量化。我们从上面的例子中可以看到， SubType 由于满足Concept SuperType 的约束，可以编译通过，但 NotSubType 就不能。

但正如我前面提到的：Concept并不能严格表达受限约束，所以即便 NotSubTypeButCanCompile 不是 SuperType 的子类型，但它仍然能编译通过，因为强制类型转换的机制存在。但是对于非基础类型而言，我们总可以禁止类进行任何非继承层次上的类型转换。

但是子类型的定义在成员类型上可以不那么严格，我们前面提到 \rm T2 也是 \rm T 的一个子类型，这样的受限量化关系用Concept也是可以表示的：

struct SuperInt { int a; };
struct Int : public SuperInt {};
struct SubInt : public Int {};
struct SuperFloat { float a; };
struct Float : public SuperFloat {};
struct SubFloat : public Float {};
template <typename T>
concept SuperType = requires(T t) {
    { t.x } -> Int;
    { t.y } -> Float;
    { t.f(a, b) } -> Int;
template <SuperType T>
void doProcess(T &t) {
    t.x = t.f(t.x, t.y);
struct SubType2 {
	SubInt x;
    SubFloat y;
    SubInt f(SuperInt, SuperFloat) { return SubInt; }
// somewhere else ...
SubType2 s2;
doProcess(s2);	// ok, SubType2 is a subtype of SuperType

F-受限量化

受限量化很强大，它使得任何能够运行在超类型上的函数都能安全地运行在子类型上。但是当类型的定义涉及到递归时，想用受限量化去表达多态就行不通了。所谓类型的递归定义，是指：

\rm type\ T\ =\ p(T)

其中 \rm p 是一个作用在类型上的算符，输出一个类型定义，显然这里对 \rm T 的定义需要用到 \rm T 。假如我想描述这样一种多态：只要这个类型 \rm T 具有一个接受两个 \rm Int 型参数，并输出类型 \rm T 的方法，也就是： \rm type\ T\ =\ \{..., f:\ Int\times Int\to T, ...\} ，那么某个函数 doPorcess 就能允许在其上。那我们显然没办法用受限量化去描述这种约束，因为强行用受限量化的话子类型的方法 \rm f 返回的就不是自身类型，而是超类型。

F-受限量化解决了上述问题，它的形式化描述是这样的：

\rm type\ T\ =\ F(T).p(T)

其中 \rm F(T) 是对参数 \rm T 的一种约束。放到这里的话 \rm F(T) 长这样：

\rm F(T)\ =\ \{f:\ Int\times Int\to T\}

也就是说 \rm F 要求类型 \rm T 必须有方法 \rm f ，并在这个基础上用 \rm p(T) 定义 \rm T 。

F-受限量化的一个例子就是在文章一开头所介绍的CRTP的例子了，在那里 Advancable<T> 就相当于 \rm F(T) ， IntPointer 继承 Advancable<IntPointer> 使得它继承了 IntPointer &advance(size_t) 这个方法，因此也就满足的 \rm F(T) 约束。随后 IntPointer 的结构定义体就相当于这里的 \rm p(T) 。

当然， Advancable 也可以用Concept来表述：

template <typename T>
concept Advancable = requires(T t, size_t n) {
    { t.advance(size_t n) } -> T &;  
template <Advancable T>
T &advance(T &item, size_t n) {
    return item.advance(n);

效果也是一样的。不过CRTP还有静态多态和减少代码冗余等优点，因此Concept的出现并不会替代CRTP。

包涵型多态

我们前面说过表达超类型-子类型关系的一种规范方法是继承。继承在C++中通常的用法是：

struct SuperType {
    virtual void move(int, int) = 0;
protected:
    int x, y;
struct SubType1 : public SuperType {
	void move(int a, int b) override { x += a; y += b; }
struct SubType2 : public SuperType {
	void move(int a, int b) override { x -= a; y -= b; }