7
votes

I have some pointers to a base type of Shape. I want to compare these objects using the == operator. The == operator should obviously return false if the objects are of different derived type. If they are of the same derived type however the members of the derived type should then be compared.

I have read that using the C++ RTTI is bad practice and should only be used in rare and essential circumstances. As far as I can see this problem cannot be generally solved without using the RTTI. Each overloaded == operator would have to check the typeid, and if they are the same perform a dynamic_cast and compare the members. This seems like a common need. Is there some kind of idiom for this problem?

#include <iostream>
using namespace std;

class Shape {
  public:
    Shape() {}
    virtual ~Shape() {}
    virtual void draw() = 0;

    virtual bool operator == (const Shape &Other) const = 0;
};

class Circle : public Shape {
  public:
    Circle() {}
    virtual ~Circle() {}
    virtual void draw() { cout << "Circle"; }

    virtual bool operator == (const Shape &Other) const {
      // If Shape is a Circle then compare radii
    }

  private:
    int radius;
};

class Rectangle : public Shape {
  public:
    Rectangle() {}
    virtual ~Rectangle() {}
    virtual void draw() { cout << "Rectangle"; }

    virtual bool operator == (const Shape &Other) const {
      // If Shape is a Rectangle then compare width and height
    }

  private:
    int width;
    int height;
};

int main() {
  Circle circle;
  Rectangle rectangle;

  Shape *Shape1 = &circle;
  Shape *Shape2 = &rectangle;

  (*Shape1) == (*Shape2); // Calls Circle ==
  (*Shape2) == (*Shape1); // Calls Rectangle ==
}
4
I don't have the time to craft a complete answer, but I'll mention that you may be interested in researching about multi-methods, which is a solution to this problem. In C++, it's not for the faint of heart, mind you.R. Martinho Fernandes
What about just using an Enum as your types seems to be aware of other types?Viktor Sehr
@R.MartinhoFernandes - Thanks I will look into thatoggmonster
@oggmonster, i think you should look at link linkForEveR
@ViktorSehr which is probably what typeid does, so why reinvent the wheel? I can ask the same of the OP. Saying "I have read that using the C++ RTTI is bad practice and should only be used in rare and essential circumstances" - overlooks the fact their scenario is precisely where RTTI should be used. Note RTTI encompasses typeid + dynamic_cast, and as the former is very cheap, I assume the OP's aversion to RTTI overall was based only on things read about the latter. Course dynamic_cast should be avoided where possible (like here) if speed is a concern, but it's usually not that badunderscore_d

4 Answers

10
votes

Use the RTTI. Use typeid, but use static_cast rather than dynamic_cast.

From a design point of view, I'd say that this is exactly what RTTI is for, any alternative solutions will, by necessity, be uglier.

virtual bool operator == (const Shape &Other) const {
    if(typeid(Other) == typeid(*this))
    {
        const Circle& other = static_cast<const Circle&>(Other);
        // ...
    }
    else
        return false;
}

From a performance point of view: typeid tends to be cheap, a simple lookup of a pointer stored in the virtual table. You can cheaply compare dynamic types for equality.

Then, once you know you have the right type, you can safely use static_cast.

dynamic_cast has a reputation for being slow (that is, slow as in "compared to virtual function calls", not slow as in "compared to a cast in java"), because it will also analyze the class hierarchy to deal with inheritance (and multiple inheritance, too). You don't need to deal with that here.

4
votes

Of course it can be done without using typeid and casting. But it is a bit cumbersome so you must decide if it's worth doing.

Version one - double visitors

Use visitor pattern

class ShapeVisitor
{
public:
    virtual void visitCircle(Circle const &) = 0;
    virtual void visitRectangle(Rectangle const &) = 0;
    // other shapes
}

To class Shape add

virtual void acceptVisitor(ShapeVisitor &) = 0;

And visitors

class CircleComparingVisitor : public ShapeVisitor
{
    Circle const & lhs; // shorthand for left hand side
    bool equal; // result of comparison
public:
    CircleComparingVisitor(Circle const & circle):lhs(circle), equal(false){}
    virtual void visitCircle(Circle const & rhs) {equal = lhs.radius == rhs.radius;}
    virtual void visitRectangle(Rectangle const &) {}
    // other shapes
    bool isEqual() const {return equal;}
}
// other shapes analogically

class ShapeComparingVisitor
{
    Shape const & rhs; // right hand side
    bool equal;
public:
    ShapeComparingVisitor(Shape const & rhs):rhs(rhs), equal(false) {}

    bool isEqual() const {return equal;}

    virtual void visitCircle(Circle const & lhs)
    {
        CircleComparingVisitor visitor(lhs);
        rhs.accept(visitor);
        equal = visitor.isEqual();
    }
    virtual void visitRectangle(Rectangle const & lhs)
    {
        RectangleComparingVisitor visitor(lhs);
        rhs.accept(visitor);
        equal = visitor.isEqual();
    }
}

Finally operator== no need to be virtual

bool Shape::operator==(const Shape &rhs) const
{
    ShapeComparingVisitor visitor(rhs);
    this->accept(visitor);
    return visitor->isEqual();
}

Second thought - operator== may be virtual and use a proper comparing visitor - so you can get rid of ShapeComparingVisitor

Version two - double dispatching

You add to Shape

virtual bool compareToCircle(Circle const &) const == 0;
virtual bool compareToRectangle(Rectangle const &) const == 0;

And implement in specific shapes

Now for example

bool Circle::operator==(Shape const & rhs) const
{
    return rhs.compareToCircle(*this);
}
1
votes

This is exactly what RTTI is for. At compile time all you know is that it's a Shape&, so you simply have to do a runtime check to see what derived type it actually is before you can make a meaningful comparison. I'm not aware of any other way to do it without violating polymorphism.

You could define many free functions for operator == for different derived type combinations, but it then wouldn't have polymorphic behaviour as you're presumably handling these via Shape& pointers so even the calling code doesn't actually know what type the objects are.

Thus, RTTI is (almost) unavoidable here, and indeed this kind of scenario is exactly why RTTI exists. It's only considered bad practice in some cases because it adds a certain fragility (you have to make sure you handle when things aren't of a type you know how to deal with, because anybody could come along and make a new subclass of Shape), and it adds a runtime cost. But you're already paying a runtime cost by using virtual methods.

I say 'almost unavoidable' because you could probably concoct some system which made further virtual method calls on the object passed in to operator == to get the right kind of comparison behaviour, but in practical terms another virtual method lookup (remember, virtual methods also have a runtime performance penalty because the compiler has no idea which implementation will get called so can't put in a concrete function address) is probably no faster than the cost of the RTTI.

If anybody knows a way to do it without that cost at all, I'd love to see it.

1
votes

My feeling is that there is a fundamental violation of the Liskov substitution principle going on here, as you're digging into the internal representations of the objects. However if you're happy to expose the internal representation of your objects (or you have to do so for other reasons) then something like this will work.

class Shape
{
   virtual void std::string serialize() const =0;
   bool operator==( const Shape & s )
   {
      return this.serialize() == s.serialize();
   }
};