31.让函数根据一个以上的对象类型来决定如何虚化

Posted on | In

问题实例

 
假设我们在设计一个游戏，游戏的背景发生在太空，有宇宙飞船、太空站和小行星等对象。这些对象可能会发生碰撞，有规则如下：

  • 如果飞船和空间站以低速接触，飞船将泊入空间站。否则，它们将有正比于相对速度的损坏。
  • 如果飞船与飞船，或空间站与空间站相互碰撞，参与者均有正比于相对速度的损坏。
  • 如果小行星与飞船或空间站碰撞，小行星毁灭。如果是小行星体积较大，飞船或空间站也毁坏。
  • 如果两个小行星碰撞，将碎裂为更小的小行星，并向各个方向溅射。

问题分析

 
首先开始分析对象共性。显然，它们都在运动，都有一个速度描述运动，因此应该存在一个抽象基类，让各对象从抽象基类中派生出来。继承体系如下：image_1cc8b0o0hd4smo21uu2166j18fc9.png-53.9kB

1
2
3
4
class GameObject { ... };
class SpaceShip: public GameObject { ... };
class SpaceStation: public GameObject { ... };
class Asteroid: public GameObject { ... };

接着我们准备撰写最关键的碰撞函数：
1
2
3
4
5
6
7
8
void checkForCollision(GameObject& object1,GameObject& object2){
    if (theyJustCollided(object1, object2)) {
        processCollision(object1, object2);
    }
    else {
        ...
    }
}

processCollision函数必然是一个虚函数，但关键问题在于，该函数的虚化并非由一个对象类型决定，而是由两个对象类型共同决定。
这种二重调度问题被称为double dispatch，相应地当然也有multiple dispatch。C++并没有提供相应的功能，因此我们必须手动模拟编译器来进行实现。

虚函数+RTTI

 
我们在GameObject中申明一个虚函数collide。这个函数被派生类以通常的形式重载：

1
2
3
4
5
6
7
8
9
10
class GameObject {
public:
    virtual void collide(GameObject& otherObject) = 0;
    ...
};
class SpaceShip: public GameObject {
public:
    virtual void collide(GameObject& otherObject);
    ...
};

为了节约篇幅，下文只针对派生类SpaceShip做出详细描述，其他派生类的情况类似于SpaceShip。
实现double-dispatch最常见的写法就是if-else逻辑链。在这种方法中，我们首先判断rhs的真实类型，然后测试所有可能：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class CollisionWithUnknownObject {//异常类
public:
    CollisionWithUnknownObject(GameObject& whatWeHit);
    ...
};
void SpaceShip::collide(GameObject& otherObject){
    const type_info& objectType = typeid(otherObject);
    if (objectType == typeid(SpaceShip)) {
        SpaceShip& ss = static_cast<SpaceShip&>(otherObject);
        ...//process a SpaceShip-SpaceShip collision;
    }
    else if (objectType == typeid(SpaceStation)) {
        SpaceStation& ss = static_cast<SpaceStation&>(otherObject);
        ...//process a SpaceShip-SpaceStation collision;
    }
    else if (objectType == typeid(Asteroid)) {
        Asteroid& a = static_cast<Asteroid&>(otherObject);
        process a SpaceShip-Asteroid collision;
    }
    else {
        throw CollisionWithUnknownObject(otherObject);
    }
}

我们完全放弃了封装:每一个object都必须了解其同胞类的版本，一旦增了新类，我们必须更新每一个RTTI体系。
在没有虚函数的概念时，这种写法就是虚函数的粗陋实现，显然这种程序毫无维护性。

只使用虚函数

 
这个方法架构与RTTI版本其实无二，只不过其collide函数增加了各种重载版本，每一个重载处理一个类型：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class SpaceShip;
class SpaceStation;
class Asteroid;
class GameObject {
public:
    virtual void collide(GameObject& otherObject) = 0;
    virtual void collide(SpaceShip& otherObject) = 0;
    virtual void collide(SpaceStation& otherObject) = 0;
    virtual void collide(Asteroid& otherobject) = 0;
    ...
};
class SpaceShip: public GameObject {
public:
    virtual void collide(GameObject& otherObject);
    virtual void collide(SpaceShip& otherObject);
    virtual void collide(SpaceStation& otherObject);
    virtual void collide(Asteroid& otherobject);
    ...
};

