5

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

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

4

7 回答 7

8

我认为这取决于您将在哪里使用它们。我假设您正在考虑做的事情是这样的：

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;
}

如果有人问为什么 data 不是 shared_ptr，答案很简单——如果数据的副本对库的客户端有好处，他们会传入数据项，然后树节点会制作一个副本。如果客户端认为复制是一个坏主意，那么客户端代码可以传入一个 shared_ptr，树节点可以安全地复制它。

于 2008-12-17T23:13:51.933 回答
3

因为 left 和 right 不共享 boost::shared_ptr<> 可能不是正确的智能指针。

这将是尝试 std::auto_ptr<> 的好地方

于 2008-12-17T23:16:13.177 回答
2

是的，一点没错。

但如果你有一个循环数据结构，请小心。如果你有两个对象，它们都有一个共享的ptr，那么如果不手动清除共享的ptr，它们就永远不会被释放。在这种情况下可以使用弱 ptr。当然，这不是二叉树的担心。

于 2008-12-17T22:53:39.477 回答
2

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

鉴于根据定义，一棵树由节点组成，每个节点都有一个父节点，因此显然是其单一所有者的候选者，这真是一个快乐的时刻。恭喜！

我认为在您的情况下开发这样的解决方案非常值得*，并且还尝试了这种shared_ptr方法，将差异完全隐藏在相同的界面后面，因此您可以在两者之间切换，并将性能差异与一些实际实验进行比较。这是知道是否shared_ptr适合您的应用程序的唯一可靠方法。

（* 对我们来说，如果你告诉我们情况如何。）

于 2008-12-17T23:06:21.557 回答
1

切勿将 shared_ptr 用于数据结构的节点。如果在任何时候共享所有权，它可能会导致节点的销毁被暂停或延迟。这可能会导致以错误的顺序调用析构函数。在数据结构中，节点的构造函数包含与其他节点耦合的任何代码，而析构函数包含与其他节点分离的代码，这是一种很好的做法。以错误顺序调用的析构函数可能会破坏这种设计。

于 2009-08-07T08:59:57.000 回答
0

shared_ptr 有一些额外的开销，特别是在空间要求方面，但如果您的元素是单独分配的，那么 shared_ptr 将是完美的。

于 2008-12-17T22:54:09.553 回答
0

你甚至需要指针吗？看来你可以使用boost::optional<BinaryTreeNode<T> > left, right.

于 2008-12-19T12:31:05.297 回答