Avoiding dynamic_cast in implementation of virtual functions in derived class

Question

Here is some sample code explaining what I am trying to achieve.

Basically, I have an algorithm that depends on some basic operations available in a class. I have defined those operations in a pure abstract base class. I want to apply that algorithm to a variety of objects that provide those operations by deriving classes for the specific objects.

However, the different derived objects are incompatible with one another as far those operations are concerned. My question is whether I can avoid using RTTI to ensure that for example, bool derived2::identical(const base* other2), asserts(or other exit mechanism) where other2 is not of type derived2.

One alternative would be to template the function algorithm on the specific derived object, but that would mean that it's implementation would have to live in a header file which I don't want to do since 1) Changing the algorithm code for test purposes can cause recompilation of large portions of the code 2) The algorithm's implementation would be exposed in the header instead of living nicely in a source file hidden from the end-user.

Header file

#include <list>

class base
{
public:
 virtual float difference(const base*) const = 0;
 virtual bool identical(const base*) const = 0; 
};


class derived1 : public base
{
 public:
 float difference(const base* other1) const
 {
  // other1 has to be of type derived1
            if(typeid(other1) == typeid(this))
            {
                    // process ...
            }
            else
            {
                    assert(0);
            }
  return 1;
 }

 bool identical(const base* other1) const
 {
  // other1 has to be of type derived1
            if(typeid(other1) == typeid(this))
            {
                    // compare...
            }
            else
            {
                    assert(0);
            }
  return true;
 }
};


class derived2 : public base
{
 public:
        float difference(const base* other2) const
        { 
             // process ...
  // other2 has to be of type derived2
            return 2;
        }

 bool identical(const base* other2) const
        {
                // do comparison
  // derived1 and derived2 cannot be compared
                return true;
        }
};

// Declaration
int algorithm(std::list<base*>& members);

Implementation of algorithm Source file

#include "header_file_containing_base"
int algorithm(std::list<base*>& members)
{
 // This function only relies on the interface defined in base
 // process members;

 return 1;
}

Main program

int main()
{
  // Create lists of derived1 and derived2
  // Run algorithm on these lists
}

Answer 1

You could use double dispatch (http://en.wikipedia.org/wiki/Double_dispatch)

Answer 2

Well, there is one simple thing: store the real type as a member.

• An enum, grouping all the types. It'll become cumbersome if you have a lot of them.
• A Factory to generate ids (using templates to only generate one id per item)
• ...

I'll illustrate the factory id:

class IdFactory
{
public:
  template <class T>
  static size_t GetId(T const&) // argument deduction
  {
    static size_t const Id = GetIdImpl();
    return Id;
  }

private:
  static size_t GetIdImpl()
  {
    static size_t Id = 0;
    return ++Id;
  }
}; // class IdFactory

And you can use it like such:

class Base
{
public:
  explicit Base(size_t id): mId(id) {}
  size_t const mId; // meaningless to change it afterward...

private:
};

class Derived: public Base
{
public:
  explicit Derived(): Base(IdFactory::GetId(*this)) {}
};

Then you can use the mId member for testing. Note that since it's const it can be exposed... otherwise you can create an inline const getter...

float Derived::difference(const Base& rhs)
{
  assert( IdFactory::GetId(*this) == rhs.mId );

  // ...
}

The cost here is negligible:

• GetId is inlined, thus no function call
• GetId is lazily initialized, apart for the initialization it amounts to checking that the static member has been initialized: it's typically implemented as a if statement which condition always evaluate to true (apart from the first time).
• == is normally fast ;)

The only downside is that you actually need to make sure that you correctly initialize the ids.

There is also a no-storing solution, which involves a virtual function call:

class Other: public Base
{
public:
  virtual size_t id() const { return IdFactory::GetId(*this); }
};

It's easier to put in practice because not storing a const member means that you don't have to write the assignment yourself.

Answer 3

@David: The problem with double dispatch is that for the end-user who implements his own class derived from base will have no means to add calls for the other derived types which could be provided as a library. Does this make sense?

The goal here is to prevent the user from inadvertently mixing up derived types and sending them to the algorithm.

Answer 4

You could use a templated function. With templates it is possible to add more classes later without the need to change the original classes, by just adding another template function in another header file. If the only problem is the compile speed - you can implement the template function in a source file apart from the header and use explicit template instanciation.