Fast RTTI in C++ for a class hierarchy

28 April 2022

programming

The Problem

Let's write a polymorphic operator base class, with which we plan to generalize the arithmetic operators in a very basic calculator.

                Code language
                cpp
              

                // polymorphic operator base class
class Operator {
 protected:
  Operator() = default;

 public:
  virtual ~Operator() = default;
};
              

In our calculator we intend to support the four basic arithmetic operations: addition, subtraction, multiplication, and division. Let's derive those operator types from the base.

                Code language
                cpp
              
                class Plus final : public Operator {};

class Minus final : public Operator {};

class Times final : public Operator {};

class Divide final : public Operator {};

Here is an incomplete function that shows how we intend to do evaluation.

                Code language
                cpp
              

                //
// requires C++20
// required headers
//   <stdexcept>
//   <type_traits>
//   <vector>
//
template <typename Elem>
requires std::is_arithmetic_v<Elem> Elem
evaluate(std::vector<Elem> const& elems,
         std::vector<Operator const*> const& ops) {
  auto e = elems.empty() ? Elem{} : elems[0];
  for (auto i = 1,                          // iter elems
       j = 0;                               // iter ops
       i < elems.size() && j < ops.size();  //
       ++i, ++j) {
    auto op = ops[j];                             // [0]
    if (/* op points to Plus type */) {           // [1]
      e += elems[i];
    } else if (/* op points to Minus type */) {   // [2]
      e -= elems[i];
    } else if (/* op points to Times type */) {   // [3]
      e *= elems[i];
    } else if (/* op points to Divide type */) {  // [4]
      e /= elems[i];
    } else {
      throw std::runtime_error("Invalid operator encountered!");
    }
  }
  return e;
}
              

Next we need to decide on how to determine the derived type of an Operator object at lines labelled 1 through 4.

C++ provides two RTTI features. We can either use dynamic_cast, possible since we are working with a polymorphic base class, or, we can use the typeid operator.

Using `dynamic_cast`

                Code language
                cpp
              

                // ...
// for ( ... ) {
// ...
    auto op = ops[j];                              // [0]
    if (dynamic_cast<Plus const*>(op)) {           // [1]
      e += elems[i];
    } else if (dynamic_cast<Minus const*>(op)) {   // [2]
      e -= elems[i];
    } else if (dynamic_cast<Times const*>(op)) {   // [3]
      e *= elems[i];
    } else if (dynamic_cast<Divide const*>(op)) {  // [4]
      e /= elems[i];
    } else {
      throw std::runtime_error("Invalid operator encountered!");
    }
// ...
// }
// ...
              

Using `typeinfo`

                Code language
                cpp
              

                // required header: <typeinfo>

// ...
// for ( ... ) {
// ...
     auto const& ti = typeid(*ops[j]);  // [0]
    if (typeid(Plus) == ti) {           // [1]
      e += elems[i];
    } else if (typeid(Minus) == ti) {   // [2]
      e -= elems[i];
    } else if (typeid(Times) == ti) {   // [3]
      e *= elems[i];
    } else if (typeid(Divide) == ti) {  // [4]
      e /= elems[i];
    } else {
      throw std::runtime_error("Invalid operator encountered!");
    }
  }
// ...
// }
// ...
              

An example evaluation

                Code language
                cpp
              

                // C++20

#include <iostream>
#include <vector>
#include <stdexcept>
#include <type_traits>
#include <vector>
#include <typeinfo> // if using typeid

// <<Operator base class definition from above>>
// <<Operator derived class definitions from above>>
// <<evaluate function definition from above>>

int main(int argc, char* argv[]) {
  auto const Op = OperatorPlus{};
  auto const Om = OperatorMinus{};
  auto const Ot = OperatorTimes{};
  auto const Od = OperatorDivide{};

  // evaluating ((2. * 3.) + 6.) - 2.) / 2.
  auto const nums = std::vector<double> {2,3,6,2,2};
  auto const ops  = std::vector<Operator*> {&Ot,&Op,&Om,&Od};


  std::cout << "result: " << evaluate(nums, ops) << std::endl; // result: 5
  return 0;
}
              

