C++ 多态

Posted on Edited on

Preface

「多态」是一个很宽泛的理念，对应繁多实现。本文将记录我所看到的多态的各种形态。作者见识短浅，还请读者多多指教。

  • 本文已计划的内容：
    • 基于 std::visit
      • 实现运行时多态的优化
      • 实现重载模式
    • CRTP 实现静态多态
      • 静态多态
      • 静态接口
      • CRTP 的一些分析和 trick
    • C++20 前基于 SFINAE 的模板偏特化
    • C++20 后基于 concepts 的模板特化
    • Hack 虚函数表，用于优化
  • 本文不会出现的内容：
    • virtual 虚函数的基础用法
    • 函数指针模拟虚函数
    • 运行时反射

std::visit

Runtime Branching

假如你要对一个矢量做线性变换 $\vec{x} = k \cdot \vec{x} + b$，又想针对 $k=1$ 或 $b=0$ 的情况做优化，应该怎么办？

这是最简单却很慢的代码：

1
2
3
4
5
6
for (int i=0; i<n; ++i) {
    if (k != 1)
        x[i] *= k;
    if (b != 0)
        x[i] += b;
}

这段代码满足速度要求，但是太啰嗦：

1
2
3
4
5
6
7
8
9
10
11
12
13
if (k == 1) {
    if (b == 0) {
        // ...
    } else {
        // ...
    }
} else {
    if (b == 0) {
        // ...
    } else {
        // ...
    }
}

想两全其美怎么办？可以利用 variant 搭配 visit 使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// since C++17
using bool_variant = std::variant<std::true_type, std::false_type>;

constexpr bool_variant to_variant(bool x) {
    if (x)
        return std::true_type{};
    else
        return std::false_type{};
}

void linear(std::vector<int> &x, int k, int b) {
    bool_variant has_k = to_variant(k != 1);
    bool_variant has_b = to_variant(b != 0);

    auto transform = [=, &x](auto has_k, auto has_b) {
        for (auto &xi : x) {
            if constexpr (has_k)
                xi *= k;
            if constexpr (has_b)
                xi += b;
        }
    };

    std::visit(transform, has_k, has_b);
}

此时编译器为 transform 生成四个特化版本，正是我们想要的东西。std::visit() 会在运行时判断 variant 内储存的是哪个 type，然后挑选正确的重载分支。

variant + constexpr if 并不是唯一的玩法，我们来看看 cppreference 还有什么花活。

The Overload Pattern

假设你要 log 一个 variant<int, float, string>，你刚刚学到了 constexpr if，于是你想到这一段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template<class> inline constexpr bool always_false_v = false;

using ifs_variant = std::variant<int, float, std::string>;

void log(const ifs_variant &arg) {
    auto logger = [](const auto &arg) {
        using T = std::decay_t<decltype(arg)>;
        if constexpr (std::is_same_v<T, int>) {
            std::cout << "int: " << arg << "\n";
        } else if constexpr (std::is_same_v<T, float>) {
            std::cout << "float: " << arg << "\n";
        } else if constexpr (std::is_same_v<T, std::string>) {
            std::cout << "string: " << arg << "\n";
        } else {
            static_assert(always_false_v<T>, "non-exhaustive visitor!");
        }
    };
    
    std::visit(logger, arg);
}

三秒之后你觉得这段代码太丑，太多的 if constexpr 和 is_same_v 语句影响阅读，你也不想用 always_false_v<T> 这样的孤儿代码。于是你想到了重载 opeartor()：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void log(const ifs_variant &arg) {
    struct {
        void operator()(int i) {
            std::cout << "int: " << i << "\n";
        }
        void operator()(float f) {
            std::cout << "float: " << f << "\n";
        }
        void operator()(const std::string &s) {
            std::cout << "string: " << s << "\n";
        }
    } logger;
    
    std::visit(logger, arg);
}

这段代码会在缺少某个重载时报错（模板巨型报错），长度也合理，你的血压下降了一些，但仍未到安全区，因为 void operator() 的重复依然很丑。你想用模板元编程自动化这些函数重载。你的目标是：

1
2
3
4
5
template <typename... Lambdas>
struct Overloaded : Lambdas... {
    // Import all function whatever the parameter is.
    using Lambdas::operator()...; 
};

这样当你用 lambda 的类型做模板参数，就能自动导入 lambda 的 opeartor()。问题来了，你怎么传入 lambda 的类型？你根本没有办法用尖括号 <> 来指定 lambda 类型！而自动类型推导至少需要一个函数调用，你想到了构造函数！可以在构造函数中传入 lambda，这样就能推导出 Lambdas 的具体类型！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <typename... Lambdas>
struct Overloaded : Lambdas... {
    using Lambdas::operator()...;

    Overloaded(Lambdas&&...) {} // Bang!
};

void log(const ifs_variant &arg) {
    auto logger = Overloaded{
        [](int i) { std::cout << "int: " << i << "\n"; },
        [](float f) { std::cout << "float: " << f << "\n"; },
        [](const std::string &s) { std::cout << "string: " << s << "\n"; },
    };
    
    std::visit(logger, arg);
}

