estruturas de dados são um lugar apropriado para shared_ptr?

Question

Eu estou no processo de implementação de uma árvore binária em C ++. Tradicionalmente, eu teria um ponteiro para a esquerda e um ponteiro para a direita, mas o gerenciamento de memória manual normalmente termina em lágrimas. O que me leva à minha pergunta ...

são estruturas de dados um local apropriado para uso shared_ptr?

Answer 1

Eu acho que depende de onde você estaria usando-os. Estou assumindo que o que você está pensando em fazer é algo como isto:

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

Isso faria sentido perfeito se você está esperando sua estrutura de dados para lidar com os nós criados dinamicamente. No entanto, uma vez que não é o design normal, eu acho que é impróprio.

A minha resposta seria que não, que não é um local apropriado para uso shared_ptr, como o uso de shared_ptr implica que o objeto é realmente compartilhado - no entanto, um nó em uma árvore binária é não sempre compartilhado. No entanto, como Martin Iorque apontou, por que reinventar a roda - já existe um tipo de ponteiro inteligente que faz o que nós estamos tentando fazer - auto_ptr. Então, vá com algo parecido com isto:

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

Se alguém perguntar por que os dados não é um shared_ptr, a resposta é simples - se cópias dos dados são bons para o cliente da biblioteca, eles passam no item de dados, e a árvore nó faz uma cópia. Se o cliente decide que as cópias são uma má idéia, então o cliente código pode passar um shared_ptr, que o nó de árvore pode seguramente copiar.

Answer 2

Porque esquerda e direita não são compartilhados boost :: shared_ptr <> é provavelmente não o ponteiro inteligente correto.

Este seria um bom lugar para tentar std :: auto_ptr <>

Answer 3

Sim, absolutamente.

Mas cuidado, se você tem uma estrutura de dados circular. Se você tem dois objetos, ambos com um ptr compartilhada com o outro, então eles nunca serão libertados sem limpar manualmente o PTR compartilhada. O PTR fraco pode ser utilizado neste caso. Isto, naturalmente, não é uma preocupação com uma árvore binária.

Answer 4

gerenciamento de memória escrita manualmente não é tão difícil nessas ocasiões felizes, onde cada objeto tem um único proprietário, que pode, portanto, excluir o que possui em seu destruidor.

Tendo em conta que uma árvore, por definição, consiste em nós que cada um tem um único pai, e, portanto, um candidato óbvio para o seu único proprietário, esta é apenas uma ocasião tão feliz. Parabéns!

Eu acho que seria bem a pena * desenvolvimento de uma tal solução no seu caso, e também tentar a abordagem shared_ptr, escondendo as diferenças inteiramente por trás uma interface idêntica, para que você alternar entre os dois e comparar a diferença de desempenho com algum realista experimentos. Essa é a única maneira segura de saber se shared_ptr é adequado para a sua aplicação.

(* para nós, se você nos dizer como ele vai.)

Answer 5

Nunca uso shared_ptr para os nós de uma estrutura de dados. Ela pode causar a destruição do nó a ser suspensas ou adiadas se em algum momento a propriedade foi compartilhado. Isto pode causar destruidores de ser chamado na seqüência errada. É uma boa prática em estruturas de dados para os construtores de nós para conter qualquer código que casais com outros nós e os destruidores para conter código que de-casais de outros nós. Destruidores chamados na seqüência errada pode quebrar o seu design.

Answer 6

Há um pouco de sobrecarga extra com um shared_ptr, nomeadamente nos requisitos de espaço, mas se seus elementos são alocados individualmente em seguida, shared_ptr seria perfeito.

Answer 7

Você precisa mesmo ponteiros? Parece que você poderia usar boost::optional<BinaryTreeNode<T> > left, right.