How should 'Invalid covariant return types' be handled for iterators and similar situations

Question

I'm trying to make a binary tree class Tree and a binary search tree class BST which inherits from the Tree, as well as iterator nested classes for each, where BST::iterator inherits from Tree::iterator.

Now, the problem is that some of the trees' functions must return an iterator of its own class, such as begin(), end(), search(T), etc. This seems to not compile because Tree::begin() and BST::begin() have "invalid covariant return types".

After researching said topic, I understand what is causing the compiler to complain, but I do not understand why it's not allowed. It seems logical that in this case for example, the Tree should return an object of type Tree::iterator and the BST should return an object of type BST::iterator.

Below is some code which should illustrate what it is I am dealing with.

Tree.h

template <class T>
class Tree {
  protected:
    class Node {
        friend Tree;
        T value;
        Node* left;
        Node* right;
    };

    Node* root;

  public:
    class iterator {
        friend Tree;
        Node* node;
      public:
        // operators and the like...
    };

    virtual iterator begin() const;
    virtual iterator end() const;
    virtual iterator search(const T& value) const;
};

BST.h

#include "Tree.h"

template <class T>
class BST : public Tree<T> {
  protected:
    class Node : public Tree<T>::Node {
        friend BST;
    };

    using Tree<T>::root;

  public:
    class iterator : public Tree<T>::iterator {
        friend BST;
    };

    using Tree<T>::begin;
    using Tree<T>::end;
    virtual iterator search(const T& value) const override;

};

It is clear to me that in this case, search is trying to return a BST<T>::iterator, and that's not allowed, because it's overriding a function which returns a Tree<T>::iterator, however it seems logical to me that this should be allowed, and I am unsure as to how this is supposed to be done.

Also, when BST<T> inherits begin() and end(), I assume it is inheriting them such that they return Tree<T>::iterators, although they should really be returning BST<T>::iterators.

What exactly is it that I'm missing, and how should something like this be achieved?

Answer 1

Polymorphism can only be done through pointer/reference, allowing covariance for return object would introduce slicing.

We cannot neither adding covariance relation to "unrelated" type as smart-pointers. (whereas Base* and Derived* can be covariant, std::unique_ptr<Base> and std::unique_ptr<Derived> cannot :/)

Covariance can be done through pointer/reference though.

One way to work around those restrictions is to have 2 methods, one virtual with supported covariance, and one regular method which uses the virtual one to mimic covariance:

template <typename T>
class Tree {
    // ...
    // Assuming iterator might be constructed with node.
    typename Tree<T>::iterator begin() const { return {node_begin()/*, ...*/}; }
    typename Tree<T>::iterator end() const   { return {node_begin()/*, ...*/}; }

protected:
    virtual typename Tree<T>::node* node_begin() const;
    virtual typename Tree<T>::node* node_end() const;
};

template <class T>
class BST : public Tree<T> {
    // ...

    typename BST<T>::iterator begin() const { return {node_begin()/*, ...*/}; }
    typename BST<T>::iterator end() const   { return {node_begin()/*, ...*/}; }

protected:
    typename BST<T>::node* node_begin() const override; // covariance on pointer
    typename BST<T>::node* node_end() const override;   // covariance on pointer
};