Когда допустима циклическая ссылка на родительский указатель?

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

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

Я понимаю, что это, вероятно, не самая лучшая идея в целом. Из общего эмпирического правила кажется справедливым сказать: «Не делай этого!»

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

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

Два объекта не могут «владеть» друг другом: это вызывает неразрешимую дилемму для порядка инициализации и удаления. Один должен быть необязательной ссылкой или иным образом указывать, что один объект не будет управлять временем жизни другого.

Рассмотрим двусвязный список: два узла связываются друг с другом взад-вперед, но ни один из них не «владеет» другим (список владеет ими обоими). Это означает, что ни один из узлов не выделяет память для другого и не несет никакой другой ответственности за идентификацию или управление временем жизни другого.

Деревья имеют сходные отношения, хотя узлы в дереве могут выделять детей, а родители имеют собственных детей. Ссылка от ребенка к родителю помогает в прохождении, но опять же не определяет владение.

В большинстве конструкций ОО ссылка на другой объект в качестве члена данных объекта подразумевает владение. Например, предположим, у нас есть классы Car и Engine. Ни один из них не очень полезен сам по себе. Можно сказать, что эти объекты зависят друг от друга: они требуют присутствия другого для выполнения полезной работы. Но кто "владеет" другим? В этом случае мы бы сказали, что автомобиль владеет двигателем, потому что автомобиль является «контейнером», в котором живут все автомобильные компоненты. И в ОО, и в реальном дизайне автомобиль является суммой его частей, и все эти части связаны друг с другом в контексте автомобиля. Двигатель может иметь ссылку обратно на автомобиль, или он может иметь ссылку на TorqueConverter,

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

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

Есть несколько аспектов, которые следует учитывать в такой конструкции:

• структурные зависимости
• отношение собственности (то есть состав против другого вида связи)
• навигационные потребности

Структурная зависимость между классами:

Если вы хотите повторно использовать классы компонентов, вам следует избегать ненужных зависимостей и избегать таких замкнутых круговых структур.

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

Право собственности на объекты:

Владеет ли один объект другим? Или иным образом заявлено: если один объект уничтожен, будет ли уничтожен и другой?

Эта тема была подробно рассмотрена Snowman, поэтому я не буду здесь ее обсуждать.

Навигация нужна между объектами:

Последний вопрос - необходимость навигации. Давайте возьмем мой любимый пример - шаблон составного дизайна « Банды четырех» .

Гамма и др. прямо упомяните о потенциальной необходимости иметь явную родительскую ссылку: « Сохранение ссылки от дочерних компонентов на их родительский элемент может упростить обход и управление сложной структурой » Конечно, вы можете представить систематический нисходящий обход, но для очень больших составных объектов это может значительно замедлить работу и в геометрической прогрессии. Прямая ссылка, даже круговая, может значительно облегчить манипулирование вашими композитами.

Примером может служить графическая модель электронной системы. Композитная структура может представлять собой электронные платы, схемы, элементы. Чтобы отобразить модель и манипулировать ею, вам понадобятся некоторые геометрические прокси в графическом представлении. Тогда, конечно, гораздо проще перейти от элемента GUI, выбранного пользователем, к компоненту, чтобы выяснить, кто является родителем и с соответствующими элементами «брат / сестра», чем начать поиск сверху вниз.

Конечно, как указали Гамма и др., Вы должны обеспечить неизменность круговых отношений. Это может быть сложно, как показал вопрос SO, на который вы ссылаетесь. Но это совершенно управляемо и безопасно.

Вывод

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

Единственный момент заключается в том, что иногда люди стремятся идти в таком направлении быстро. Так что стоит рассмотреть все 3 аспекта, прежде чем принимать решение пойти на это или нет.

Обычно циклические ссылки - очень плохая идея, потому что они означают циклические зависимости. Вы, наверное, уже знаете, почему циклические зависимости плохие, но для полноты, версия tl; dr состоит в том, что всякий раз, когда классы A и B зависят друг от друга, невозможно понять / исправить / оптимизировать / и т. Д. A или B без понимание / исправление / оптимизация / и т. д. другого класса одновременно. Что быстро приводит к основам кода, где вы ничего не можете изменить, не меняя ничего.

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

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

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

[...] предлагает даже для графиков не делать что-то подобное.

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

В качестве примера, дерево квадрантов может хранить элементы в программном обеспечении векторной графики. Однако выбор пользователя сохраняется в отдельном списке выбора ссылок / указателей на векторные элементы. Когда пользователь хочет удалить этот выбор, мы должны обновить дерево квадрантов, и там может быть намного эффективнее обновить дерево снизу вверх, начиная с листьев, а не сверху вниз. В противном случае для каждого элемента вам придется работать от корня до листа, а затем выполнять резервное копирование снова.

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

Преимущества:

• Когда объекты могут существовать в нескольких списках одновременно, память для узлов списка должна быть выделена и освобождена только один раз.

• Когда объект должен быть уничтожен, вы можете легко удалить его из всех списков, в которых он находится, без линейного поиска в каждом списке.

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