Двоичное дерево с разными типами узлов

Question

Я работаю над несколько сложным математическим кодом, написанным на C++. Я использую (templated) древовидные структуры для представления адаптивной функции. Из-за некоторых математических свойств я оказываюсь в ситуации, когда мне нужно перейти от одного типа узла к другому. Это должно происходить прозрачно и с минимальными издержками, как с точки зрения хранения, так и с точки зрения производительности, поскольку эти структуры используются в очень тяжелых вычислениях.

Детальная ситуация такова: у меня есть шаблонный абстрактный базовый класс, определяющий общие математические и структурные свойства общего, двусвязного узла. Каждому узлу нужна информация как от его родителя, так и от класса дерева верхнего уровня, а также для отслеживания его детей. Два класса наследуют от этого класса, FunctionNode и GenNode. Эти классы очень различаются с точки зрения хранения и функциональности, и не должны быть (по крайней мере, публичными) предками друг друга. Таким образом, я хотел бы построить дерево так:

 T 
    N 
    /\ 
    N N 
    /\ 
     G N 
    /\ 
    G G 

где Т представляет собой дерево, Н является нормальным FunctionNode и G является GenNode. Проблема заключается в N-G-переходе: N должен иметь детей типа G, а G - родительский тип N. Так как N и G - только кузены, а не братья и сестры, я не могу преобразовать N * в G *. Достаточно, чтобы G знал, что N является BaseNode, но N должен каким-то образом хранить G полиморфно, чтобы правильные виртуальные машины вызывались автоматически при прохождении дерева. Любые идеи о том, как решить эту проблему элегантно и эффективно, будут высоко оценены! :) Конечно, можно просто взломать это, но так как это очень фундаментальный кусок кода, я бы хотел иметь хорошее решение для него. Вполне вероятно, что в будущем будет много выводов этого кода.

С наилучшими пожеланиями,

Jonas Juselius

центр теоретической и вычислительной химии, Университет Тромсё

Answer 1

Не использовать наследование, когда делегация будет делать. Посмотрите на Стратегия шаблон дизайна для руководства по этому вопросу.

Переход «N-G» может быть лучше обработан с помощью подкласса N (N_g), который является унарным оператором (где другие N являются двоичными) и делегирует работу связанному объекту G. Поддерево G тогда - фактически - непересекающееся семейство классов, основанных на G, а не N.

T 
    N 
/\ 
N N 
    /\ 
    N_g N 
    | 
    G 
/\ 
    G G 

---

«Одна из проблем состоит в том, что я заранее не знаю, будет ли следующий N быть N или N_g.»

"заранее?" До чего? Если вы создаете N, а затем пытаетесь решить, должны ли они быть N_g, вы опустили несколько вещей.

1. Вы создали экземпляр N слишком рано в процессе.

2. Вы забыли написать конструктор N_g, который работает путем копирования Н.

3. Вы забыли написать replace_N_with_Ng метод, который «клоны» N, чтобы создать N_g, а затем заменяет оригинал N в дереве с N_g.

Пункт полиморфизма заключается в том, что вам не нужно знать «заранее», что-то есть. Вы должны подождать как можно дольше, чтобы создать N или N_g и связать полученный N (или подкласс N) объекта с деревом.

«Кроме того, иногда мне нужно обрезать все G: s и генерировать больше N: s, прежде чем, возможно, создать еще несколько G: s."

Изобразительное. Вы идете по дереву, заменяя N_g экземпляры N экземплярами на «обрезку». Вы идете по дереву, заменяя N экземпляров на N_g, чтобы создать новое/другое поддерево G.

Answer 2

Изучите использование RTTI - Run-time Type Information.

Answer 3

Возможно, вы используете Boost.Any?

По-моему, пример учебника на мой взгляд.

Answer 4

Подумав о проблеме еще немного я придумал следующую мысль:

Логически, но не функционально, GenNode а-добрейший из FunctionNode. Если один из них разделяет FunctionNode на два класса, один из которых содержит общие знаменатели, а один, имеющий дополнительную функциональность, только FunctionNode должен иметь, FunctionNode может наследовать от этого класса, используя частное наследование. Теперь GenNode может надежно наследовать от FunctionNode, и все проблемы могут быть решены, как обычно, с помощью виртуальных машин. Любые комментарии?