умные указатели для моделирования общей древовидной структуры и ее итераторов - PullRequest
Новая
       32

умные указатели для моделирования общей древовидной структуры и ее итераторов

2 голосов
/ 13 июля 2011

Я моделирую общую древовидную структуру, имея класс для каждого узла с указателями на родителя, первого потомка и первого брата, а также указатель на последнего брата (не нужно, но полезно). К этому я добавляю некоторые дополнительные данные atd. Моя текущая реализация: 

class TreeNode {
    typedef boost::shared_ptr<TreeNode> Ptr;
    typedef boost::weak_ptr<TreeNode> WPtr;

    WPtr p2parent;     ///< pointer to the parent node (NULL in the root)
    Ptr p2sibling;     ///< pointer to the first sibling (or NULL)
    Ptr p2child;       ///< pointer to the first child (or NULL)
    WPtr p2lastChild;  ///< pointer to the last child (not strictly needed)
};

Как видите, я использую shared_ptr для одноуровневого и дочернего элемента, поэтому можно удалить все дерево, просто удалив его корень. Что касается указателя на родителя, я знаю, что не должен использовать shared_ptr, так как это создаст циклы, поэтому мне придется выбирать между слабым_птром и необработанным указателем (TreeNode *) - есть мысли?

Для (необязательного) указателя на последний дочерний элемент, выбор между слабым_птр, общим_птр и необработанным указателем - что является лучшим выбором, чтобы сделать весь класс внутренне непротиворечивым?

Наконец, у меня есть пара итераторов по структуре, например, итератор atd для глубины. Какие указатели должны использовать итераторы внутри: необработанный указатель, weak_ptr или shared_ptr? Каковы преимущества трех подходов?

Ответы [ 2 ]

6 голосов
/ 13 июля 2011

shared_ptr - полное перерасход: это дерево, поэтому нет общего владения узлами. У каждого узла есть один владелец: его родитель.

Если используемая вами реализация поддерживает его, вы должны использовать std::unique_ptr для двух дочерних указателей и для указателя на корневой узел. Если ваша реализация не поддерживает std::unique_ptr, вы можете использовать std::auto_ptr, но вы захотите явно сделать класс узла некопируемым. В любом случае вы можете использовать необработанный указатель для указателя на родителя.

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

Итератору нужен только необработанный указатель на элемент, на который он указывает.

2 голосов
/ 13 июля 2011

Для указателя родителя: Необходимо убедиться, что он всегда указывает на фактического родителя в установщиках для потомков в родительском элементе, поэтому добавить unset в деструктор Treenode сравнительно просто. В этом случае подойдет тупой указатель.

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

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

Итераторы: Следует использовать умный указатель.

  • Если они используют shared_ptr, они сохранят поддерево живым, даже если вы измените дерево и отключите его.
  • Если они используют weak_ptr, они станут недействительными при удалении указанного узла (вам нужно будет убедиться, что указатель все еще действует во многих местах).

Выбор зависит от того, какую семантику вы хотите.

...