c++ - 嵌套的 shared_ptr 破坏导致堆栈溢出

Question

这更像是一个设计问题(我知道为什么会这样，只是想看看人们如何处理它)。假设我有一个简单的链表 struct:

struct List {
    int head;
    std::shared_ptr<List> tail;
};

shared_ptr 允许在多个列表之间共享子列表。但是，当列表变得很长时，其析构函数中可能会发生堆栈溢出(由 shared_ptrs 的递归释放引起)。我尝试过使用显式堆栈，但这变得非常棘手，因为一个尾部可以由多个列表拥有。如何设计我的 List 来避免这个问题？

更新:澄清一下，我不是在重新发明轮子(std::forward_list)。上面的List只是真实数据结构的简化版。真正的数据结构是一个有向无环图，如果你想它只是很多具有共享尾部/头部的链表。复制图通常非常昂贵，因此数据共享是必要的。

更新 2: 我正在考虑显式遍历指针链和 std::move。比如:

~List()
{
    auto p = std::move(tail);
    while (p->tail != nullptr && p->tail.use_count() == 1) {
        // Some other thread may start pointing to `p->tail`
        // and increases its use count before the next line
        p = std::move(p->tail);
    }
}

这似乎在单个线程中工作，但我担心线程安全。

Answer 1

如果您在销毁链接数据结构时遇到堆栈溢出问题，最简单的解决方法就是实现延迟清理:

struct Graph {
    std::shared_ptr<Graph>  p1, p2, p3;   // some pointers in your datastructure
    static std::list<std::shared_ptr<Graph>>   deferred_cleanup;

    ~Graph() {
        deferred_cleanup.emplace_back(std::move(p1));
        deferred_cleanup.emplace_back(std::move(p2));
        deferred_cleanup.emplace_back(std::move(p3));
    }
    static void cleanup() {
        while (!deferred_cleanup.empty()) {
            std::list<std::shared_ptr<Graph>>  tmp;
            std::swap(tmp, deferred_cleanup);
            tmp.clear(); } }
};

您只需要记住定期调用 Graph::cleanup();。