C++中使用智能指针实现的循环双向链表

Question

在C ++中使用智能指针创建循环双向链表是否可能？

struct Node {
  int val;
  shared_ptr<Node> next;
  weak_ptr prev;
};

shared_ptr<Node> head;

但是这将会有一个共享指针的循环引用，因此无法正确地释放内存。

- innocent_bystander

---

你正在使用弱指针，所以没问题，但要注意共享指针可能会慢。 - imreal

但请记住这是一个循环链表。最后一个节点的下一个指针指向第一个节点，而第一个节点（通过传递）将指向最后一个节点。 - innocent_bystander

Answer 1

将循环链表作为一个类（包括构建所需的任何操作，如附加）进行处理。在其析构函数中，通过设置tail->next = nullptr来断开链接。断开哪个链接并不重要，因此如果您没有使用头和尾，则只需将任何一个设为nullptr即可。在我的测试中，我创建了一个循环链表，但节点没有被销毁。然后在结束时，我添加了tail->next = nullptr，然后所有析构函数正确地触发了。

- Kenny Ostrom

---

在构造函数或节点添加代码中，您必须手动设置生成循环的shared_ptr，而不是通过分配来设置它，以便对称性要求，在析构函数中，您必须手动重置它以销毁循环。 - Aiken Drum

@AikenDrum 如果你需要实现一个析构函数，那么三五定律就适用了。为了编写更简单、更健壮的代码，最好遵循零五定律。 - jxh

@jxh 没有构造函数是不可能创建循环列表的。如果没有构造函数，.add()必须有条件地创建额外的链接。这只是延迟构造。调用者间接地在第一次add()上触发构造。从技术上讲，为了对称，调用者需要调用.remove()/.reset()，这将销毁链接。然而，他们不想这样做，所以我们会在析构函数中为他们完成。“零/三法则”并不是真正的规则，也不是选择一个而不是另一个。简单、健壮的代码来自常识和实用主义，而不是某个人想出来的“规则”。 - Aiken Drum

@jxh更不用说，我相当确定在这个数据结构上无法使用默认的拷贝构造函数，所以零规则也无从谈起了。 - Aiken Drum

Answer 2

我的原始回答缺乏细节。这个回答会给出一个适当的解释，说明如何实现循环链表而不会出现内存泄漏，并且仍然遵守零规则。答案基本上相同，使用一个哨兵，但机制比我最初想象的更加复杂。

关键是使用一个哨兵类型，它的行为就像一个列表节点，但实际上并没有真正共享指向列表头的指针。为了实现这一点，节点类应该分成一个行为对象和一个状态对象。

class NodeState {
    std::shared_ptr<Node> next_;
    std::weak_ptr<Node> prev_;
    int value_;
    NodeState (int v) : value_(v) {}
    NodeState (std::shared_ptr<Node> p) : next_(p), prev_(p) {}
    //...
};

class Node {
    virtual ~Node () = default;
    virtual NodeState & state () = 0;
    std::shared_ptr<Node> & next () { return state().next_; }
    std::weak_ptr<Node> & prev () { return state().prev_; }
    int & value () { return state().value_; }
    void insert (const std::shared_ptr<Node> &p) {
        //...
    }
};

现在，您可以定义一个节点实现和哨兵实现。

class NodeImplementation : public Node {
    NodeState state_;
    NodeState & state () { return state_; }
    NodeImplementation (int v) : state_(v) {}
    //...
};

class NodeSentinel : public Node {
    List &list_;
    NodeSentinel (List &l) : list_(l) {}
    NodeState & state () { return list_.sentinel_state_; }
};

该列表本身包含一个由哨兵对象使用的NodeState。在初始化时，列表创建一个哨兵对象并初始化其状态。

class List {
    //...
    NodeState sentinel_state_;
    std::shared_ptr<Node> head () { return sentinel_state_.next_; }
    std::shared_ptr<Node> sentinel () {
        return std::shared_ptr<Node>(head()->prev());
    }
    //...
public:
    List () : sentinel_state_(std::make_shared<NodeSentinel>(*this)) {}
    //...
    void push_front (int value) {
        head()->insert(std::make_shared<NodeImplementation>(value));
    }
    void push_back (int value) {
        sentinel()->insert(std::make_shared<NodeImplementation>(value));
    }
    //...
};

那么，这个组织做什么？它通过使用哨兵节点作为断点来避免循环引用的问题。虽然列表的尾部指向哨兵对象，但哨兵对象本身不指向任何东西。相反，它使用列表本身的状态来确定其下一个和前一个邻居。

因此，只有在列表存在时，循环共享指针才能持续存在。一旦列表被销毁，Item A 就会失去它的引用，通过多米诺效应，Sentinel 本身也将被销毁。

一个基本点是，哨兵对象本身绝不能直接暴露给列表接口的用户。它应始终保持为列表对象的内部。它本质上代表 STL 类型容器中的 end()，逻辑上，它永远无法从列表中移除（直到列表本身被销毁）。实际上，这意味着对列表的删除操作需要在传入的迭代器表示哨兵时提前退出。 演示

尝试在线

- jxh

Answer 3

还可以定义一个成员函数next()，它可以在共享指针和弱指针之间进行选择。

#include <iostream>
#include <memory>
using namespace std;

struct T {
    int n_;
    shared_ptr<T> next_;
    weak_ptr<T> weaknext_;
    T(shared_ptr<T> next, int n) : next_(next), n_(n) {};
    auto next() {
         if (next_ == nullptr)
             return shared_ptr<T>(weaknext_);
         return next_;
    }
    ~T() { cout << n_ << "ok\n"; }
};
int main() {
    auto p0 = make_shared<T>(nullptr, 1);
    auto p1 = make_shared<T>(p0, 2);
    auto p2 = make_shared<T>(p1, 3);
    p0->weaknext_ = p2;  //makes the list circular
    auto p = p2;
    for (int i = 0; i < 5; ++i) {
        cout << p->n_ << "\n";
        p = p->next();
    }
}

- vollitwr