Les structures de données sont-elles un endroit approprié pour le shared_ptr ?

Question

Je suis en train d'implémenter un arbre binaire en C++. Traditionnellement, j'aurais un pointeur à gauche et un pointeur à droite, mais la gestion manuelle de la mémoire se termine généralement par des larmes. Ce qui m'amène à ma question...

Les structures de données sont-elles un endroit approprié pour utiliser les shared_ptr ?

Answer 1

Je pense que ça dépend de l'endroit où vous allez les utiliser. Je suppose que ce que vous envisagez de faire est quelque chose comme ça :

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 parfaitement logique si vous attendez de votre structure de données qu'elle gère les nœuds créés dynamiquement. Cependant, comme ce n'est pas la conception normale, je pense que c'est inapproprié.

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

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 des trices partagées, la réponse est simple : si des copies des données sont bonnes pour l'ensemble de l'organisation, il est possible d'en faire des copies. client de la bibliothèque, ils passent dans l'élément de données, et le nœud de l'arbre fait une copie. Si le client décide que les copies sont une mauvaise idée, alors la client Le code peut passer dans un shared_ptr, que le nœud d'arbre peut copier en toute sécurité.

Answer 2

Parce que la gauche et la droite ne sont pas partagées, boost::shared_ptr<> n'est probablement pas le pointeur intelligent correct.

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

Answer 3

Oui, absolument.

Mais attention si vous avez une structure de données circulaire. Si vous avez deux objets, qui ont tous deux un ptr partagé, alors ils ne seront jamais libérés sans effacer manuellement le ptr partagé. Le ptr faible peut être utilisé dans ce cas. Ceci, bien sûr, n'est pas un problème avec un arbre binaire.

Answer 4

L'écriture manuelle de la gestion de la mémoire n'est pas si difficile dans les cas heureux où chaque objet a un seul propriétaire, qui peut donc supprimer ce qu'il possède dans son destructeur.

Étant donné qu'un arbre est, par définition, constitué de nœuds qui ont chacun un seul parent, et donc un candidat évident pour leur propriétaire unique, c'est une heureuse occasion. Félicitations !

Je pense qu'il vaudrait la peine* de développer une telle solution dans votre cas, ET aussi d'essayer la shared_ptr qui dissimule entièrement les différences derrière une interface identique. Vous pouvez ainsi passer de l'une à l'autre et comparer les différences de performances à l'aide de quelques expériences réalistes. C'est le seul moyen sûr de savoir si shared_ptr est adapté à votre application.

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

Answer 5

N'utilisez jamais de shared_ptr pour les noeuds d'une structure de données. Cela peut entraîner la suspension ou le retard de la destruction du nœud si, à un moment donné, la propriété a été partagée. Cela peut entraîner l'appel des destructeurs dans le mauvais ordre. Dans les structures de données, il est bon que les constructeurs de nœuds contiennent du code qui se couple avec d'autres nœuds et que les destructeurs contiennent du code qui se découple des autres nœuds. Les destructeurs appelés dans le mauvais ordre peuvent briser cette conception.