Вызывайте функцию производного класса, не входящую в базовый класс, без приведения Dynami c для максимизации производительности. - PullRequest
Новая
       22

Вызывайте функцию производного класса, не входящую в базовый класс, без приведения Dynami c для максимизации производительности.

0 голосов
/ 07 января 2020

Я внедряю AVLTree в C ++ как упражнение для подготовки будущих проектов. Дерево AVLTree в основном представляет собой дерево BSTTree, но с дополнительной детализацией, что дерево сбалансировано, т. Е. Для узла x с левым дочерним элементом y и правым дочерним элементом z число дочерних элементов слева от x (дочерних элементов y и дочерних элементов y) не может отличаются от числа дочерних элементов справа от x более чем на 1 узел.

Каждый узел будет представлять значение типа int и имеет ссылку на родительский узел, на возможно существующий левый дочерний узел и на возможно существующий правый дочерний узел. 

class BSTNode {
protected:
    int value;
    BSTNode* parent;
    BSTNode* left;
    BSTNode* right;
    ...
public:
    virtual void setLeftChild(BSTNode* left); 
    ...
}

Чтобы отследить количество дочерних узлов, у меня есть AVLNode, расширяющий BSTNode двумя целыми числами, leftAffinity и rightAffinity, где leftAffinity сообщает мне количество узлов слева ( аналогично для права с rightAffinity). Поскольку я не гарантирую, что значения, которые я добавляю, всегда уникальны, я не могу обновить сходство, пока не найду место для размещения нового узла. 

class AVLNode : public BSTNode {
private:
    int leftAffinity;
    int rightAffinity;
    ...
public:
    void setLeftChild(BSTNode* left) override;
    ...
}

Как только я успешно установил левый потомок узла равным left , в AVLNode я также обновляю leftAffinity текущего узла (и рекурсивно до родительского элемента родительского элемента до достижения root дерева) до left->getLeftAffinity() + left->getRightAffinity().

Проблема здесь в том, что функции по схожести определены в AVLNode, поэтому я не могу немедленно вызвать left-> getLeftAffinity () без приведения, так как здесь я не знаю, является ли left BSTNode или AVLNode. Я знаю, что идея заключается в том, чтобы любой дочерний узел AVLNode также был только AVLNode, что можно было бы обеспечить, гарантируя, что любой BSTNode, который не является AVLNode, преобразуется в AVLNode.

  • Я делаю я не хочу изменять аргумент функции для получения AVLNode * вместо этого, так как это вынуждает меня объявлять left, right и parent как AVLNode * в классе AVLNode, и, таким образом, я получаю дубликаты переменных, по одной для каждого класса BSTNode и по одному для AVLNode класс, даже если left, right и parent являются частными в классе BSTNode.
  • Я не хочу использовать динамическое приведение c, поскольку целью упражнения было создание эффективной древовидной структуры данных с O(log n) сложность операций вставки и получения. Я читал, что Dynami c литье и дорого, и его также следует избегать, так как оно обычно намекает на недостаток дизайна.

Возможные подходы:

  • Создать " no-op "функция в классе BSTNode, которая переопределяется в классе AVLNode для управления сходствами узлов. Эта функция не должна быть там, так как она не связана с BSTNode.
  • Dynami c приведение к каждой операции добавления, и при успешном завершении, один раз для каждого родителя до root дерева, что слишком дорогой.
  • Не использовать виртуальный вообще для этих функций, что заставило бы меня перегрузить многие функции в AVLNode.
  • Измените все функции, чтобы получать AVLNode * вместо BSTNode *, в то же время заставляя преобразование BSTNode * в AVLNode * с конструктором в AVLNode, но это потребует динамического приведения c, так как в противном случае я потеряю leftAffinity и rightAffinity добавляемого узла и вызову другие проблемы с наследованием функции.

Выбор, который мне кажется лучшим, заключается в том, чтобы использовать подход «без операции», так как он работал бы, если бы производительность была ключевой.

Я новичок в C ++, поэтому я ценю любые мысли о подходах, которые я использую. я написал и, например, если есть тривиальное решение, которое я пропустил. Что будет лучшим выбором в этой ситуации?

1 Ответ

1 голос
/ 07 января 2020

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

BSTNode, вероятно, не добавляет достаточного значения в этом роль, чтобы оправдать осложнения, которые он производит, и вам, вероятно, следует просто избавиться от него.

Но иногда подобные вещи являются полезными для предоставления базовых реализаций скелета для сложных самообращающихся классов. реализовать. В C ++ типо-корректный способ сделать это с любопытным повторяющимся шаблоном шаблона со странным именем: https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern

Используя этот шаблон, базовый класс определяется как шаблон, который принимает в качестве параметра производный класс: 

template <class NODE> class BSTNode {
    int value;
    NODE *left;
    NODE *right;
    ...
}

class AvlNode : public BSTNode<AvlNode> {
   ...
}

Теперь все указатели в AvlNode имеют правильный тип, и приведение не требуется.

...