分类: C/C++
2009-08-26 15:32:05
有时,借用一下Jacqueline Susann的话:一次是不够的。例如你有着一个光辉形象、崇高声望、丰厚薪水的程序员工作,在Redmond,Wshington的一个著名软件公司--当然,我说的就是任天堂。为了得到经理的注意,你可能决定编写一个video game。游戏的背景是发生在太空,有宇宙飞船、太空站和小行星。
在你构造的世界中的宇宙飞船、太空站和小行星,它们可能会互相碰撞。假设其规则是:
l 如果飞船和空间站以低速接触,飞船将泊入空间站。否则,它们将有正比于相对速度的损坏。
l 如果飞船与飞船,或空间站与空间站相互碰撞,参与者均有正比于相对速度的损坏。
l 如果小行星与飞船或空间站碰撞,小行星毁灭。如果是小行星体积较大,飞船或空间站也毁坏。
l 如果两个小行星碰撞,将碎裂为更小的小行星,并向各个方向溅射。
这好象是个无聊的游戏,但用作我们的例子已经足够了,考虑一下怎么组织C++代码以处理物体间的碰撞。
我们从分析飞船、太空站和小行星的共同特性开始。至少,它们都在运动,所以有一个速度来描述这个运动。基于这一点,自然而然地设计一个基类,而它们可以从此继承。实际上,这样的类几乎总是抽象基类,并且,如果你留心我在Item M33中的警告,基类总是抽象的。所以,继承体系是这样的:
class GameObject { ... };
class SpaceShip: public GameObject { ... };
class SpaceStation: public GameObject { ... };
class Asteroid: public GameObject { ... };
现在,假设你开始进入程序内部,写代码来检测和处理物体间的碰撞。你会提出这样一个函数:
void checkForCollision(GameObject& object1,
GameObject& object2)
{
if (theyJustCollided(object1, object2)) {
processCollision(object1, object2);
}
else {
...
}
}
问题来了。当你调用processCollision()时,你知道object1和object2正好相撞,并且你知道发生的结果将取决于object1和object2的真实类型,但你并不知道其真实类型;你所知道的就只有它们是GameObject对象。如果碰撞的处理过程只取决于object1的动态类型,你可以将processCollision()设为虚函数,并调用object1.processColliion(object2)。如果只取决于object2的动态类型,也可以同样处理。但现在,取决于两个对象的动态类型。虚函数体系只能作用在一个对象身上,它不足以解决问题。
你需要的是一种作用在多个对象上的虚函数。C++没有提供这样的函数。可是,你必须要实现上面的要求。现在怎么办呢?
一种办法是扔掉C++,换种其它语言。比如,你可以改用CLOS(Common Lisp Object System)。CLOS支持绝大部分面向对象的函数调用体系中只能想象的东西:multi-method。multi-method是在任意多的参数上虚拟的函数,并且CLOS更进一步的提供了明确控制“被重载的multi-method将如何调用”的特性。
让我们假设,你必须用C++实现,所以必须找到一个方法来解决这个被称为“二重调度(double dispatch)”的问题。(这个名字来自于object-oriented programming community,在那里虚函数调用的术语是“message dispatch”,而基两个参数的虚调用是通过“double dispatch”实现的,推而广之,在多个参数上的虚函数叫“multiple dispatch”。)有几个方法可以考虑。但没有哪个是没有缺点的,这不该奇怪。C++没有直接提供“double dispatch”,所以你必须自己完成编译器在实现虚函数时所做的工作(见Item M24)。如果容易的话,我们可能就什么都自己做了,并用C语言编程了。我们没有,而且我们也不能够,所以系紧你的安全带,有一个坎途了。
l 用虚函数加RTTI
虚函数实现了一个单一调度,这只是我们所需要的一半;编译器为我们实现虚函数,所以我们在GameObject中申明一个虚函数collide。这个函数被派生类以通常的形式重载:
class GameObject {
public:
virtual void collide(GameObject& otherObject) = 0;
...
};
class SpaceShip: public GameObject {
public:
virtual void collide(GameObject& otherObject);
...
};
我在这里只写了派生类SpaceShip的情况,SpaceStation和Asteroid的形式完全一样的。
实现二重调度的最常见方法就是和虚函数体系格格不入的if...then...else链。在这种刺眼的体系下,我们首先是发现otherObject的真实类型,然后测试所有的可能:
// if we collide with an object of unknown type, we
// throw an exception of this type:
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
process a SpaceShip-SpaceShip collision;
}
else if (objectType == typeid(SpaceStation)) {
SpaceStation& ss =
static_cast
process a SpaceShip-SpaceStation collision;
}
else if (objectType == typeid(Asteroid)) {
Asteroid& a = static_cast
process a SpaceShip-Asteroid collision;
}
else {
throw CollisionWithUnknownObject(otherObject);
}
}
注意,我们需要检测的只是一个对象的类型。另一个是*this,它的类型由虚函数体系判断。我们现在处于SpaceShip的成员函数中,所以*this肯定是一个SpaceShip对象,因此我们只需找出otherObject的类型。
这儿的代码一点都不复杂。它很容易实现。也很容易让它工作。RTTI只有一点令人不安:它只是看起来无害。实际的危险来自于最后一个else语句,在这儿抛了一个异常。
我们的代价是几乎放弃了封装,因为每个collide函数都必须知道所以其它同胞类中的版本。尤其是,如果增加一个新的类时,我们必须更新每一个基于RTTI的if...then...else链以处理这个新的类型。即使只是忘了一处,程序都将有一个bug,而且它还不显眼。编译器也没办法帮助我们检查这种疏忽,因为它们根本不知道我们在做什么(参见Item E39)。
这种类型相关的程序在C语言中已经很有一段历史了,而我们也知道,这样的程序本质上是没有可维护性的。扩充这样的程序最终是不可想象的。这是引入虚函数的主意原因:将产生和维护类型相关的函数调用的担子由程序员转给编译器。当我们用RTTI实现二重调度时,我们正退回到过去的苦日子中。
这种过时的技巧在C语言中导致了错误,它们C++语言也仍然导致错误。认识到我们自己的脆弱,我们在collide函数中加上了最后的那个else语句,以处理如果遇到一个未知类型。这种情况原则上说是不可能发生的,但在我们决定使用RTTI时又怎么知道呢?有很多种方法来处理这种未曾预料的相互作用,但没有一个令人非常满意。在这个例子里,我们选择了抛出一个异常,但无法想象调用者对这个错误的处理能够比我们好多少,因为我们遇到了一个我们不知道其存在的东西。
l 只使用虚函数
其实有一个方法可以将用RTTI实现二重调度固有风险降到最低的,不过在此之前让我们看一下怎么只用虚函数来解决二重调度问题。这个方法和RTTI方法有这同样的基本构架。collide函数被申明为虚,并被所有派生类重定义,此外,它还被每个类重载,每个重载处理一个派生类型:
class SpaceShip; // forward declarations
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);
...
};
其基本原理就是用两个单一调度实现二重调度,也就是说有两个单独的虚函数调用:第一次决定第一个对象的动态类型,第二次决定第二个对象动态类型。和前面一样,第一次虚函数调用带的是GameObject类型的参数。其实现是令人吃惊地简单:
void SpaceShip::collide(GameObject& otherObject)
{
otherObject.collide(*this);
}
粗一看,它象依据参数的顺序进行循环调用,也就是开始的otherObject变成了调用成员函数的对象,而*this成了它的参数。但再仔细看一下啦,它不是循环调用。你知道的,编译器根据参数的静态类型决定调那一组函数中的哪一个。在这儿,有四个不同的collide函数可以被调用,但根据*this的静态类型来选中其中一个。现在的静态类型是什么?因为是在SpaceShip的成员函数中,所以*this肯定是SpaceShip类型。调用的将是接受SpaceShip参数的collide函数,而不是带GameOjbect类型参数的collide函数。
所有的collide函数都是虚函数,所以在SpaceShip::collide中调用的是otherObject真实类型中实现的collide版本。在这个版本中,两个对象的真实类型都是知道的,左边的是*this(实现这个函数的类的类型),右边对象的真实类型是SpaceShip(申明的形参类型)。
看了SpaceShip类中的其它collide的实现,就更清楚了:
void SpaceShip::collide(SpaceShip& otherObject)
{
process a SpaceShip-SpaceShip collision;
}
void SpaceShip::collide(SpaceStation& otherObject)
{
process a SpaceShip-SpaceStation collision;
}
void SpaceShip::collide(Asteroid& otherObject)
{
process a SpaceShip-Asteroid collision;
}
你看到了,一点都不混乱,也不麻烦,没有RTTI,也不需要为意料之外的对象类型抛异常。不会有意料之外的类型的,这就是使用虚函数的好处。实际上,如果没有那个致命缺陷的话,它就是实现二重调度问题的完美解决方案。
这个缺陷是,和前面看到的RTTI方法一样:每个类都必须知道它的同胞类。当增加新类时,所有的代码都必须更新。不过,更新方法和前面不一样。确实,没有if...then...else需要修改,但通常是更差:每个类都需要增加一个新的虚函数。就本例而言,如果你决定增加一个新类Satellite(继承于GameObjcet),你必须为每个现存类增加一个collide函数。
修改现存类经常是你做不到的。比如,你不是在写整个游戏,只是在完成程序框架下的一个支撑库,你可能无权修改GameObject类或从其经常的框架类。此时,增加一个新的成员函数(虚的或不虚的),都是不可能的。也就说,你理论上有操作需要被修改的类的权限,但实际上没有。打个比方,你受雇于Nitendo,使用一个包含GameObject和其它需要的类的运行库进行编程。当然不是只有你一个人在使用这个库,全公司都将震动于每次你决定在你的代码中增加一个新类型时,所有的程序都需要重新编译。实际中,广被使用的库极少被修改,因为重新编译所有用了这个库的程序的代价太大了。(参见Item M34,以了解怎么设计将编译依赖度降到最低的运行库。)
总结一下就是:如果你需要实现二重调度,最好的办法是修改设计以取消这个需要。如果做不到的话,虚函数的方法比RTTI的方法安全,但它限制了你的程序的可控制性(取决于你是否有权修改头文件)。另一方面,RTTI的方法不需要重编译,但通常会导致代码无法维护。自己做抉择啦!
l 模拟虚函数表
有一个方法来增加选择。你可以回顾Item M24,编译器通常创建一个函数指针数组(vtbl)来实现虚函数,并在虚函数被调用时在这个数组中进行下标索引。使用vtbl,编译器避免了使用if...then...else链,并能在所有调用虚函数的地方生成同样的代码:确定正确的vtbl下标,然后调用vtbl这个位置上存储的指针所指向的函数。
没理由说你不能这么做。如果这么做了,不但使得你基于RTTI的代码更具效率(下标索引加函数指针的反引用通常比if...then...else高效,产生的代码也少),同样也将RTTI的使用范围限定在一处:你初始化函数指针数组的地方。提醒一下,看下面的内容前最好做一下深呼吸( I should mention that the meek may inherit the earth, but the meek of heart may wish to take a few deep breaths before reading what follows)。
对GameObjcet继承体系中的函数作一些修改:
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;
}
和开始时使用的基于RTTI的方法相似,GameObjcet类只有一个处理碰撞的函数,它实现必须的二重调度的第一重。和后来的基于虚函数的方法相似,每种碰撞都由一个独立的函数处理,不过不同的是,这次,这些函数有着不同的名字,而不是都叫collide。放弃重载是有原因的,你很快就要见到的。注意,上面的设计中,有了所有其它需要的东西,除了没有实现Spaceship::collide(这是不同的碰撞函数被调用的地方)。和以前一样,实现了SpaceShip类,SpaceStation类和Asteroid类也就出来了。
在SpaceShip::collide中,我们需要一个方法来映射参数otherObject的动态类型到一个成员函数指针(指向一个适当的碰撞处理函数)。一个简单的方法是创建一个映射表,给定的类名对应恰当的成员函数指针。直接使用一个这样的映射表来实现collide是可行的,但如果增加一个中间函数lookup时,将更好理解。lookup函数接受一个GameObject参数,返回相应的成员函数指针。
这是lookup的申明:
class SpaceShip: public GameObject {
private:
typedef void (SpaceShip::*HitFunctionPtr)(GameObject&);
static HitFunctionPtr lookup(const GameObject& whatWeHit);
...
};
函数指针的语法不怎么优美,而成员函数指针就更差了,所以我们作了一个类型重定义。
既然有了lookup,collide的实现如下:
void SpaceShip::collide(GameObject& otherObject)
{
HitFunctionPtr hfp =
lookup(otherObject); // find the function to call
if (hfp) { // if a function was found
(this->*hfp)(otherObject); // call it
}
else {
throw CollisionWithUnknownObject(otherObject);
}
}
如果我们能保持映射表和GameObject的继承层次的同步,lookup就总能找到传入对象对应的有效函数指针。人终究只是人,就算再仔细,错误也会钻入软件。这就是我们为什么检查lookup的返回值并在其失败时抛异常的原因。
剩下的就是实现lookup了。提供了一个对象类型到成员函数指针的映射表后,lookup自己很容易实现,但创建、初始化和析构这个映射表是个有意思的问题。
这样的数组应该在它被使用前构造和初始化,并在不再被需要时析构。我们可以使用new和delete来手工创建和析构它,但这时怎么保证在初始化以前不被使用呢?更好的解决方案是让编译器自动完成,在lookup中把这个数组申明为静态就可以了。这样,它在第一次调用lookup前构造和初始化,在main退出后的某个时刻被自动析构(见Item E47)。
而且,我们可以使用标准模板库提供的map模板来实现映射表,因为这正是map的功能:
class SpaceShip: public GameObject {
private:
typedef void (SpaceShip::*HitFunctionPtr)(GameObject&);
typedef map
...
};
SpaceShip::HitFunctionPtr
SpaceShip::lookup(const GameObject& whatWeHit)
{
static HitMap collisionMap;
...
}
此处,collisionMap就是我们的映射表。它映射类名(一个string对象)到一个Spaceship的成员函数指针。因为map
给出了collisionMap后,lookup的实现有些虎头蛇尾。因为搜索工作是map类直接支持的操作,并且我们在typeid()的返回结果上总可以调用的(可移植的)一个成员函数是name()(可以确定(注11),它返回对象的动态类型的名字)。于是,实现lookup,仅仅是根据形参的动态类型在collisionMap中找到它的对应项、
lookup的代码很简单,但如果不熟悉标准模板库的话(再次参见Item M35),就不会怎么简单了。别担心,程序中的注释解释了每一步在做什么。
SpaceShip::HitFunctionPtr
SpaceShip::lookup(const GameObject& whatWeHit)
{
static HitMap collisionMap; // we'll see how to
// initialize this below
// look up the collision-processing function for the type
// of whatWeHit. The value returned is a pointer-like
// object called an "iterator" (see Item 35).
HitMap::iterator mapEntry=
collisionMap.find(typeid(whatWeHit).name());
// mapEntry == collisionMap.end() if the lookup failed;
// this is standard map behavior. Again, see Item 35.
if (mapEntry == collisionMap.end()) return 0;
// If we get here, the search succeeded. mapEntry
// points to a complete map entry, which is a
// (string, HitFunctionPtr) pair. We want only the
// second part of the pair, so that's what we return.
return (*mapEntry).second;