数据结构是否适合使用shared_ptr？

Question

我正在用C++实现二叉树。传统上，我会有一个指针指向左边和一个指针指向右边，但手动内存管理通常会导致问题。这让我想到了我的问题...

数据结构是否适合使用shared_ptr？

- Gabriel Isenberg

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意味着对象实际上是共享的。但是，二叉树中的节点从未被共享。不过，正如Martin York指出的那样，为什么要重复造轮子 – 已经有了一个能做我们想做的事的智能指针类型 – 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，答案很简单 - 如果数据的副本对于库的客户端有好处，他们会传入数据项，树节点会进行复制。如果客户端决定副本是个坏主意，那么客户端代码可以传入一个shared_ptr，这样树节点就可以安全地复制。

- Harper Shelby

---

为什么不使用auto_ptr<>？你遗漏了公共接口。现在必须包含一些内存管理代码。这就是为什么我们有智能指针，以便我们不必重新发明轮子来进行内存管理。 - Martin York

好的，auto_ptr 对他们来说是一个有效的选择 - 实际上，可能更好，因为它的语义与二叉树节点的左右指针的语义一致。 - Harper Shelby

你可能需要将类型 T 传递到 left 和 right 的声明中，否则无法编译。 - Mark Kegel

自 C++11 起，auto_ptr 已被弃用，您应该使用 unique_ptr。 - Dominic

Answer 2

因为左右不共享，所以 boost::shared_ptr<> 可能不是正确的智能指针。

在这种情况下，尝试使用 std::auto_ptr<> 是一个好选择。

- Martin York

Answer 3

是的，绝对可以。

但是如果您有一个循环数据结构，请小心。如果您有两个对象，它们都具有彼此共享的指针，则它们将永远不会被释放，除非手动清除共享指针。在这种情况下，可以使用弱指针。当然，在二叉树中不必担心这个问题。

- David Norman

---

树本质上不会有环。 - Martin York

Answer 4

手动编写内存管理并不难，特别是在每个对象都有单一所有者的情况下，因此可以在其析构函数中删除所拥有的内容。

考虑到树由定义上每个节点都只有一个父节点，因此很明显它们有一个明显的单一所有者，这就是这样一个幸福的场合。恭喜！

我认为在你的情况下开发这样的解决方案非常值得，并且还应该尝试使用`shared_ptr`方法，将差异完全隐藏在相同的接口后面，这样您可以在两种方法之间切换并通过一些真实的实验比较性能差异。这是唯一确定`shared_ptr`是否适用于您的应用程序的方法。

（*如果您告诉我们结果，对我们来说非常重要。）

- Earwicker

Answer 5

在数据结构的节点中，永远不要使用shared_ptr。如果在任何时候共享了所有权，则可能会导致节点的销毁被暂停或延迟。这可能会导致析构函数按错误的顺序调用。 在数据结构中，一个好的实践是将节点的构造函数包含与其他节点耦合的任何代码，并将析构函数包含解除与其他节点耦合的代码。以错误的顺序调用析构函数可能会破坏此设计。

- John Morrison

Answer 6

使用shared_ptr会增加一些额外的开销，尤其是空间需求方面，但如果您的元素是单独分配的，则shared_ptr将是完美的选择。

- Mark Ransom

Answer 7

你真的需要指针吗？看起来你可以使用boost::optional<BinaryTreeNode<T>> left,right。

- MSalters