Какой самый безопасный способ реализовать древовидную структуру?

Question

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

class tree_node
{
    public:
        tree_node (tree_node* parent) : parent_(parent)
        {
            parent_.add_child(this);
        }

    private:
        std::vector<tree_node*> children_;
        tree_node* parent_;
}

Моя главная проблема с этим дизайном заключается в том, что класс tree_node может удалить любого из своих дочерних и родительских элементов. Я хочу изменить дизайн, чтобы запретить это. Итак:

• Можно ли как-то изменить дизайн, чтобы использовать ссылки вместо указателей? (вектор ссылок не работает).
• Если я использую ссылки, как я могу относиться к особому случаю корневого узла (у которого нет родителя)?
• Можно ли запретить удаление детей / родителей из класса tree_node?

Любые другие идеи для достижения моей цели приветствуются.

Answer 1

Безопасное решение - сохранить дочерние элементы как boost :: shared_ptr и сохранить родительский элемент в виде необработанного указателя. Тогда корневому узлу присваивается родительский узел null.

Чтобы ответить на ваши вопросы:

• Можно ли как-то изменить дизайн, чтобы использовать ссылки вместо указателей? (вектор ссылок не работает).

Вы должны использовать указатели в этой ситуации. Ссылки просто не будут работать.

• Можно ли запретить удаление детей / родителей в классе tree_node?

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

Вы говорите, что хотите запретить классу что-то делать для себя. Как это имеет смысл? Если вы не хотите, чтобы ваш класс удалял своих детей, просто не делайте этого.

Answer 2

РЕДАКТИРОВАТЬ: Чтобы ответить на вопрос, заданный в заголовке, но не в тексте: самый безопасный способ - НЕ повторно реализовать дерево.Используйте стандартный библиотечный ассоциативный контейнер или, возможно, увеличьте BGL.

Вы можете использовать ссылочный класс-оболочку в контейнерах (и boost::optional, содержащий такую ​​обертку для родительской ссылки, если это необходимо), но я не уверенэто решение вашей основной проблемы.Класс tree_node не управляет памятью, поэтому нет особого риска удаления.

Далее, вам действительно нужно N-арное дерево?Не могли бы вы обойтись без std::map или одного из других ассоциативных контейнеров и избежать кодирования множества ошибок?

Очевидно, что открытый API вашего дерева не должен обеспечивать прямой доступ к классу узла (см. map и его использование итераторов), поэтому, пока дерево правильно управляет памятью, ваши заботы об управлении указателями должны быть минимальными, поскольку вы полностью контролируете все управление узлами.

Answer 3

Я понимаю, почему детям нельзя разрешить удалять родительский узел, но я не понимаю, почему вы хотите запретить удаление дочернего узла.Это одна из самых фундаментальных операций на дереве.

Answer 4

Ваш класс не управляет памятью и, следовательно, не будет удалять другие узлы. Если вы хотите убедиться, что любой, кто использует класс tree_node, не удаляет ни родителей, ни детей, вам нужно поместить их в чисто виртуальный базовый класс (где они являются частными) и иметь наследование tree_node. Пользователь, который использует tree_node, затем вынужден использовать предоставленные вами методы.

Кроме того, если вы не хотите слишком беспокоиться об указателях, используйте умные указатели (см. Boost :: shared_ptr)