Comparing derived classes in C++ without dynamic casting or static downcasting

Question

I'm trying to compare objects of a common base class together. The comparison should fail (output a failure string, for instance) in any case when the two objects differ in class, or differ in values specific to the object. Ideally the comparison is somehow enforced, such that a new derived class would also have to write a comparison function to members of its class. Here's a code example:

#include <iostream>
#include <string>
#include <vector>

class Vehicle 
{ 
public:
  virtual std::string compareTo(Vehicle* v) = 0;
};

class Bicycle : public Vehicle
{
public:
  Bicycle() { color_ = "red"; }
  std::string compareTo(Vehicle* v) { return "We're different vehicles."; }
  std::string compareTo(Bicycle* b) { return color_.compare(b->color_) ? "We're different bicycles." : "We're the same bicycle."; }

private:
  std::string color_;
};

class Car : public Vehicle
{
public:
  Car() { style_ = "sedan"; }
  std::string compareTo(Vehicle* v) { return "We're different vehicles."; }
  std::string compareTo(Car* c) { return style_.compare(c->style_) ? "We're different cars." : "We're the same car."; }

private:
  std::string style_;
};

int main()
{
  Vehicle* compareFrom = new Bicycle();

  std::vector<Vehicle*> compareTos;
  compareTos.push_back(new Bicycle());
  compareTos.push_back(new Car());

  std::vector<Vehicle*>::iterator it;
  for (it = compareTos.begin(); it != compareTos.end(); ++it)
    std::cout << compareFrom->compareTo(*it) << std::endl;

  return 0;
}

Currently, the output (which you can see here) says "We're different vehicles". I know this is happening because I'm using the abstract base pointer. The problem is how to fix it!

The output I'd like to have is that the bicycles output that they're the same, because they do have the same color. Bicycles and cars should output that they're different vehicles. Bicycles of different colors and cars of different styles should also output that they're different. I feel like there must be a great pattern to use to solve this problem, but I'm getting mired in dynamic casting or unsafe downcast issues. Also, I would like for the comparison function to be enforced among members of the same class (so Bicycles must be able to compare to other Bicycles).

Answer 1

You want Multiple Dispatch (i.e. select which function to call dynamically based on more than one variable, not just 'this'). This is because you need to inspect the type somehow, otherwise the compiler will do a static analysis on the types and select what function to call (The virtual one in Vehicle).

No way around that. dynamic_cast is your friend here, but you may want to roll your own RTTI system for performance (or other) reasons. (The wikipedia article shows one way..)

 std::string Bicycle::compareTo(Vehicle* v) { 
    if (Bicycle* b = dynamic_cast<Bicycle*>(v)) {
       return compareTo(b);
    } else {
       return "We're different vehicles."; 
    }
 }

There is an implementation of this pattern in the Loki C++ library which might help if you have many types that need comparing.

Multiple dispatch is not supported by the language in C++, nor in most mainstream languages. There was a proposal to add it to C++11 though, see this question and Bjarne's paper. I think it was rejected because (known and unknown) issues with dynamic linking, which the C++ standard sadly knows nothing about.

Answer 2

Your code has the big problem that it’s not easily extensible (violates the open/closed principle). You can however delegate the comparison to a base class method.

Also, if you want to enforce the semantic (a good thing) then you will not be able to circumvent downcasting, sorry.

To make it robust and extensible,

1. Make the base method pure virtual
2. Provide an implementation for the base method (yes, this works! Even if it’s pure virtual) that compares the objects’ types
3. In the derived classes, use the base class’ implementation to test for type equality, then do the actual logic check.

#include <iostream>
#include <iomanip>
#include <string>
#include <typeinfo>

struct vehicle {
    virtual bool compare_to(vehicle const& other) const = 0;
};

bool vehicle::compare_to(vehicle const& other) const {
    return typeid(*this) == typeid(other);
}

struct car : vehicle {
    std::string color;

    car(std::string const& color) : color(color) { }

    bool compare_to(vehicle const& other) const {
        bool result = vehicle::compare_to(other);
        return result and (color == static_cast<car const&>(other).color);
    }
};

struct bike : vehicle {
    int spokes;

    bike(int spokes) : spokes(spokes) { }

    bool compare_to(vehicle const& other) const {
        bool result = vehicle::compare_to(other);
        return result and (spokes == static_cast<bike const&>(other).spokes);
    }
};

int main() {
    car c1("blue");
    car c2("red");
    bike b1(42);

    std::cout << std::boolalpha;
    std::cout << c1.compare_to(c2) << "\n"
              << c1.compare_to(b1) << "\n"
              << c1.compare_to(c1) << "\n";
}

The above code, the static_cast is safe since we have ensured beforehand that the type is the same, thus the cast will never fail.

Note that the use of typeid here is entirely legitimate. It shouldn’t even be very inefficient since there is no deep type hierarchy to walk. But if you want to make this more efficient you can implement a simple own mechanism which uses a static table in the base class to map each created instance to type-unique number identifier (e.g. std::map<vehicle*, type_id>, where type_id is a plain old enum) and perform a simple lookup.

… Or use dynamic_cast, actually.

Answer 3

I normally implement this using a 'kind' member in the base class. I find this has a few advantages:

• Performance - no need for virtual function call and dynamic cast
• By using a different 'bit' for each class type, then higher level comparisons can be made. For example 'unicycle' and 'bicycle' might both be human powered, so you could easily check for that separately from their main kind.

The kind type would look like the following:

    enum Kind {
      HUMAN_POWERED  = (0x1 << 0),
      MOTOR_POWERED  = (0x1 << 1),
      BICYCLE        = (0x1 << 2) | HUMAN_POWERED,
      UNICYCLE       = (0x1 << 3) | HUMAN_POWERED,
      CAR            = (0x1 << 4) | MOTOR_POWERED
    };

Now it's possible to check that the CAR is not a BICYCLE, but also if two types are MOTOR_POWERED or not!

bool areSameClass (Vehicle const & lhs, Vehicle const & rhs)
{
  return (lhs->getKind () & rhs->getKind ()) & (HUMAN_POWERED | MOTOR_POWERED);
}

Answer 4

If you have RTTI enabled in your compiler, you might be able to use the typeid() operator, but this will require your classes to be polymorphic.