C++ overwritten member function of derived class returns array of derived class

Question

I am trying to write a program that searches for a node in a tree, starting from a root-node. As I want the search-algorithm to be as generic as possible, I want to use templates, and I want to use SFINAE to check if a given type implements all the functions I need.

To calculate the successors of a node, the type of the node has to have the function successors(), which returns a vector of nodes:

#include <vector>

class has_successors_t {
public:
  virtual std::vector<has_successors_t> successors() = 0;
};

the class to do the search looks like this:

#include <type_traits>

template <class node_t,
          class = std::enable_if_t<std::is_base_of<has_successors_t, node_t>::value>>
class breadthFirstSearch {
public:
    static node_t search(node_t root_node) {
        // search for the target node
    }
};

That way I tried to make the program compile only if a given type has a function to calculate its successors. But when I try to do the following:

#include <vector>

class some_node_t : public has_successors_t {
public:
  std::vector<some_node_t> successors() {
    // return the successors
  }
};

I get an error: error: invalid covariant return type for 'virtual std::vector<some_node_t> some_node_t::successors()'.

So, I know what the error means, but how can I solve problems like this? I could imagine that I am not the first one to encounter problems where I have a base class and a derived class, and I want an overwritten function in the derived class that returns a vector (or array, or queue, or anything like that) which contains elements of the derived class. But I just can't find a solution for that.

Thanks in advance for any help!

Greetings, Sebastian

Answer 1

You are breaking the basic rule of thumb. Run time olymorhism aka OOP in C++ only works with pointers or references. If you don't have pointers or references, there is no polymorphism and you don't need virtual functions or even base classes at all. You can SFINAE out on successor method directly rather than on a base class.

Something like this should fit the bill.

template <class N, 
     class = enable_if_t<is_same_v<vector<N*>,
        decltype(declval<N>().successors())>>> ...

The following assumes you will have pointers (smart or otherwise) because juggling nodes by value might not be an attractive proposition. I will use regular pointers for brevity

You might be able to achieve something like that with CRTP.

template <typename S>
class has_successors_t {
public:
  virtual 
std::vector<S *> successors() = 0;
};

class some_node_t : public has_successors_t<some_node_t> {
public:
  std::vector<some_node_t *> 
successors() {
    // return the successors
  }
};

Then the search function becomes just

template <class node_t>
class breadthFirstSearch {
public:
    static node_t 
search(has_successors_t<tnode_t> * root_node) {
    // search for the target node
    }
};

This however means that you will need to deal with has_successors_t<some_node_t> * rather than just has_successors_t *. Which leads to the next question. If you already have has_successors_t<some_node_t> *, why not just go one step further and have just some_node_t * and ditch has_successors_t altogether. Oops! We're back to SFINAEing out on having successors, only with pointers this time.

There are some uses for CRTP but you need to see for yourself whether it fits your design.