Поиск детей

Question

У меня есть класс A. Класс A отвечает за управление временем жизни объектов B, и он содержит контейнер объектов B, равный map<BGuid,B>, а каждый объект B содержит контейнер объектов C, равный map<CGuid,C>. У меня есть один global Объект для всего приложения.

У меня следующая проблема: У меня есть объект CGuid, и я хочу использовать его, чтобы найти мой объект C. Но для этого мне также нужно знать объект BGuid, который скажет мне, в каком объекте B мне следует искать мой объект C. Но все, что у меня есть, это CGuid, что означает, что я должен проверить каждый объект B, чтобы увидеть, содержит ли он мой объект C. Однако я думаю, что это грязно. Я подумал, что, возможно, у меня должен быть другой класс, скажем, M, который будет содержать карту всех моих объектов C, и я могу искать прямо в нем только с помощью CGuid, но это означает, что мне нужно поддерживать дополнительную карту только для поиска.

Также я исключаю, что в будущем мой класс C будет содержать map<Dguid,D>, поэтому у меня возникнет та же проблема с объектами D, на этот раз еще хуже, мне понадобятся Bguid, Cguid и Dguid, чтобы найти мой объект D.

Как решить эту проблему?

Answer 1

У вас классические отношения Родитель - Дети. Я предлагаю вам улучшить свой дизайн, не уточняя, как обрабатывается (то есть с картами). используйте контейнер для хранения дочерних элементов, и пусть у дочерних элементов есть указатель на родительский элемент. Таким способом легко пройти от любой точки до вершины.

Полезным шаблоном OOP Design для этих случаев является CompositePattern

Answer 2

map<BGuid,B>, map<CGuid,pair<B,C>>, map<DGuid,pair<C,D>>

С GUID вы получаете объект и родительский объект.С объектом вы получаете GUID.Рекурс от начала.

Answer 3

Вы можете назначить диапазоны GUID детей каждому родительскому GUID.Предположим, что BGuid находится в интервале [0, 9], а CGuid в интервале [0, 99].Теперь вы можете сопоставить десять CGuids с каждым BGuid с помощью такой функции:

mapGuids(B): CGuid => BGuid = B % 10

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

Answer 4

Есть ли у вас ограничения по памяти?Если нет, я бы сохранил таблицы обратного просмотра (карты), поэтому вам нужна таблица для C-> B, когда вы добавляете D, вам нужна вторая D-> C, поэтому, если у вас есть C, чтобы найти ее правильно, вынужен один поиск, чтобы найти B, затем из A вы можете пройти еще два поиска.Намного быстрее, чем итерация по всем B, ищущим C!

Еще одна альтернатива: есть ли у вас контроль над Guid, если это так, вы можете попробовать ввести информацию о "пути" в guid.Скажем, к примеру, B guid - это «B.1», «B.2», «B.3» и т. Д., Исправление после «.»разделитель говорит вам, что это такое.Когда вы добавляете C, вы можете просто добавить дополнительный '.', То есть guid C 1 (давайте предположим, что он хранится в B 1) = "B.1.1", так что теперь, чтобы найти объект, вы анализируете ключ и вуаляу вас есть свой «путь» к C1.