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

我会看一下std::list的接口，它是链表的C++实现。看来您正在处理链接列表 class 的模板错误。理想情况下，您的链表不应该关心所有权语义（即它是否使用原始指针、智能指针或堆栈分配变量实例化）。下面是一个使用 STL 容器的所有权语义示例。但是，有来自更权威来源的更好的 STL 和所有权示例。

#include <iostream>
#include <list>
#include <memory>

using namespace std;

int main()
{

    // Unique ownership.
    unique_ptr<int> int_ptr = make_unique<int>(5);

    {
        // list of uniquely owned integers.
        list<unique_ptr<int>> list_unique_integers;

        // Transfer of ownership from my parent stack frame to the
        // unique_ptr list.
        list_unique_integers.push_back(move(int_ptr));

    } // list is destroyed and the integers it owns.

    // Accessing the integer here is not a good idea.
    // cout << *int_ptr << endl;
    // You can make a new one though.
    int_ptr.reset(new int(6));

    // Shared ownership.
    // Create a pointer we intend to share.
    shared_ptr<int> a_shared_int = make_shared<int>(5);

    {
        // A list that shares ownership of integers with anyone that has
        // copied the shared pointer.
        list<shared_ptr<int>> list_shared_integers;

        list_shared_integers.push_back(a_shared_int);

        // Editing and reading obviously works.
        const shared_ptr<int> a_ref_to_int = list_shared_integers.back();
        (*a_ref_to_int)++;
        cout << *a_ref_to_int << endl;

    } // list_shared_integers goes out of scope, but the integer is not as a
    // "reference" to it still exists.

    // a_shared_int is still accessible.
    (*a_shared_int)++;
    cout << (*a_shared_int) << endl;

} // now the integer is deallocated because the shared_ptr goes 
// out of scope.

了解所有权、内存 allocation/deallocation 和共享指针的一个很好的练习是做一个实现您自己的智能指针的教程。然后您将确切地了解如何使用智能指针，并且您将有一个 xen 时刻，您会意识到 C++ 中的几乎所有内容都返回到 RAII（资源所有权）。

回到你问题的关键。如果您想坚持使用 T 类型的节点，请不要将节点包装在智能指针中。 Node 析构函数必须删除底层的原始指针。原始指针可能指向一个指定为 T 的智能指针本身。当您的 "LinkedList" 的 class 析构函数被调用时，它会遍历具有 Node::next 的所有节点并在之后调用 delete node;它获得了指向下一个节点的指针。

您可以创建一个列表，其中的节点是智能指针...但这是一个非常专业的链表，可能称为 SharedLinkedList 或 UniqueLinkedList，在对象创建、弹出等方面具有非常不同的语义。举个例子，一个 UniqueLinkedList将值弹出给调用者时，会在 return 值中移动一个节点。要针对此问题进行元编程，需要对传递的不同类型的 T 使用偏特化。例如，类似于：

template<class T>
struct LinkedList
{
    Node<T> *head;
};

// The very start of a LinkedList with shared ownership. In all your access
// methods, etc... you will be returning copies of the appropriate pointer, 
// therefore creating another reference to the underlying data.
template<class T>
struct LinkedList<std::shared_ptr<T>>
{
    shared_ptr<Node<T>> head;
};

现在开始实施您自己的 STL！您已经可以看到使用这种方法对问题的评论中提到的潜在问题。如果节点有 shared_ptr next 它将导致调用该共享节点的析构函数，这将调用下一个共享节点的析构函数等等（由于递归可能导致堆栈溢出）。所以这就是我不太喜欢这种方法的原因。

Answer 2

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

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

使用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 指针在两个选项中都只是一个观察指针：它的任务不是保持先前的节点活动，而只是提供一个 link 来访问它们。为此，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 是否仍然有效。

Answer 3

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

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

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

用Herb Sutter的话来说：

Never use owning raw pointers and delete, except in rare cases when implementing your own low-level data structure (and even then keep that well encapsulated inside a class boundary).

Herb Sutter's and Bjarne Stroustrup's C++ Core Guidelines:

中也表达了类似的内容

This problem cannot be solved (at scale) by transforming all owning pointers to unique_ptrs and shared_ptrs, partly because we need/use owning "raw pointers" as well as simple pointers in the implementation of our fundamental resource handles. For example, common vector implementations have one owning pointer and two non-owning pointers.

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

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

Answer 4

结构看起来像

template<typename T> struct Node
{
T data;
shared_ptr<Node<T>> next;
};

节点的创建看起来像

shared_ptr<Node<int>> head(new Node<int>);

或

auto head = make_shared<Node>(Node{ 1,nullptr });

Answer 5

不要在像数据结构这样的图形中使用智能指针，因为它可能会导致堆栈溢出，由于析构函数或 inc 的递归调用，导致许多性能问题，由于 dfs 和 bfs 算法的工作方式，decr 引用计数不是最佳的

C++ 链表使用智能指针

C++ Linked list using smart pointers

c++

templates

pointers

linked-list