C++ Double Dispatch for Equals()

Question

想象一下,我有抽象的基类 Shape,派生类Circle和Rectangle.

class Shape {};
class Circle : public Shape {};
class Rectangle : public Shape {};

我需要确定两个形状是否相等,假设我有两个Shape*指针.(这是因为我有两个实例,vector<Shape*>我想看看它们是否具有相同的形状.)

建议的方法是双重调度.我想出的就是这个(这里大大简化了,所以形状等于同一类型的所有其他形状):

class Shape {
public:
    virtual bool equals(Shape* other_shape) = 0;
protected:
    virtual bool is_equal(Circle& circle) { return false; };
    virtual bool is_equal(Rectangle& rect) { return false; };
    friend class Circle;    // so Rectangle::equals can access Circle::is_equal
    friend class Rectangle; // and vice versa
};

class Circle : public Shape {
public:
    virtual bool equals(Shape* other_shape) { return other_shape->is_equal(*this); };
protected:
    virtual bool is_equal(Circle& circle) { return true; };
};

class Rectangle : public Shape {
public:
    virtual bool equals(Shape* other_shape) { return other_shape->is_equal(*this); };
protected:
    virtual bool is_equal(Rectangle& circle) { return true; };
};

这是有效的,但我必须为每个派生类添加一个单独的equals函数和friend声明Shape.然后我必须将完全相同的equals函数复制粘贴到每个派生类中.这是一个非常多的样板,比如10种不同的形状!

有更简单的方法吗？

dynamic_cast是不可能的; 太慢了.(是的,我对它进行了基准测试.速度在我的应用程序中很重要.)

我试过这个,但它不起作用:

class Shape {
public:
    virtual bool equals(Shape* other_shape) = 0;
private:
    virtual bool is_equal(Shape& circle) { return false; };
};

class Circle : public Shape {
public:
    virtual bool equals(Shape* other_shape) { return other_shape->is_equal(*this); };
private:
    virtual bool is_equal(Circle& circle) { return true; };
};

class Rectangle : public Shape {
public:
    virtual bool equals(Shape* other_shape) { return other_shape->is_equal(*this); };
private:
    virtual bool is_equal(Rectangle& circle) { return true; };
};

equals()即使在相同的形状上,也始终返回false.似乎派遣总是选择is_equal(Shape&)基本功能,即使可以使用"更具体"的匹配.这可能是有道理的,但我不太了解C++调度,知道原因.

Answer 1

当您创建这样的方法时:

virtual bool is_equal(Shape& circle) { return false; };

在子类中,

virtual bool is_equal(Circle& circle) { return true; };

这些方法不一样.你有两个独立的虚拟方法,它们都没有被覆盖(它们过载甚至没有超载,正如Ben Voigt指出的那样).当你打电话时Shape::is_equal,只有一个版本:Shape::is_equal(Shape&)...没有被覆盖,总是返​​回false.

您必须在父类中定义单独的重载方法,然后在子类中重写它们.例如,

class Shape {
    // Choice between these two methods happens at compile time...
    virtual bool is_equal(Circle& circle) { return false; };
    virtual bool is_equal(Rectangle& circle) { return false; };
};

class Rectangle : Shape {
    // Choice between this and Shape::is_equal(Rectangle&) happens at runtime...
    virtual bool is_equal(Rectangle& circle) { return true; };
};

但是,使用这样的技巧,你可能不会接近C程序员执行它的方式的性能或简单性:

typedef enum {
    SHAPE_CIRCLE,
    SHAPE_RECTANGLE
} shape_type_t;

struct shape {
    shape_type_t type;
};

struct circle {
    shape_type_t type;
    ...
};

struct rectangle {
    shape_type_t type;
    ...
};

bool shape_equal(struct shape *x, struct shape *y)
{
    if (x->type != y->type)
        return false;
    switch (x->type) {
    case SHAPE_CIRCLE:
        return circle_equal((struct circle *) x, (struct circle *) y);
    case SHAPE_RECTANGLE:
        ...;
    }
}

如果重载和虚拟方法使您的代码比C版本更复杂,那么您可能希望重新考虑是否通过重载和虚方法解决了这个特定问题.

Answer 2

双调度已经得到很好的研究.双调度的推广称为"多方法".

Modern C++ Design的第11章详细介绍了这个问题.使用dynamic_cast<>您所描述的方法在第11.3节"双开关类型:蛮力"中.作者甚至描述了如何自动化大部分工作并自动生成对称重载.然后,作者介绍了一种基于std::map<>和的对数调度std::type_info.最后,该部分以"Constant-Time Multimethods:Raw Speed"结尾,它(大致)基于回调函数矩阵.

所提出的解决方案包括处理仿函数和强制转换的冗长解释,以避免在存在多个(和虚拟)继承时出现令人讨厌的陷阱.

如果考虑在C++中实现多方法,我强烈建议您阅读本书并实现建议的解决方案.