其基本原理就是用两个单一调度实现二重调度，也就是说有两个单独的虚函数调用：以rhs作为函数调用的对象再次调用虚函数，*this的静态类型已知，可以直接匹配。
1
2
3
void SpaceShip::collide(GameObject& otherObject){
    otherObject.collide(*this);
}

该方法的缺陷和RTTI一样：每一个类都必须知道其同胞类，当增加新类时，所有代码必须更新，而且必须为每一个新类增加一个新的虚函数。如果当前依赖于某个运行库，这样的改动会导致整个运行库都必须重新编译。

模拟虚函数表

 
在More Effective C++ 24中我们提及了vtbl，虚函数实现的基础。使用vtbl，编译器避免了使用if…then…else链，并能在所有调用虚函数的地方生成同样的代码。我们没有理由无法在之前的RTTI体系中模拟vtbl。
首先，我们对GameObjcet继承体系中的函数作一些修改,为每个子类添加对应的碰撞函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class GameObject {
public:
    virtual void collide(GameObject& otherObject) = 0;
    ...
};
class SpaceShip: public GameObject {
public:
    virtual void collide(GameObject& otherObject);
    virtual void hitSpaceShip(SpaceShip& otherObject);
    virtual void hitSpaceStation(SpaceStation& otherObject);
    virtual void hitAsteroid(Asteroid& otherobject);
    ...
};
void SpaceShip::hitSpaceShip(SpaceShip& otherObject){
    process a SpaceShip-SpaceShip collision;
}
void SpaceShip::hitSpaceStation(SpaceStation& otherObject){
    process a SpaceShip-SpaceStation collision;
}
void SpaceShip::hitAsteroid(Asteroid& otherObject){
    process a SpaceShip-Asteroid collision;
}

在Spaceship::collide中，我们需要一个方法来映射参数otherObject的动态类型到一个成员函数指针，我们使用一个中间函数lookup来完成此工作:
1
2
3
4
5
6
class SpaceShip: public GameObject {
private:
    typedef void (SpaceShip::*HitFunctionPtr)(GameObject&);
    static HitFunctionPtr lookup(const GameObject& whatWeHit);
    ...
}

既然有了lookup，那么collide的实现就很简单了：
1
2
3
4
5
6
7
8
9
void SpaceShip::collide(GameObject& otherObject){
    HitFunctionPtr hfp = lookup(otherObject);
    if(hfp) {
        (this->*hfp)(otherObject);
    }
    else {
        throw CollisionWithUnknownObject(otherObject);
    }
}

接下来要做的就是保证动态类型与成员函数之间的映射了。

映射表

首先要做的是一个映射表。该映射表应该在它被使用前构造与初始化，并在不被需要时析构。以上操作应该由编译器自动完成，所以我们将映射表设为lookup函数中的static对象，在第一次调用lookup时构造，在main退出后自行析构：

1
2
3
4
5
6
7
8
9
10
11
class SpaceShip: public GameObject{
private:
    typedef void (SpaceShip::*HitFunctionPtr)(GameObject&);
    typedef map<string, HitFunctionPtr> HitMap;
    ...
};
SpaceShip::HitFunctionPtr
SpaceShip::lookup(const GameObject& whatWeHit){
    static HitMap collisionMap;
    ...
}

通过使用map的find函数，lookup实现如下：
1
2
3
4
5
6
7
SpaceShip::HitFunctionPtr
SpaceShip::lookup(const GameObject& whatWeHit){
    static HitMap collisionMap;
    auto mapEntry = collisionMap.find(typeid(whatWeHit).name());
    if (mapEntry == collisionMap.end()) return nullptr;
    return mapEntry->second;
}

初始化映射表

我们需要写一个私有的静态成员函数initializeCollisionMap来构造和初始化映射表，然后用其返回值来初始化collisionMap：

