圆形双链表与c ++中的智能指针

Question

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

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

shared_ptr<Node> head;

但是这将有一个共享指针的循环引用，因此不能正确解除分配。

Answer 1

使循环链表本身成为一个类（使用构建它所需的任何操作，如append）。让它的析构函数通过设置tail-> next = nullptr来打破链接。你打破哪个链接并不重要，所以如果你没有使用头部和尾部，只需将其中任何一个设置为nullptr，就可以了。

在我的测试中，我制作了一个循环链表，节点没有破坏。然后在结束时，我在退出之前添加了tail-> next = nullptr，并且所有析构函数都正确地触发了。

Answer 2

我原来发布的答案很清楚细节。这个给出了一个正确的解释，说明如何在没有内存泄漏的情况下实现循环链​​表，并且仍然遵守Zero规则。答案基本上是相同的，使用哨兵，但机制比我最初的让步更多。

诀窍是使用行为类似于列表节点的sentinel类型，但实际上并没有真正具有指向列表头部的共享指针。为此，应将节点类分为行为对象和状态对象。

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) {
        //...
    }
};

现在，您可以定义节点实现和Sentinel实现。

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_; }
};

列表本身包含sentinel对象使用的NodeState。初始化后，列表会创建一个sentinel对象并初始化其状态。

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));
    }
    //...
};

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

因此，只要列表存在，循环共享指针只会持续存在。一旦列表被摧毁，Item A失去了它的参考，并且通过多米诺骨牌效应，Sentinel本身将被摧毁。

一个基本点是，必须永远不要将sentinel对象本身直接暴露给列表接口的用户。它应始终保持在列表对象的内部。它基本上代表了STL类似容器中的end()，从逻辑上讲，它永远不会从列表中删除（直到列表本身被销毁）。实际上，这意味着如果传入的迭代器代表sentinel，则列表上的删除操作需要提前退出。

Demo

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();
    }
}