I've got a base class with (potentially) a lot of subclasses, and I would like to be able to compare any two objects of the base class for equality. I am trying to do this without invoking the blasphemous typeid keyword.
#include <iostream>
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;
};
struct A : public Base {
A(int eh) : a(eh) {}
int a;
virtual bool equalityBounce(const Base* lhs) const{
return lhs->equalityCheck(this);
}
virtual bool equalityCheck(const Base* rhs) const {return false;}
virtual bool equalityCheck(const A* rhs) const {return a == rhs->a;}
};
int main() {
Base *w = new A(1), *x = new A(2);
std::cout << (*w == *w) << "\n";
std::cout << (*w == *x) << "\n";
}
I understand that the code as written is failing because lhs in equalityBounce() is a Base*, so it doesn't even know about the version of equalityCheck() that takes an A*. But I don't know what to do about it.
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 call Base::equalityCheck() Base::equalityCheck(A*) because this is an A*Base *lhs object will call its equalityCheck(A*). If lhs is an A* it will hence go for A::equalityCheck(A*) which will produce the expected (correct) result. Congratulations !lhs would be a pointer to another class X also derived from Base. In this case, lhs->equalityCheck(A*) would call X::equalityCheck(A*) and could also return the correct response, taking into consideration that you'd compare an X with an A. 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