C++ Double Dispatch for Equals()
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.
How can I implement double dispatch when I don't know all the classes in advance?
Why it doesn't work
The problem with your double dispatch implementation is that you expect that the most specific equalityCheck() is called.
But your implementation is totaly based on a polymorphic base class, and equalityCheck(const A*) overloads but does not override equalityCheck(const Base*) !
Otherwhise said, at compile time the compiler knows that A::equalityBounce() could call equalityCheck(A*) (because this is an A*), but unfortunately it calls Base::equalityCheck() which has no specialised version for an A* parameter.
How to implement it ?
For the double dispatch to work, you need to have type specific implementations of the double dispatched equalityCheck() in your base class.
For this to work, the Base needs to be aware of its descendents:
struct A;
struct Base {
virtual bool operator==(const Base& rhs) const
{
return rhs.equalityBounce(this);
}
virtual bool equalityBounce(const Base* lhs) const = 0;
virtual bool equalityCheck(const Base* lhs) const = 0;
virtual bool equalityCheck(const A* lhs) const = 0;
};
struct A : public Base {
...
bool equalityBounce(const Base* lhs) const override{
return lhs->equalityCheck(this);
}
bool equalityCheck(const Base* rhs) const override {
return false;
}
bool equalityCheck(const A* rhs) const override{
return a == rhs->a;
}
};
Note the use of override to make sure that the function really overrides a virtual function of the base.
With this implementation it will work, because:
A::equalityBounce()will callBase::equalityCheck()- among all the overloaded versions of this function, it will choose the
Base::equalityCheck(A*)becausethisis anA* - the invoked
Base *lhsobject will call itsequalityCheck(A*). Iflhsis anA*it will hence go forA::equalityCheck(A*)which will produce the expected (correct) result. Congratulations ! - suppose
lhswould be a pointer to another classXalso derived fromBase. In this case,lhs->equalityCheck(A*)would callX::equalityCheck(A*)and could also return the correct response, taking into consideration that you'd compare anXwith anA.
How to make it extensible ? The double-dispatch map !
The problem with the double dispatch using a strongly typed language, is that the "bounced" object needs to know about how to compare to specific (known in advance) classes. As your source object and your bounced object are of the same polymorphic base type, the base needs hence to know all involved types. This design limits seriously the extensivbility.
If you want to be able to add any derived type without knowing it in advance in the base class, then you have to go through dynamic types (be it dynamic_cast or typeid):
I propose you here a proposal for dynamic EXTENSIBILITY. It uses single dispatch for comparing two objects of the same type, and a double-dispatch map to compare different types between them (returning by default false if nothing was declared):
struct Base {
typedef bool(*fcmp)(const Base*, const Base*); // comparison function
static unordered_map < type_index, unordered_map < type_index, fcmp>> tcmp; // double dispatch map
virtual bool operator==(const Base& rhs) const
{
if (typeid(*this) == typeid(rhs)) { // if same type,
return equalityStrict(&rhs); // use a signle dispatch
}
else { // else use dispatch map.
auto i = tcmp.find(typeid(*this));
if (i == tcmp.end() )
return false; // if nothing specific was foreseen...
else {
auto j = i->second.find(typeid(rhs));
return j == i->second.end() ? false : (j->second)(this, &rhs);
}
}
}
virtual bool equalityStrict(const Base* rhs) const = 0; // for comparing two objects of the same type
};
The A class would then be rewrtitten as:
struct A : public Base {
A(int eh) : a(eh) {}
int a;
bool equalityStrict(const Base* rhs) const override { // how to compare for the same type
return (a == dynamic_cast<const A*>(rhs)->a);
}
};
With this code, you can compare any objects with an object of the same type. Now to show extensibility, I've created a struct X, with the same members than A. If I want to allow to copare A with X, I just have to define a comparison function:
bool iseq_X_A(const Base*x, const Base*a) {
return (dynamic_cast<const X*>(x)->a == dynamic_cast<const A*>(a)->a);
} // not a member function, but a friend.
Then to make dynamic double dipatch work, I have to add this function to the double-dispatch map:
Base::tcmp[typeid(X)][typeid(A)] = iseq_X_A;
Then the resutls are easy to verify:
Base *w = new A(1), *x = new A(2), *y = new X(2);
std::cout << (*w == *w) << "\n"; // true returned by A::equalityStrict
std::cout << (*w == *x) << "\n"; // false returned by A::equalityStrict
std::cout << (*y == *x) << "\n"; // true returned by isseq_X_A
Double Dispatch in C++
One way (certainly not the only way) is to call a virtual function on foo, passing it bar. Each derived type of foo implements this dispatch function the same way, which will pass itself to a virtual handler function in bar.
When you need to add more, you extend the interfaces to accept the new type(s). All the foo functions have the same implementation but they differ such that "this" is correctly the dynamic type of the object.
Also, Andrei Alexandrescu had a nice investigation into this with design alternatives in his (now not-so-modern) book Modern C++ Design, which still covers the idea but is written for c++98, but definitely still worth reading (though many things it says can't be done are now part of C++, partly due to that book.)
See it live: https://godbolt.org/z/oRyVJx
This example has 3 Foo classes, and 2 Bar classes.
#include <iostream>
class BarBase;
class FooBase {
public:
virtual ~FooBase() = default;
virtual void dispatch(BarBase*) = 0;
};
class Foo1;
class Foo2;
class Foo3;
class BarBase {
public:
virtual ~BarBase() = default;
virtual void accept(Foo1*) = 0;
virtual void accept(Foo2*) = 0;
virtual void accept(Foo3*) = 0;
};
class Bar1 : public BarBase {
public:
void accept(Foo1*) override;
void accept(Foo2*) override;
void accept(Foo3*) override;
};
class Bar2 : public BarBase {
public:
void accept(Foo1*) override;
void accept(Foo2*) override;
void accept(Foo3*) override;
};
class Foo1 : public FooBase {
public:
void dispatch(BarBase* bar) override { bar->accept(this); }
};
class Foo2 : public FooBase {
public:
void dispatch(BarBase* bar) override { bar->accept(this); }
};
class Foo3 : public FooBase {
public:
void dispatch(BarBase* bar) override { bar->accept(this); }
};
void Bar1::accept(Foo1 * f) { std::cout << "Bar1 accepting Foo1\n"; }
void Bar1::accept(Foo2 * f) { std::cout << "Bar1 accepting Foo2\n"; }
void Bar1::accept(Foo3 * f) { std::cout << "Bar1 accepting Foo3\n"; }
void Bar2::accept(Foo1 * f) { std::cout << "Bar2 accepting Foo1\n"; }
void Bar2::accept(Foo2 * f) { std::cout << "Bar2 accepting Foo2\n"; }
void Bar2::accept(Foo3 * f) { std::cout << "Bar2 accepting Foo3\n"; }
//
// Doesn't know which types of foo and bar it has, but it doesn't matter...
//
void call(FooBase& foo, BarBase& bar) {
foo.dispatch(&bar);
}
int main() {
Foo1 f1;
Foo2 f2;
Foo3 f3;
Bar1 b1;
Bar2 b2;
call(f1, b1);
call(f2, b1);
call(f3, b1);
call(f1, b2);
call(f2, b2);
call(f3, b2);
}
output:
Bar1 accepting Foo1
Bar1 accepting Foo2
Bar1 accepting Foo3
Bar2 accepting Foo1
Bar2 accepting Foo2
Bar2 accepting Foo3
C++ double dispatch extensible without RTTI
The first thing to realize is that double (or higher order) dispatch doesn't scale. With single
dispatch, and n types, you need n functions; for double dispatch n^2, and so on. How you
handle this problem partially determines how you handle double dispatch. One obvious solution is to
limit the number of derived types, by creating a closed hierarchy; in that case, double dispatch can
be implemented easily using a variant of the visitor pattern. If you don't close the hierarchy,
then you have several possible approaches.
If you insist that every pair corresponds to a function, then you basically need a:
std::map<std::pair<std::type_index, std::type_index>, void (*)(Base const& lhs, Base const& rhs)>
dispatchMap;
(Adjust the function signature as necessary.) You also have to implement the n^2 functions, and
insert them into the dispatchMap. (I'm assuming here that you use free functions; there's no
logical reason to put them in one of the classes rather than the other.) After that, you call:
(*dispatchMap[std::make_pair( std::type_index( typeid( obj1 ) ), std::type_index( typeid( obj2 ) )])( obj1, obj2 );
(You'll obviously want to wrap that into a function; it's not the sort of thing you want scattered
all over the code.)
A minor variant would be to say that only certain combinations are legal. In this case, you can usefind on the dispatchMap, and generate an error if you don't find what you're looking for.
(Expect a lot of errors.) The same solution could e used if you can define some sort of default
behavior.
If you want to do it 100% correctly, with some of the functions able to handle an intermediate class
and all of its derivatives, you then need some sort of more dynamic searching, and ordering to
control overload resolution. Consider for example:
Base
/ \
/ \
I1 I2
/ \ / \
/ \ / \
D1a D1b D2a D2b
If you have an f(I1, D2a) and an f(D1a, I2), which one should be chosen. The simplest solution
is just a linear search, selecting the first which can be called (as determined by dynamic_cast on
pointers to the objects), and manually managing the order of insertion to define the overload
resolution you wish. With n^2 functions, this could become slow fairly quickly, however. Since
there is an ordering, it should be possible to use std::map, but the ordering function is going to
be decidedly non-trivial to implement (and will still have to use dynamic_cast all over the
place).
All things considered, my suggestion would be to limit double dispatch to small, closed hierarchies,
and stick to some variant of the visitor pattern.
Multiple dispatch in C++
Multi-dispatch is the ability to choose which version of a function to call based on the runtime type of the arguments passed to the function call.
Here's an example that won't work right in C++ (untested):
class A { };
class B : public A { };
class C : public A { }
class Foo
{
virtual void MyFn(A* arg1, A* arg2) { printf("A,A\n"); }
virtual void MyFn(B* arg1, B* arg2) { printf("B,B\n"); }
virtual void MyFn(C* arg1, B* arg2) { printf("C,B\n"); }
virtual void MyFn(B* arg1, C* arg2) { printf("B,C\n"); }
virtual void MyFn(C* arg1, C* arg2) { printf("C,C\n"); }
};
void CallMyFn(A* arg1, A* arg2)
{
// ideally, with multi-dispatch, at this point the correct MyFn()
// would be called, based on the RUNTIME type of arg1 and arg2
pFoo->MyFn(arg1, arg2);
}
...
A* arg1 = new B();
A* arg2 = new C();
// Using multi-dispatch this would print "B,C"... but because C++ only
// uses single-dispatch it will print out "A,A"
CallMyFn(arg1, arg2);
Double dispatch and factory pattern
Maybe something like this could do it using member variables
#include <iostream>
#include <vector>
enum
{
CIRCLE,
RECTANGLE
};
class Circle;
class Rectangle;
class Shape {
private:
Shape() {};
public:
unsigned shapeType;
virtual ~Shape() {};
friend class Circle;
friend class Rectangle;
};
class Creator {
public:
unsigned shapeType;
virtual ~Creator() {};
virtual Shape* create() = 0;
bool equals(Shape& s) { return (this->shapeType == s.shapeType); };
};
class Circle : public Shape {
private:
Circle() : Shape() {shapeType=CIRCLE;};
public:
class CircleCreator : public Creator {
public:
CircleCreator() {shapeType=CIRCLE;};
virtual Shape* create() { return new Circle(); };
};
};
class Rectangle : public Shape {
private:
Rectangle() : Shape() {shapeType=RECTANGLE;};
public:
class RectangleCreator : public Creator {
public:
RectangleCreator() {shapeType=RECTANGLE;};
virtual Shape* create() { return new Rectangle(); };
};
};
int main() {
/* First step, build the list */
std::vector<Shape*> shapeList;
std::vector<Shape*>::iterator it;
Rectangle::RectangleCreator rc;
Circle::CircleCreator cc;
Shape* s = cc.create();
Shape* s1 = rc.create();
shapeList.push_back(s);
shapeList.push_back(s1);
/* Second step: check if we've got a shape starting from a creator */
for (it = shapeList.begin(); it != shapeList.end(); ++it) {
if (rc.equals(**it)) {
std::cout << "same shape" << std::endl;
}
}
return 0;
}
or this - using virtual function to return type
#include <iostream>
#include <vector>
enum
{
CIRCLE,
RECTANGLE,
UNKNOWN
};
class Circle;
class Rectangle;
class Shape {
private:
Shape() {};
public:
virtual ~Shape() {};
friend class Circle;
friend class Rectangle;
virtual unsigned iAmA(){return UNKNOWN;};
};
class Creator {
public:
virtual ~Creator() {};
virtual Shape* create() = 0;
virtual bool equals(Shape& s) { return false; };
};
class Circle : public Shape {
private:
Circle() : Shape() {};
virtual unsigned iAmA(){return CIRCLE;};
public:
class CircleCreator : public Creator {
public:
CircleCreator() {};
virtual Shape* create() { return new Circle(); };
virtual bool equals(Shape& other_shape) { return (CIRCLE == other_shape.iAmA()); };
};
};
class Rectangle : public Shape {
private:
Rectangle() : Shape() {};
virtual unsigned iAmA(){return RECTANGLE;};
public:
class RectangleCreator : public Creator {
public:
RectangleCreator() {};
virtual Shape* create() { return new Rectangle(); };
virtual bool equals(Shape& other_shape) { return (RECTANGLE == other_shape.iAmA()); };
};
};
int main() {
/* First step, build the list */
std::vector<Shape*> shapeList;
std::vector<Shape*>::iterator it;
Rectangle::RectangleCreator rc;
Circle::CircleCreator cc;
Shape* s = cc.create();
Shape* s1 = rc.create();
shapeList.push_back(s);
shapeList.push_back(s1);
/* Second step: check if we've got a shape starting from a creator */
for (it = shapeList.begin(); it != shapeList.end(); ++it) {
if (rc.equals(**it)) {
std::cout << "same shape" << std::endl;
}
}
return 0;
}
Related Topics
How to Load a Bmp on Glut to Use It as a Texture
Is Casting Std::Pair<T1, T2> Const& to Std::Pair<T1 Const, T2> Const& Safe
Why Can't We Declare Object of a Class Inside the Same Class
How to Avoid Errors While Using Crtp
Getting the Size of a C++ Function
How to Link Google Protobuf Libraries via Cmake on Linux
Get Signatures of Exported Functions in a Dll
Is Using Unsigned Integer Overflow Good Practice
Piping (Or Command Chaining) with Qprocess
How to Program for Windows Phone 7 in Standard C++ Only
Conversion from Void* to the Pointer of the Base Class
How to Call a Pointer-To-Member-Function
How to Implement a Map with Different Data Types as Values
Borderless Window with Drop Shadow