Являются ли структуры данных подходящим местом для shared_ptr?

Question

Я нахожусь в процессе реализации двоичного дерева в C ++. Традиционно у меня был бы указатель влево и указатель вправо, но ручное управление памятью обычно заканчивалось слезами. Что приводит меня к моему вопросу ...

Являются ли структуры данных подходящим местом для использования shared_ptr?

Answer 1

Я думаю, это зависит от того, где вы будете их использовать. Я предполагаю, что вы думаете о том, чтобы сделать что-то вроде этого:

template <class T>
class BinaryTreeNode 
{
    //public interface ignored for this example
    private:
        shared_ptr<BinaryTreeNode<T> > left;
        shared_ptr<BinaryTreeNode<T> > right;
        T data;
}

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

Мой ответ будет: нет, это не подходящее место для использования shared_ptr, так как использование shared_ptr подразумевает, что объект на самом деле является общим - однако, узел в двоичном дереве не когда-либо совместно использовался , Однако, как указал Мартин Йорк, зачем изобретать велосипед - уже есть умный тип указателя, который делает то, что мы пытаемся сделать - auto_ptr. Так что иди с чем-то вроде этого:

template <class T>
class BinaryTreeNode 
{
    //public interface ignored for this example
    private:
        auto_ptr<BinaryTreeNode<T> > left;
        auto_ptr<BinaryTreeNode<T> > right;
        T data;
}

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

Answer 2

Поскольку левый и правый не являются общими, boost :: shared_ptr <>, вероятно, не правильный смарт-указатель.

Это хорошее место, чтобы попробовать std :: auto_ptr <>

Answer 3

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

Учитывая, что дерево по определению состоит из узлов, каждый из которых имеет одного родителя, и, следовательно, является очевидным кандидатом для своего единственного владельца, это просто такой счастливый случай. Поздравляем!

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

(* для нас, если вы расскажете нам, как это происходит.)

Answer 4

Да, абсолютно.

Но будьте осторожны, если у вас круговая структура данных. Если у вас есть два объекта, оба с общим ptr друг другу, то они никогда не будут освобождены без ручной очистки общего ptr. В этом случае можно использовать слабый ptr. Это, конечно, не беспокоит двоичное дерево.

Answer 5

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

Answer 6

Вам даже нужны указатели? Кажется, вы могли бы использовать boost::optional<BinaryTreeNode<T> > left, right.

Answer 7

Существует некоторая дополнительная нагрузка с shared_ptr, особенно в требованиях к пространству, но если ваши элементы выделены индивидуально, то shared_ptr будет идеальным.