使用智能指针的 C 链表

Question

我只对带有模板的链表使用原始指针。例如，成员数据 Node<T>* head; 当我插入一个节点时，其中一行将是 head = new Node<T>(data); 。

但是，现在我需要使用智能指针，但我不确定如何将其更改为使用智能指针。成员数据是否会更改为 shared_ptr<Node<T>> head; 而另一行会更改为

head = shared_ptr<Node<T>>( new <Node<T>>(data) ); ?

原文由 Mark 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您不需要为链表使用智能指针，因为该语句没有意义。您 不要 将智能指针用于低级数据结构。您将智能指针用于高级程序逻辑。

就低级数据结构而言，您使用 C++ 标准库中的标准容器类，例如 std::list[*] ，它可以解决所有内存管理问题，而无需使用任何智能指针内部。

如果您 真的 需要自己的高度专业化/优化的自定义容器类，因为整个 C++ 标准库不适合您的要求，并且您需要 替换 std::list ， std::vector ， std::unordered_map 和其他经过优化、测试、记录和安全的容器——我非常怀疑！ –，那么无论如何您都必须手动管理内存，因为这样一个专门的类的重点几乎肯定是需要内存池、写时复制甚至垃圾收集等技术，所有这些都与典型的智能指针相冲突相当简单的删除逻辑。

用 赫伯萨特 的话来说：

永远不要使用拥有原始指针和删除， 除非在极少数情况下实现自己的低级数据结构（即使这样，也要将其很好地封装在类边界内）。

Herb Sutter 和 Bjarne Stroustrup 的 C++ Core Guidelines 中也表达了类似的内容：

这个问题不能通过将所有拥有指针转换为 unique_ptrs 和 shared_ptrs 来解决（大规模），部分原因是 我们需要/使用拥有“原始指针”以及实现我们的基本资源句柄的简单指针。例如，常见的向量实现有一个拥有指针和两个非拥有指针。

在 C++ 中使用原始指针编写链表类可能是一项有用的 学术 练习。在 C++ 中使用智能指针编写链表类是一项毫无意义的学术练习。在生产代码中使用这两种自制的东西中的任何一种几乎都是错误的。

---

[*] 或者只是 std::vector ，因为由于缓存局部性，无论如何这几乎总是更好的选择。

原文由 Christian Hackl 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

设置智能指针增强列表基本上有两种选择：

1. 使用 std::unique_ptr ：

    template<typename T>
   struct Node
   {
        Node* _prev;
        std::unique_ptr<Node> _next;
        T data;
   };

   std::unique_ptr<Node<T> > root; //inside list

那将是我的第一选择。唯一指针 _next 注意没有内存泄漏，而 _prev 是一个观察指针。但是，复制构造函数和诸如此类的东西——如果你需要它们——需要手动定义和实现。

1. 使用 shared_ptr ：

    template<typename T>
   struct Node
   {
        std::weak_ptr<Node> _prev;   //or as well Node*
        std::shared_ptr<Node> _next;
        T data;
   };

   std::shared_ptr<Node<T> > root; //inside list

这是可复制的设计方案，并且由于weak_ptr而增加了进一步的安全性，见下文。当涉及到列表的结构更改（例如插入和删除）时，它的性能不如 unique_ptr，例如由于 shared_ptr 的控制块中的线程安全。

然而，遍历列表，即取消引用指针，应该与 unique_ptr 一样高效。

在这两种方法中，想法是一个节点拥有完整的剩余列表。现在，当一个节点超出范围时，剩余列表不会成为内存泄漏，因为节点会被迭代破坏（从最后一个开始）。

_prev 指针在两个选项中都只是一个观察指针：它的任务不是保持先前节点的活动，而只是提供访问它们的链接。为此， Node * 通常就足够了（–注意： 观察指针 意味着您永远不会在指针上执行与内存相关的事情，例如 new ， delete ）。

如果您想要更安全，您还可以使用 std::weak_ptr 防止类似

std::shared_ptr<Node<T> > n;
{
    list<T> li;
    //fill the list
    n = li.root->next->next; //let's say that works for this example
}
n->_prev; //dangling pointer, the previous list does not exists anymore

使用 weak_ptr ，您可以 lock() 它并以这种方式 _prev 是否仍然有效。

原文由 davidhigh 发布，翻译遵循 CC BY-SA 4.0 许可协议