1
2
3
4
5
6
7
8
9
10
class SpaceShip: public GameObject {
private:
    static HitMap initializeCollisionMap();
    ...
};
SpaceShip::HitFunctionPtr
SpaceShip::lookup(const GameObject& whatWeHit){
    static HitMap collisionMap = initializeCollisionMap();
    ...
}

这种写法意味着我们需要拷贝赋值，如果初始化函数返回指针则可以避免该问题，但堆中对象又可能会发生资源泄露。考虑到RAII，我们可以将 collisionMap改为一个智能指针，它将在自己被析构时delete 所指向的对象：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class SpaceShip: public GameObject {
    private:static HitMap* initializeCollisionMap();
    ...
};
SpaceShip::HitFunctionPtr
SpaceShip::lookup(const GameObject& whatWeHit){
    static auto_ptr<HitMap> collisionMap(initializeCollisionMap());
    ...
}
SpaceShip::HitMap * SpaceShip::initializeCollisionMap(){
    HitMap *phm = new HitMap;
    (*phm)["SpaceShip"] = &hitSpaceShip;
    (*phm)["SpaceStation"] = &hitSpaceStation;
    (*phm)["Asteroid"] = &hitAsteroid;
    return phm;
}

但这无法通过编译，因为HitMap内包容的是一堆指向成员函数的指针，他们的参数类型都是GameObject，而hitSpaceShip等函数带的不一样。虽然对象类型可以隐式转换，但函数指针并没有这种转换关系。
使用reinterpret_cast并不是好主意，而且存在极大风险，当spaceship位于多继承体系下时，编译器可能会传输错误的地址。为了不采取类型转换，我们不得不把hit函数的形参改为统一的gameobject，然后在每一个函数中使用dynamic_cast：
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
class GameObject {
public:
    virtual void collide(GameObject& otherObject) = 0;
    ...
};
class SpaceShip: public GameObject {
public:
    virtual void collide(GameObject& otherObject);
    virtual void hitSpaceShip(GameObject& spaceShip);
    virtual void hitSpaceStation(GameObject& spaceStation);
    virtual void hitAsteroid(GameObject& asteroid);
    ...
};
void SpaceShip::hitSpaceShip(GameObject& spaceShip){
    SpaceShip& otherShip = dynamic_cast<SpaceShip&>(spaceShip);
    process a SpaceShip-SpaceShip collision;
}
void SpaceShip::hitSpaceStation(GameObject& spaceStation){
    SpaceStation& station = dynamic_cast<SpaceStation&>(spaceStation);
    process a SpaceShip-SpaceStation collision;
}
void SpaceShip::hitAsteroid(GameObject& asteroid){
    Asteroid& theAsteroid = dynamic_cast<Asteroid&>(asteroid);
    process a SpaceShip-Asteroid collision;
}

使用非成员碰撞函数

 
之前我们一直以成员函数指针存放于map中，这直接导致如果添加新类的话，依然存在更新成员函数的问题，这也导致了重新编译。
另外，当发生A撞B时，应该调用谁的成员函数呢?我们总以左侧参数决定调用对象，实际上我们应该认定，A与B的碰撞应该既不在A中处理也不在B中处理。
当我们把碰撞函数从类中移除，其文件组织形式大致如下：

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
26
27
28
29
30
#include "SpaceShip.h"
#include "SpaceStation.h"
#include "Asteroid.h"
namespace { //无名命名空间
    void shipAsteroid(GameObject& spaceShip,GameObject& asteroid);
    void shipStation(GameObject& spaceShip,GameObject& spaceStation);
    void asteroidStation(GameObject& asteroid,GameObject& spaceStation);
    ...
    void asteroidShip(GameObject& asteroid,GameObject& spaceShip){ 
        shipAsteroid(spaceShip, asteroid); 
    }
    void stationShip(GameObject& spaceStation,GameObject& spaceShip){ 
        shipStation(spaceShip, spaceStation); 
    }
    void stationAsteroid(GameObject& spaceStation,GameObject& asteroid){                            asteroidStation(asteroid, spaceStation); 
    }
    typedef void (*HitFunctionPtr)(GameObject&, GameObject&);
    typedef map<pair<string,string>, HitFunctionPtr > HitMap;
    pair<string,string> makeStringPair(const char *s1,const char *s2);
    HitMap* initializeCollisionMap();
    HitFunctionPtr lookup(const string& class1,const string& class2);
}//end namespace

