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

Question

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

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

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

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

С уважением,

Йонас Юзелиус

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

Answer 1

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

Переход "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, который работает путем копирования N.

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

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

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

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

Answer 2

Подумав еще над проблемой, я пришел к следующей мысли:

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

Answer 3

Хотели ли вы использовать Boost.Any ?

На мой взгляд, это похоже на пример из учебника.

Answer 4

Ознакомьтесь с использованием RTTI - Информация о типе времени выполнения .