Les structures de données un endroit approprié pour shared_ptr?

Question

Je suis en train de mettre en œuvre un arbre binaire en C ++. Traditionnellement, j'aurais un pointeur vers la gauche et un pointeur vers la droite, mais la gestion de la mémoire manuelle se termine généralement en larmes. Ce qui me conduit à ma question ...

Les structures de données un endroit approprié pour utiliser shared_ptr?

Answer 1

Je pense que cela dépend de l'endroit où vous seriez les utiliser. Je suppose que ce que vous envisagez de faire quelque chose comme ceci:

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

Ce serait logique si vous attendez votre structure de données pour gérer les noeuds créés dynamiquement. Cependant, étant donné que ce n'est pas la conception normale, je pense qu'il est inapproprié.

Ma réponse serait que non, ce n'est pas un endroit approprié d'utiliser shared_ptr, comme l'utilisation de shared_ptr implique que l'objet est en fait partagé - cependant, un noeud dans un arbre binaire est pas jamais partagé. Cependant, comme Martin York a souligné, pourquoi réinventer la roue - il y a déjà un type de pointeur intelligent qui fait ce que nous essayons de faire - auto_ptr. Donc, aller avec quelque chose comme ceci:

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

Si quelqu'un demande pourquoi les données ne sont pas une shared_ptr, la réponse est simple - si des copies des données sont bonnes pour le client de la bibliothèque, ils passent dans l'élément de données, et l'arbre noeud fait une copie. Si le client décide que les copies sont une mauvaise idée, le client code peut passer dans un shared_ptr, que le nœud de l'arbre peut en toute sécurité copie.

Answer 2

Parce que gauche et droite ne sont pas partagés boost :: shared_ptr <> est probablement pas le pointeur intelligent correct.

Ce serait un bon endroit pour essayer std :: auto_ptr <>

Answer 3

Oui, tout à fait.

Mais attention si vous avez une structure de données circulaire. Si vous avez deux objets, les deux avec un REE partagé les uns aux autres, ils ne seront jamais libérés sans compensation manuellement le PTR partagé. Le PTR faible peut être utilisé dans ce cas. Ceci, bien sûr, est pas un souci avec un arbre binaire.

Answer 4

La gestion de la mémoire d'écriture est manuellement pas si difficile à ces occasions heureuses où chaque objet a un seul propriétaire, qui peut donc supprimer ce qu'elle possède dans son destructor.

Étant donné qu'un arbre par définition se compose de noeuds qui ont chacun un seul parent, et donc un candidat évident pour leur seul propriétaire, c'est juste une telle occasion heureuse. Félicitations!

Je pense que ce serait bien utile * développer une telle solution dans votre cas, et aussi essayer l'approche shared_ptr, cachant les différences entièrement derrière une interface identique, de sorte que vous basculer entre les deux et comparer la différence de performance avec un peu réaliste expériences. C'est le seul moyen sûr de savoir si shared_ptr est adapté à votre application.

(* pour nous, si vous nous dire comment ça se passe.)

Answer 5

Ne jamais utiliser shared_ptr pour les noeuds d'une structure de données. Elle peut provoquer la destruction du nœud à être suspendu ou retardé si à tout moment la propriété était partagée. Cela peut causer des Destructeurs à appeler dans la mauvaise séquence. Il est une bonne pratique dans les structures de données pour les constructeurs de noeuds pour contenir tout code que les couples avec d'autres noeuds et les destructeurs contiennent un code de-couples d'autres nœuds. Destructeurs appelé dans la mauvaise séquence peut briser cette conception.

Answer 6

Il y a un peu de frais généraux supplémentaires avec un shared_ptr, notamment dans l'espace requis, mais si vos éléments sont attribués individuellement alors shared_ptr serait parfait.

Answer 7

Avez-vous besoin de pointeurs? Il semble que vous pouvez utiliser boost::optional<BinaryTreeNode<T> > left, right.