这是一个更多的设计问题（我知道为什么会发生这种情况，只是想看看人们如何处理它）。假设我有一个简单的链表 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);
}
}
这似乎在单个线程中工作，但我担心线程安全。
如果您在链接数据结构的销毁时遇到堆栈溢出问题，最简单的解决方法就是实现延迟清理：
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(); 定期。
这应该做到这一点。通过一点点工作，它可以很容易地做到线程安全（在删除引擎中有点锁定/原子）
概要：
使用自定义析构函数创建节点的shared_ptr，而不是删除节点，而是将其移交给删除引擎。
引擎的实现是一个单例。在被通知要删除的新节点时，它将该节点添加到删除队列。如果没有删除节点，则依次删除队列中的节点（无递归）。
发生这种情况时，到达引擎的新节点只会添加到队列的后面。正在进行的删除周期将很快完成。
#include <memory>
#include <deque>
#include <stdexcept>
#include <iostream>
struct node;
struct delete_engine
{
void queue_for_delete(std::unique_ptr<node> p);
struct impl;
static impl& get_impl();
};
struct node
{
node(int d) : data(d) {}
~node() {
std::cout << "deleting node " << data << std::endl;
}
static std::shared_ptr<node> create(int d) {
return { new node(d),
[](node* p) {
auto eng = delete_engine();
eng.queue_for_delete(std::unique_ptr<node>(p));
}};
}
int data;
std::shared_ptr<node> child;
};
struct delete_engine::impl
{
bool _deleting { false };
std::deque<std::unique_ptr<node>> _delete_list;
void queue_for_delete(std::unique_ptr<node> p)
{
_delete_list.push_front(std::move(p));
if (!_deleting)
{
_deleting = true;
while(!_delete_list.empty())
{
_delete_list.pop_back();
}
_deleting = false;
}
}
};
auto delete_engine::get_impl() -> impl&
{
static impl _{};
return _;
}
void delete_engine::queue_for_delete(std::unique_ptr<node> p)
{
get_impl().queue_for_delete(std::move(p));
}
struct tree
{
std::shared_ptr<node> root;
auto add_child(int data)
{
if (root) {
throw std::logic_error("already have a root");
}
auto n = node::create(data);
root = n;
return n;
}
};
int main()
{
tree t;
auto pc = t.add_child(6);
pc = pc->child = node::create(7);
}
std :: shared_ptr（以及之前的boost :: shared_ptr）是构建涉及大规模DAG的动态系统的事实上的标准。
实际上，DAG没有那么深（在你的平均外汇定价服务器中可能有10或12个算法？）所以递归删除不是问题。
如果您正在考虑构建一个深度为10,000的巨大DAG，那么它可能会成为一个问题，但说实话，我认为这将是您最不担心的问题。
DAG的类比就像一个链表......不是真的。因为它是非循环的，所有指向“up”的指针都需要是shared_ptr，并且所有的后指针（例如对sink算法的绑定消息订阅）都需要是weak_ptr，你在触发消息时会锁定它。
免责声明：我花了很多时间设计和构建基于参数化算法组件的有向无环图的信息系统，共享组件的大量共享（即具有相同参数的相同算法）。
图表的性能从来都不是问题。瓶颈是：
最初在程序启动时构建图形 - 有一个 批量 在那一点上的噪音，但它只发生一次。
将数据导入和导出进程（通常是消息总线）。这通常是涉及I / O的瓶颈。