void processCollision(GameObject& object1,GameObject& object2){
    HitFunctionPtr phf = lookup(typeid(object1).name(),typeid(object2).name());
    if(phf) 
        phf(object1, object2);
    else 
        throw UnknownCollision(object1, object2);
}

注意这里使用了无名命名空间，其特点在于命名空间内所有东西均被本文件所私有（类似于声明在文件范围内的static函数)
非成员映射需要两个类型名与一个HitFunctionPtr，但只要用pair把那两个string绑一起就好了。于是映射表初始化函数实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
namespace {
    pair<string,string> makeStringPair(const char *s1,const char *s2){ 
        return pair<string,string>(s1, s2); 
    }
} // end namespace
namespace {
    HitMap * initializeCollisionMap(){
        HitMap *phm = new HitMap;
        (*phm)[makeStringPair("SpaceShip","Asteroid")] =&shipAsteroid;
        (*phm)[makeStringPair("SpaceShip", "SpaceStation")] =&shipStation;
        ...
        return phm;
    }
} // end namespace

lookup 函数也必须被修改以处理pair<string,string>对象，并将它作为映射表的第一部分:
1
2
3
4
5
6
7
8
namespace {
    HitFunctionPtr lookup(const string& class1,const string& class2){
        static auto_ptr<HitMap> collisionMap(initializeCollisionMap());
        auto mapEntry = collisionMap->find(make_pair(class1, class2));
        if (mapEntry == collisionMap->end()) return nullptr;
        return (*mapEntry).second;
    }
} // end namespace

因为上述函数的声明都在无名命名空间中，因此实现也必须在无名命名空间中。

继承与模拟虚函数表

 
假设我们当前需要区分贸易飞船与军事飞船的区别，无疑，继承体系需要更改：
image_1cc8g09pf18qt12ag5u1hmh1r0am.png-76.5kB
我们会发现lookup根本找不到这两个子类，除非我们再次更新表，这样再次造成了重编译。

再次讨论初始化vtbl

 
之所以会出现上一个问题完全是由于我们的map是完全静态的，每当我们注册一个碰撞函数，其行为便被完全固定。从面向对象的角度而言，我们应该建立一个class存放映射表，并且为它提供动态修改映射关系的成员函数：

1
2
3
4
5
6
7
8
9
10
11
12
class CollisionMap {
public:
    typedef void (*HitFunctionPtr)(GameObject&, GameObject&);
    void addEntry(const string& type1,const string& type2,
                  HitFunctionPtr collisionFunction,bool symmetric = true);
    void removeEntry(const string& type1,const string& type2);
    HitFunctionPtr lookup(const string& type1,const string& type2);
    static CollisionMap& theCollisionMap();//单例模式
private:
    CollisionMap();
    CollisionMap(const CollisionMap&);
};

该类使用了单例模式，保证只存在一张表。同时允许增加对称性碰撞，自动添加对称关系。
为了确保发生碰撞前映射关系已存在，我们可以创建一个register类：
1
2
3
4
5
6
7
8
class RegisterCollisionFunction {
public:
    RegisterCollisionFunction(const string& type1,const string& type2,
                              CollisionMap::HitFunctionPtr collisionFunction,
                              bool symmetric = true){
        CollisionMap::theCollisionMap().addEntry(type1, type2,collisionFunction,symmetric);
    }
};

用户于是可以使用此类型的一个全局对象来自动地注册他们所需要的函数：
1
2
3
4
5
6
7
RegisterCollisionFunction cf1("SpaceShip", "Asteroid",&shipAsteroid);
RegisterCollisionFunction cf2("SpaceShip", "SpaceStation",&shipStation);
RegisterCollisionFunction cf3("Asteroid", "SpaceStation",&asteroidStation);
...
int main(int argc, char * argv[]){
    ...
}

因为这些全局对象在main被调用前就构造了，它们在构造函数中注册的函数也在main被调用前就加入了映射表。如果以后增加了一个派生类或新的碰撞对象，也只需要在主函数执行前加入即可，不需要修改库文件。