C++ Double Dispatch for Equals()

Imagine I have abstract base class Shape, with derived classes Circle and Rectangle.

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

I need to determine if two shapes are equal, assuming I have two Shape* pointers. (This is because I have two instances of vector<Shape*> and I want to see if they have the same shapes.)

The recommended way to do this is double dispatch. What I've come up with is this (greatly simplified here, so that shapes are equal to all other shapes of the same type):

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; };
};

This works, but I have to add a separate equals function and friend declaration in Shape for each derived class. Then I have to copy-paste the exact same equals function into each derived class, too. This is an awful lot of boilerplate for say, 10 different shapes!

Is there a simpler way to do it?

dynamic_cast is out of the question; too slow. (Yes, I benchmarked it. Speed matters in my app.)

I tried this but it doesn't work:

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() always returns false, even on identical shapes. It seems dispatch is always choosing the is_equal(Shape&) base function, even when a "more specific" match is available. This probably makes sense but I don't understand C++ dispatch well enough to know why.

Solution 1:

When you create methods like this:

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

And in the subclass,

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

These are not the same method. You have two separate virtual methods, neither of which is overridden (they are overloaded not even overloaded, as Ben Voigt pointed out). When you call Shape::is_equal, there is only one version: Shape::is_equal(Shape&)... which is not overridden and always returns false.

You would have to define the separate overloaded methods in the parent class and then override them in the child class. For example,

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; };
};

However, using tricks like this, you will probably not approach the performance or simplicity of the way a C programmer would do it:

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:
        ...;
    }
}

If overloading and virtual methods are making your code more complicated than the C version, then you may wish to rethink whether you solve this particular problem with overloading and virtual methods.

Solution 2:

Double-dispatch has been well studied. The generalization of double-dispatch is called a "multi-method".

Chapter 11 of Modern C++ Design addresses this issue in detail. The approach using dynamic_cast<> that you described is in section 11.3 "Double Switch-on-Type: Brute Force". The author even describes how to automate most of the work and automatically generate the symmetric overloads. Then, the author introduces a logarithmic dispatch based on std::map<> and std::type_info. Finally, the section ends with "Constant-Time Multimethods: Raw Speed" that's (roughly) based on a matrix of callback functions.

The presented solution includes lengthy explanations on handling functors and casts to avoid nasty pitfalls in presence of multiple (and virtual) inheritance.

If you consider implementing multi-methods in C++, I stronly recommend that you read the book and implement the proposed solution.

Solution 3:

You could use a type enumeration and static casting if dynamic_cast is too slow...

enum ShapeType
{
    SHAPE_TYPE_CIRCLE,
    SHAPE_TYPE_RECTANGLE
};

struct Shape
{
    virtual ShapeType GetShapeType() const = 0;
    virtual bool isEqual(const Shape& other) const = 0;
};

struct Circle : Shape
{
    virtual ShapeType GetShapeType() const { return SHAPE_TYPE_CIRCLE; }

    virtual bool isEqual(const Shape& other) const
    {
        if (other.GetShapeType() == SHAPE_TYPE_CIRCLE)
        {
            const Circle *circle = static_cast<const Circle*>(&other);

            // do some circle specific comparison
            return true;
        }
        return false;
    }
};