嵌套的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();定期打电话.

Answer 2

std::shared_ptr（以及在此之前的 boost::shared_ptr）现在和过去都是构建涉及大规模 DAG 的动态系统的事实上的标准。

事实上，DAG 并没有那么深入（在您的平均外汇定价服务器中可能有 10 或 12 个算法？），因此递归删除不是问题。

如果您正在考虑构建一个深度为 10,000 的巨大 DAG，那么这可能会成为一个问题，但说实话，我认为这将是您最不担心的问题。

DAG 就像一个链表的类比……其实不然。因为它是非循环的，所以所有指向“向上”的指针都需要是shared_ptr，而所有后向指针（例如，将消息订阅绑定到接收器算法）都需要是weak_ptr，在触发消息时将其锁定。

免责声明：我花了很多时间设计和构建基于参数化算法组件的有向无环图的信息系统，并共享大量通用组件（即具有相同参数的相同算法）。

图表的性能从来都不是问题。瓶颈是：

1. 程序启动时最初构建图表 -此时有很多噪音，但只发生一次。

2. 将数据传入和传出进程（通常是消息总线）。这始终是瓶颈，因为它涉及 I/O。