Как обрабатывать «неверные ковариантные типы возвращаемых данных» для итераторов и аналогичных ситуаций - PullRequest
Новая
       35

Как обрабатывать «неверные ковариантные типы возвращаемых данных» для итераторов и аналогичных ситуаций

2 голосов
/ 28 июня 2019

Я пытаюсь создать класс двоичного дерева Tree и класс двоичного дерева поиска BST, который наследуется от Tree, а также iterator вложенных классов для каждого, где BST::iterator наследуется от Tree::iterator.

Теперь проблема в том, что некоторые функции деревьев должны возвращать iterator своего собственного класса, например begin(), end(), search(T) и т. Д. Это, похоже, не компилируется, потому что Tree::begin() и BST::begin() имеют "недопустимые ковариантные типы возврата".

После изучения указанной темы я понимаю , что заставляет компилятор жаловаться, но я не понимаю , почему это не разрешено. Кажется логичным, что в этом случае, например, Tree должен возвращать объект типа Tree::iterator, а BST должен возвращать объект типа BST::iterator.

Ниже приведен код, который должен проиллюстрировать, с чем я имею дело.

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;

};

Мне ясно, что в этом случае поиск пытается вернуть BST<T>::iterator, и это недопустимо, потому что он переопределяет функцию, которая возвращает Tree<T>::iterator, однако мне кажется логичным, что это должно быть разрешено, и я не уверен, как это должно быть сделано.

Кроме того, когда BST<T> наследует begin() и end(), я предполагаю, что он наследует их так, что они возвращают Tree<T>::iterators, хотя они действительно должны возвращать BST<T>::iterators.

Что именно мне не хватает, и как этого добиться?

1 Ответ

1 голос
/ 28 июня 2019

Полиморфизм может быть осуществлен только через указатель / ссылку, что допускает ковариацию для возвращаемого объекта, что приводит к нарезке.

Мы не можем также добавить ковариационное отношение к «несвязанному» типу как умные указатели. (тогда как 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
};
...