Why not use an overloaded evaluation function?

                Code language
                cpp
              

                template <typename E>
class Operator {
  //...
  public:
  virtual E evaluate(E lhs, E rhs) const = 0;
  //...
};

template <typename E>
class Plus final : public Operator<E> {
  private:
  E evaluate(E lhs, E rhs) const override {
    return lhs + rhs;
  }
}

// ...
// ...
              

Yes that is perfectly fine for simple cases. However, if want to add more functionalities to the operator base class, we must modify the base class as well as all the derived classes.

Or, one could write another base class with a virtual function for the new functionality, then write new concrete operator classes that derive from both the new base class and the corresponding Plus, Minus, Times, or Divide class (Or something along the lines, untested idea, but possible). This is cumbersome evidently.

Problems with `dynamic_cast`

It can be expensive. I will just leave some references here. In short, there are cases when dynamic_cast is necessary but should be avoided when possible.
typeid is cheaper than dynamic_cast: see this comment and this comment.

Problems with `typeid`

typeid comparison can still be slow as the operator==() of the std::type_info object, which results from calling typeid, is implementation defined and might use string comparison. We could do better than that. Also, the idiom presented here is possible when RTTI is disabled during compilation and typeid is only available when RTTI is enabled.

Fast RTTI

Here is the full implementation with an example:

                Code language
                cpp
              

                // C++20
#include <iostream>
#include <type_traits>
#include <vector>

// abstract Operator class
struct Operator {
 public:
  using type_id_t = int;

  ~Operator() = default;

  template <typename T>
  bool is() const {
    return this->type_id() == id_for_type<std::decay_t<T>>();
  }

 protected:
  Operator() = default;

  // each derived class implements this method
  virtual type_id_t type_id() const = 0;

  // type id is computed once for a type T
  // and returned the same id whenever called with the T
  template <typename T>
  static type_id_t id_for_type() {
    static auto id = next_id();
    return id;
  }

 private:
  static type_id_t next_id() {
    static std::atomic<type_id_t> grand_type_id = 0;
    return ++grand_type_id;
  }
};

struct Plus final : Operator {
  type_id_t type_id() const { return id_for_type<Plus>(); }
};

struct Minus final : Operator {
  type_id_t type_id() const { return id_for_type<Minus>(); }
};

struct Times final : Operator {
  type_id_t type_id() const { return id_for_type<Times>(); }
};

struct Divide final : Operator {
  type_id_t type_id() const { return id_for_type<Divide>(); }
};

template <typename Elem>
requires std::is_arithmetic_v<Elem> Elem
evaluate(std::vector<Elem> const& elems,
         std::vector<Operator const*> const& ops) {
  auto e = elems.empty() ? Elem{} : elems[0];
  for (auto i = 1,                          // iter elems
       j = 0;                               // iter ops
       i < elems.size() && j < ops.size();  //
       ++i, ++j) {
    auto o = ops[j];               // [0]
    if (o->is<Plus>()) {           // [1]
      e += elems[i];
    } else if (o->is<Minus>()) {   // [2]
      e -= elems[i];
    } else if (o->is<Times>()) {   // [3]
      e *= elems[i];
    } else if (o->is<Divide>()) {  // [4]
      e /= elems[i];
    } else {
      throw std::runtime_error("Invalid operator encountered!");
    }
  }
  return e;
}

int main(int argc, char* argv[]) {
  auto const Op = Plus{};
  auto const Om = Minus{};
  auto const Ot = Times{};
  auto const Od = Divide{};

  // evaluating ((2. * 3.) + 6.) - 2.) / 2.
  auto const nums = std::vector<double>{2, 3, 6, 2, 2};
  auto const ops = std::vector<Operator const*>{&Ot, &Op, &Om, &Od};

  std::cout << "result: " << evaluate(nums, ops) << std::endl;  // result: 5

  return 0;
}
              

Tagged with

Cpp
Design