使用智能指针的C++链接列表

Question

我只使用链接列表的原始指针和模板.例如,成员数据,Node<T>* head;当我插入节点时,其中一行是head = new Node<T>(data);.

但是,现在我需要使用智能指针,我不知道如何更改它以使用智能指针.会员数据是否会更改为shared_ptr<Node<T>> head;,另一行会更改为
head = shared_ptr<Node<T>>( new <Node<T>>(data) );？

Answer 1

您不需要为链表使用智能指针,因为该语句没有意义.你不使用低级别的数据结构的智能指针.您可以将智能指针用于高级程序逻辑.

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

如果你真的很需要你自己的高度专业化/优化的定制容器类,因为整个C++标准库是不适合您的需求,您需要更换为std::list,std::vector,std::unordered_map和其他优化,测试,文档和安全的容器-这一点我非常怀疑! - 然后你必须手动管理内存,因为这样一个专门的类几乎肯定需要内存池,写时复制甚至垃圾收集等技术,所有这些都与典型的智能指针冲突相当简单的删除逻辑.

用Herb Sutter的话说:

永远不要使用拥有原始指针和删除,除非在极少数情况下实现您自己的低级数据结构(甚至然后保持良好封装在类边界内).

Herb Sutter和Bjarne Stroustrup的C++核心指南中也表达了这些内容:

通过将所有拥有指针转换为unique_ptrs和shared_ptrs,无法解决这个问题(大规模),部分原因是我们需要/使用拥有"原始指针"以及基本资源句柄实现中的简单指针.例如,公共向量实现具有一个拥有指针和两个非拥有指针.

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

^[*] 或者只是std::vector,因为缓存局部性几乎总是更好的选择.

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是一个观察指针。然而，复制之类的东西需要手工定义和实现。

2. 使用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
   

   这是更安全的替代方案，但性能不如唯一指针。此外，它是可复制的设计。

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

该_prev指针是在这两个选项只有一个观察指针：它的任务不是保持以前的节点活着，但只提供一个链接去拜访他们。为此， aNode *通常就足够了（--注意：观察指针意味着您永远不会在指针上执行与内存相关的操作，例如new, delete）。

如果你想要更安全，你也可以使用 a 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 

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