c++ - Polymorphism for a class with no virtual functions?

Question

I'm building a parsing tree which works quite simply: there's a base class for Node and the derived classes for different types of nodes. Children nodes are stored in a list<Node*>.

The problem arises when you want to traverse such a tree and do some stuff with it. As we know, in C++ you can't perform a downcast if the type is non-polymorphic. However, in my situation I obviously need to be able to downcast from Node to the real class of the child node. How should I solve this problem? Do I really need to add a useless virtual function just to be able to do that (I don't really need any in my code)? Or is my approach towards designing this structure completely wrong?

Answer 1

You can impement polymorphic value types if you want.

Unless you need insane extendibility, dynamic cast is going to be a poor performing option; it is a nuclear bomb to kill a termite.

An easy way is to make your node a std::variant of possible node types. You can add a "get base class" helper if you need it (and cache it for speed).

For moderate extendibility, a std any is a value type that lets you cast to exact type.

Or you can implement your own downcast table if you prefer, and keep storing pointers.

Myself, I'd use the variant approach. Nodes containing nodes takea a bit of finess (as variant needs the full class definition, and a node is a variant of each node type), bit there are a lot of solutions (node is actually a thin class that inherits from, or contains a variant, for example).

Using C++ dynamic cast requires a virtual method. But you can make the destructor virtual to satisfy that.

template<class Base, class...Ts> requires (std::is_base_of_v<Base, Ts>&&...)
struct poly_variant:std::variant<Ts...>{
  Base& base(){ return std::visit([](auto&&elem)->Base&{return elem;}, *this); }
  Base const& base()const{ return std::visit([](auto&&elem)->Base const&{return elem;}, *this); }
  using std::variant<Ts...>::variant;
};

struct node;

// define base_avian
// define duck, chicken, flock

struct node : poly_variant<base_avian, chicken, duck, flock> {
  using poly_variant<base_avian, chicken, duck, flock>::poly_variant;
};

there. Now you can

std::vector<node> children;
for(auto&child:children){
  child.base().SomeAvianMethod();
  flock* f=std::fet_if<flock>(&child);
}

no vtable in sight.

Of course if your base_avian type is empty you can ignore most of this.