Bang! 第五行编译报错，编译器说，你企图使用 Lambda 的默认构造函数，但这个函数是 deleted！

想了半天，你顿悟过来，Overloaded 的构造函数一定要显式调用 Lambdas 的构造函数才行，于是你写出：

1
2
3
4
5
6
template <typename... Lambdas>
struct Overloaded : Lambdas... {
    using Lambdas::operator()...;

    Overloaded(Lambdas &&...t) : Lambdas{std::forward<Lambdas>(t)}... {};
};

编译终于过了！你还擅长举一反三，联想到 make_tuple() 可以在没有尖括号 <> 的情况下工作，你可以模仿它，于是你写出：

1
2
3
4
5
6
7
8
9
10
template <typename... Lambdas>
struct Overloaded : Lambdas... {
    using Lambdas::operator()...;
    // no more explicit ctor
};

template <typename... Lambdas>
constexpr auto make_Overloaded(Lambdas &&...t) {
    return Overloaded<Lambdas...>{std::forward<Lambdas>(t)...};
}

这段代码很秀也很正确。可惜好景不长，一个保洁阿姨路过了你，说，小伙子你写的不行，来看我秀一手：

1
2
template<class... Ts> struct Overloaded : Ts... { using Ts::operator()...; };
template<class... Ts> Overloaded(Ts...) -> Overloaded<Ts...>;

编译通过！阿姨的第二行模板恰好替代了 make_Overloaded，正确推导出所有模板参数！这是 C++17 的新功能 *Custom Template Argument Deduction Rules*。这一功能在 C++20 中更加智能，所以你可以删掉那行显式推导规则。

现在，你进化成了 std::visit 不用 Overloaded{} 就不舒服星人。

Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <string>
#include <variant> // C++17

using ifs_variant = std::variant<int, float, std::string>;

template<class... Ts> struct Overloaded : Ts... { using Ts::operator()...; };
template<class... Ts> Overloaded(Ts...) -> Overloaded<Ts...>;

void log(const ifs_variant &arg) {
    std::visit(Overloaded{
        [](int i) { std::cout << "int: " << i << "\n"; },
        [](float f) { std::cout << "float: " << f << "\n"; },
        [](const std::string &s) { std::cout << "string: " << s << "\n"; },
    }, arg);
}

int main() {
    ifs_variant i{10}, f(0.7f), s{"string"};
    log(i);
    log(f);
    log(s);
    return 0;
}

The CRTP

Curiously recurring template pattern (CRTP) 是指一个类的父类的模板参数含有自己。例如：

1
2
3
4
5
6
7
8
template<typename T>
class Counter {
    //...
};

class Foo : Counter<Foo> {
    //...
};

如此一来，父类在编译期就知道自己的派生类型，可以利用这一点做很多事，比如模板化的对象计数器、编译期多态、非退化的链式调用、模板化接口实现等等。网上很多声音说 CRTP 主要是用来消除动态绑定，但我认为 CRTP 主要是用来约束和简化代码的。我们来看看 CRTP 到底有什么用。

Static Polymorphism

由于父类知道派生类型，我们可以用 static_cast<T*>(this) 一步到位，将自己向下转型。还可以调用 T::static_func 实现静态分发。

Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>

template <typename T>
struct Base {
    void member_func() { static_cast<T *>(this)->member_func_impl(); }
    static void static_func() { T::static_func_impl(); }
};

struct Obj : Base<Obj> {
    void member_func_impl() { std::cout << "Obj::member_func_impl\n"; }
    static void static_func_impl() { std::cout << "Obj::static_func_impl\n"; }
};

int main() {
    Obj a;
    Base<Obj> &ref = a;
    ref.member_func();
    Base<Obj>::static_func();
    return 0;
}

会不会觉得有点脱裤子放屁？这样写有什么优势？用了 CRTP 之后，就宣告丧失了动态分发的能力，那为什么不干脆把 Base 类删掉呢？

有人说，Base 类描述了子类应该实现的几个函数，而且没有运行时开销。我认为最好使用 C++20 concept 来实现这种编译期约束。用 CRTP 是可以的，但是请注意标识符命名，我们来看一些 Bugs。

Bugs

1
2
3
4
5
6
7
8
9
10
template <typename T>
struct Base {
    // Notice the "T::member_func()"
    void member_func() { static_cast<T *>(this)->T::member_func(); }
    static void static_func() { T::static_func(); }
};

struct Obj : Base<Obj> {
    // empty!
};

编译没有任何报错，而程序在运行时会因为无穷递归而陷入栈溢出。所以千万不要为了美观，让子类重复基类的函数名。

我们再看一个人为制造的错误：

1
2
3
struct Obj : Base<Obj2> { // a bug compiles
    // implementation which is unused
}

