泛型二进位搜索树中的根应该使用什么类型的指针？

Question

这是我的通用二进制搜索树的标题。现在，我只是使用树根的原始指针。我应该使用什么样的指针？其中一些类型是唯一的、共享的、(智能指针)弱的、原始的、打开的。。。。。

template <typename T>
class BST
{
public:
    BST();
    BSTNode<T>* Root;
    void Insert(BSTNode<T> newNode);
    void Delete(T deleteNode);
    BSTNode<T>* ReturnNodeSearch();
    BSTNode<T>* MinimumValue();
    BSTNode<T>* MaximumValue();
    bool isEmpty();
};

Answer 1

使用std::unique_ptr，因为您不太可能希望两个单独的BST对象共享相同的实现节点。通常，在这种情况下，您只需对BST对象本身使用外部引用或(可能)外部BST。

Answer 2

这取决于你想做什么。我建议最好的做法是使用std::unique_ptr<>或std::shared_ptr<>来确保在不再需要时正确释放内存。但是，原始指针可以在这里工作，尽管您必须自己处理去分配。通常，用于处理和拥有动态分配内存的智能指针的好处往往大于使用原始指针的好处。

在更详细但较高的层次上：

• 原始指针--处理问题，但如果不再需要这个内存，则只需管理取消分配即可。当某个对象/函数仍然有指向它的指针时，您可能会意外地释放一个对象/函数中的内存。
• std::unique_ptr<> --将管理内存在其生存期内，如果您不必与任何其他对象共享指针，则很好。
• std::shared_ptr<> --还将管理内存，通过引用来增加一些开销，计算有多少std::shared_ptr<>也在监视内存位置。这还将确保内存仅在没有其他std::shared_ptr<>对象指向内存时才被移除。
• std::weak_ptr<> --只能与std::shared_ptr<>结合使用，用于防止内存中相同对象的引用周期。

不一定有错误的答案。它只取决于您想要的实现。唯一不应该使用的类型是std::auto_ptr<>，所以不要使用该类型。

Answer 3

当查看您的代码示例时，会想到三个选项，其中任何一个选项都是可行的；下面让我们探讨一下这些选项。

• Raw pointer
• shared_ptr<T>
• unique_ptr<T>

每一种方法都有各自的缺点和优点。

由于在您的示例中使用的是raw，我将首先从这个示例开始：

原始

• Pro: --你可以灵活地管理你自己的内存，但这是以更高的责任为代价的。
• Con: --它容易出现内存泄漏、悬空和无效指针。

shared_ptr

• Pro: -为您管理内存；并且可以跨多个对象访问，因为它是通过引用计数共享内存。
• Con: --它基于这样一种假设，即您永远不会因为使用这个智能指针而面临内存泄漏或悬空指针，在这种情况下，它并不总是被保证释放，但在大多数情况下通常是这样。有时，您可能不希望一个指针可以跨多个对象访问。它也有一个小的性能影响从参考计数。

unique_ptr

• Pro: --与上面几乎相同的是，只有一个对象可以拥有它，为不必要的访问提供更多的保护。
• Con: -类似于上述假设，即内存将始终被释放。如果所需的功能确实需要多个对象或源在未来某个时间点访问此功能，则使用这种类型的指针将限制您。您可以转移所有权，但不能通过多个对象访问。

最后，这取决于您想要使用哪种类型的特殊需要。在特定情况下，在类中使用原始指针(如果它们是private members )没有什么错，但是在处理内存的分配和释放时，您有更多的工作要管理类，更需要做的是良心。如果使用unique_ptr，那么就需要知道内存对象是否严格地属于属于类对象的内部。如果使用shared_ptr，那么就需要知道哪些外部对象将引用它。

最后，你问：

What kind of pointer should I use?

从上述信息中获取知识，通过理解您正在使用的对象的类型，让我们考虑BST所做的或所负责的事情，以及它作为类对象的主要角色。

我们知道它是一个Binary Space Partitioning Tree，通常与Binary Search一起使用。其中一个是data structure，另一个是searching algorithm。

它是一棵由一组nodes组成的树，每个node都有2 leaf nodes。树中的第一个node通常称为root或head，其中没有数据或是empty的叶节点通常称为tail，通常设置为null或nullptr。我们可以看到这些节点之间的关系，并且知道BST将至少具有root节点的ownership。这样，BST对象的每个实例都将是来自另一个实例的唯一实例。示例：

BST tree1; // Tree 1
BST tree2; // Tree 2

// Not valid code below but shown to illustrate a concept
tree1.root != tree2.root; // These two roots are not equal as in not the same memory.

这就是我们想让一棵树与另一棵树保持唯一的东西，由于这种行为，我们真的不想使用shared_ptr。对于这个特定的类，我认为如果不使用raw pointers和管理您自己的内存，并使用智能指针在多个对象之间显示ownership和uniqueness，那么unique_ptr将是更好的选择。

在设计类和尝试使用哪个smart pointer时，您应该问并自己回答以下几个基本问题：

• 这个对象是have a吗？如果是的话；它是唯一拥有它的，还是每个实例的内部内存需要是唯一的？如果是，则使用unique_ptr
• 这个对象必须跨多个对象引用吗？如果是，请使用shared_ptr。

以下是一些参考资料:一篇来自论文，另一篇来自和Q/A，一篇来自代码评审：

• BST-SmartPointers.pdf
• 堆栈溢出: BST中唯一的而不是共享的
• 堆栈代码检查: BST w/ Smart指针

这些参考资料也可以帮助您做出明确的决定。