Я пытаюсь создать класс бинарного дерева Tree
и класс бинарного дерева поиска BST
, который наследуется от Tree
, а также iterator
вложенных классов для каждого, где BST::iterator
наследуется от Tree::iterator
.
Теперь проблема в том, что некоторые из функций деревьев должны возвращать iterator
своего собственного класса, например begin()
, end()
, search(T)
и т. д. Кажется, что это не компилируется, потому что Tree::begin()
и BST::begin()
имеют «недопустимые ковариантные возвращаемые типы».
Изучив указанную тему, я понимаю, что что вызывает компилятор может пожаловаться, но я не понимаю, что Зачем это не разрешено. Кажется логичным, что в этом случае, например, Tree
должен возвращать объект типа Tree::iterator
, а BST
должен возвращать объект типа BST::iterator
.
Ниже приведен код, который должен иллюстрировать, с чем я имею дело.
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;
};
#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;
};
Мне ясно, что в этом случае поиск пытается вернуть BST<T>::iterator
, а это не разрешено, потому что он переопределяет функцию, которая возвращает Tree<T>::iterator
, однако мне кажется логичным, что это должно быть разрешено, и я не уверен, что как это должно быть сделано.
Кроме того, когда BST<T>
наследует begin()
и end()
, я предполагаю, что он наследует их таким образом, что они возвращают Tree<T>::iterators
, хотя на самом деле они должны возвращать BST<T>::iterators
.
Полиморфизм может быть реализован только через указатель/ссылку, что позволяет использовать ковариацию для возвращаемого объекта, что приведет к нарезке.
Мы не можем ни добавлять отношение ковариации к «несвязанному» типу, как смарт-указатели. (тогда как Base*
и Derived*
могут быть ковариантными, std::unique_ptr<Base>
и std::unique_ptr<Derived>
не могут :/)
Однако ковариация может быть выполнена с помощью указателя/ссылки.
Один из способов обойти эти ограничения — иметь 2 метода: один виртуальный с поддерживаемой ковариацией и один обычный метод, который использует виртуальный метод для имитации ковариации:
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
};