编译器不会给你任何提醒，而你，Obj，沦为 Obj2 的替身。所幸的是，这个 bug 是可以修复的！只要将 Base 的构造函数设为私有，再加一个友元即可：

1
2
3
4
5
6
7
8
9
10
11
template <typename T>
struct Base {
private:
    Base() = default;
    friend T;
};

struct Obj2 {};

struct Obj : Base<Obj2> { // Instantiating Obj does not compile
};

现在，Obj 无权访问 Base 的构造函数，如果企图构造 Obj 对象，编译器会报错，然而你还是要检查半天才能发现，原来是 CRTP 写错了！更惨的是，如果你只调用静态成员，那么编译通过！天王老子来了都不报错！慢慢找 Bug 吧你就。

Template Interface Implementation

目前为止 CRTP 被我批评得太多了，实际上 CRTP 还是有点用的，它可以模板化接口实现，而这一点在 C++20 concept 中我暂时没发现对应的东西。

假设你要设计一个 Scaleable 接口，对于每一个具体类，它的逻辑都是：

1
2
3
4
5
6
7
struct Obj : Scaleable {
    // getter, setter ...

    override void scale(double k) {
        setValue(getValue() * k);
    }
}

你立即想到

  1. 你不需要 Scaleable 的动态绑定
  2. 每个类都复制粘贴一样的代码十分愚蠢
  3. C++20 concept 不能提供默认成员实现（作者以为的。如果可以请告诉我）

你知道可以用 CRTP！于是你设计出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <typename T>
struct Scaleable {
    template <typename K>
    T &scale(K &&multiplicator) {
        T &self = static_cast<T &>(*this);
        self.setValue(self.getValue() * multiplicator);
        return self;
    }
};

struct Obj : Scaleable<Obj> {
    double value;
    void setValue(double val) { value = val; }
    double getValue() { return value; }
};

这段代码很漂亮，还支持非退化的链式调用。最重要的是，它在 Obj 定义时就表明了 Scaleable 的语义。如果使用 C++20 concept 或者其他非成员函数去实现，scale 的实现就可能藏在某个 header 里，你不能一眼看出 Obj 是否 Scaleable，语义的表达就会被割裂。

聪明的你又想到了接口方法还可以是类外的方法：

1
2
3
4
5
6
template <typename T>
T &scale(Scaleable<T> &x, double k) {
    T &self = static_cast<T &>(x);
    self.setValue(self.getValue() * k);
    return self;
}

是不是很像 C++20 concept？我觉得很像！

A CRTP Helper

每次实现 CRTP 接口的时候，有很多重复工作要做，比如千篇一律的 static_cast 要写，还有 private ctor + friend class 定式，太繁琐。
本来使用 CRTP 的初衷就是简化代码，如今岂不是南辕北辙？

你想到可以抽象出所有的 CRTP 接口的公共部分，做成一个基类：

1
2
3
4
5
6
7
8
9
10
11
template <typename T>
struct CRTP {
    T &self() { return static_cast<T &>(*this); }
    const T &self() const { return static_cast<const T &>(*this); }
private:
    CRTP() = default;
    friend T;
};

template <typename T>
struct Scaleable : CRTP<T> { /* ... */ };

这看起来很美好，可是很快你又发现了问题：多个接口造成菱形继承：

1
2
3
4
// diamond inheritance: CRTP<T>
struct Obj : Scaleable<Obj>, Lengthable<Obj> { 
    // ...
};

这里使用虚继承无助于解决问题：被虚继承的基类是不能用 static_cast 向下转型的。

试过很多方案都不能解决菱形继承问题（如果有请告诉我），只能硬避开菱形继承了：

Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <typename T, template<typename> class Interface>
struct CRTP {
    T &self() { return static_cast<T &>(*this); }
    const T &self() const { return static_cast<const T &>(*this); }
private:
    CRTP() = default;
    friend Interface<T>;
};

template <typename T>
struct Scaleable : CRTP<T, Scaleable> { /* ... */ };


template <typename T>
struct Lengthable : CRTP<T, Lengthable> { /* ... */ };

这样一来，Scaleable 和 Lengthable 的基类是两个不同的类，同时保持了零开销抽象，完美解决问题。

仔细观察你会发现，CRTP 避开菱形继承的手段恰好是 CRTP！

顺便提醒一句，调用 self() 的时候必须写 this->self()，否则编译器不知道正确的名字空间。

Pros & Cons

你很可能已经感觉到把 CRTP 当作接口用有什么好处：

  1. 接口表达了清晰、明确的语义；
  2. 既可以重写实现，又可以提供默认实现，十分灵活；
  3. 编译期内联能力，零开销抽象；
  4. 链式调用时类型不会退化。
    但 CRTP 也有不足之处：
  5. 本质上是语言表达能力不足的妥协（还是推荐 concept）；
  6. 要求类继承接口，不利于库设计；
  7. 难以表达两种接口的交集；
  8. 容易写 Bug，编译报错信息不友好；
  9. 宣告放弃动态绑定，需要谨慎设计。

References