C ++ Double Dispatch for Equals ()

Question

Imagine an abstract base class of Shape , with derived classes of Circle and Rectangle .

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

I need to determine if two shapes are equal if 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 shape.)

The recommended way to do this is double dispatch . What I came up with is (it’s very simplified here, so the forms are equal to all other forms 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 and friend function to the Shape for each derived class. Then I need to copy-paste the exact same equals function into each derived class. This is an awful lot of patterns, say 10 different shapes!

Is there an easier way to do this?

dynamic_cast out of the question; too slow. (Yes, I compared this. Speed ​​matters in my application.)

I tried this, but it does not 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 in the same form. Sending always seems to select the underlying function is_equal(Shape&) , even if a “more specific” match is available. This probably makes sense, but I don't understand how to send C ++ well enough to understand why.

Answer 1

When creating such methods:

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

And in a subclass

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

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

You will need to define the individual 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 probably don't approach the performance or simplicity of how the C programmer does 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 make your code more complex than version C, you might wonder if you can solve this problem with overloading and virtual methods.

Answer 2

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

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

The presented solution includes lengthy explanations on working with functors and casts to avoid unpleasant errors in the presence of multiple (and virtual) inheritance.

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

Answer 3

You can use type enumeration and static casting if dynamic_cast 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; } }; 

Answer 4

I usually refer to dynamic_cast and virtual funcntions. If the compiler is not too dumb, dynamic one-step casting is no different from the two transitions in the vtable.

 class shape { protected: virtual bool is_equal(const shape* s) const=0; friend bool oeprator==(const shape& a, cost shape& b) { return a.is_equal(&b); } }; class circle: public shape { double radius; point<duouble> center; protected: virtual bool is_equal(const shape* s) const { const circle* p = dynamic_cast<const circle*>(s); return p && p->radius==radius && p->center==center; } }; 

The same goes for a rectangle or any other shape. in principle, double scheduling requires - if N are classes, then functions N ² . So you just need N functions (one for each class).

If you feel that the dynamic tide is too slow, you can use the enumeration declared in the base class and are correctly initialized by the derived classes. But this requires that you update the enum values ​​each time a new class is added. For example: classic shape {protected: enum shapes_type {no_shape, circle_shape, rectangle_shape}; shape_type my_type; virtual bool is_equal (const shape * s) const = 0; friend bool oeprator == (const shape & a, cost shape & b) {return a.is_equal (& b); } shape (): my_type (no_shape) {}};

 class circle: public shape { double radius; point<duouble> center; protected: virtual bool is_equal(const shape* s) const { const circle* p = static_cast<const circle*>(s); return my_type == s->my_type && p->radius==radius && p->center==center; } public: circle() { my_type = circle_shape; } }; 

If you rely on base_defined an enumeration is unacceptable (an unknown number of possible classes), you can rely on a simple value (for example: an integer), which can be a unidirectional type with a trick like:

 int int_generator() { static int x=0; return ++x; } template<class T> int id_for_type() { static int z = int_generator(); return z; } class shape { ... int my_type; }; class circle { ... circle() { my_type = id_for_type<circle>(); } }; 

Answer 5

Virtual functions can easily replace dynamic_cast RTTI type checking, for example: http://ideone.com/l7Jr5

 struct Shape { struct subtype { enum { Shape, Circle, Rectangle, ColoredCircle }; }; virtual bool is_a( int type ) const { return type == subtype::Shape; } virtual bool is_equal(const Shape& s) const { return false; } }; struct Rectangle : Shape { virtual bool is_a( int type ) const { return type == subtype::Rectangle || Shape::is_a(type); } virtual bool is_equal(const Shape& s) const { if (!s.is_a(subtype::Rectangle)) return false; const Rectangle& r = static_cast<const Rectangle&>(s); return true; // or check width and height } }; struct Circle : Shape { virtual bool is_a( int type ) const { return type == subtype::Circle || Shape::is_a(type); } virtual bool is_equal(const Shape& s) const { if (!s.is_a(subtype::Circle)) return false; const Circle& c = static_cast<const Circle&>(s); return true; // or check radius } }; struct ColoredCircle : Circle { virtual bool is_a( int type ) const { return type == subtype::ColoredCircle || Circle::is_a(type); } }; int main(void) { Rectangle x; Shape y; return x.is_equal(y); } 

-

Why are there 10 copies of the “exact” function? Shouldn't Rectangle::is_equal(const Rectangle&) const compare rectangle-specific elements?

If all the rectangles fall into the same equivalence class, as is the case with the code you showed, then you can just have a single virtual function that returns the equivalence class.

Answer 6

In my projects, I move the Shape::operator== method to private and do not implement it. The amount of work to properly resolve this is not worth the effort.

In other words, the given Shape * vector:

 std::vector<Shape *> my_shapes; 

I can do the following:

 my_shapes.push_back(new Rectangle); my_shapes.push_back(new Circle); 

The problem occurs when comparing objects:

 Shape * p_shape_1 = my_shapes[0]; Shape * p_shape_2 = my_shapes[1]; if (*p_shape_1 == *p_shape_2) {...} 

The expression is equivalent to:

p_shape_1-> operator == (* p_shape_2);

If a virtual or polymorphic operation is in effect, it becomes:

Rectangle :: operator == ((circle));

In other words, there is a high probability that the Rectangle will compare itself with a circle or other figure; wrong comparison.

So, in my projects, I forbid equality comparisons based on pointers to the base class. The only material that can be compared using pointers to base classes is content in the base class.