c++ - 共享指针递归删除递归数据结构栈溢出

Question

我有许多长链接列表(它们有多达 20,000 个项目)。它们有不同的开始，但它们最终可以从某个节点开始指向同一个节点。我决定让这样的链表一起成长，共享它们之间的内存。

这就是我决定使用共享指针实现链表的原因:

#include <memory>
struct SharedLinkedList {
    int someData;
    std::shared_ptr<SharedLinkedList> next;
};

这样一切正常。不再需要的链表被删除。如果他们与其他链表共享某些部分，则仅删除他们未共享的部分。

当没有共享部分的较长链表即将被删除时，问题就会出现。删除从第一个元素开始。这减少了对下一个元素的引用数量，该元素也可以被删除，并且递归重复直到堆栈溢出。

这是创建长链接列表然后删除它失败的代码示例。

SharedLinkedList* beginningOfList;
SharedLinkedList* actualElement = new SharedLinkedList();
SharedLinkedList* nextElement;

beginningOfList = actualElement;
for (int i = 0; i < 1000; i++) { // 100 is OK, 1000 is KO
    nextElement = new SharedLinkedList();
    actualElement->next = std::shared_ptr<SharedLinkedList>(nextElement);
    actualElement = nextElement;
}
delete beginningOfList;

我提前感谢以下任何一项:

1. 对 shared_pointers 的解释以及我遗漏了什么。我该如何使用它们？甚至可以使用它们来完成吗？发明共享指针的目的不就是共享内存吗？
2. 建议如何重新实现我的代码
3. 此代码将用于将在我的计算机上运行的科学计算。我可以通过某种方式调整一些东西以获得更大的堆栈吗？

请注意，这个问题不是特定于 c++11 的。我不关心使用哪种共享指针实现。我什至实现了自己的共享指针。这让我有更长的链表，但析构函数中的递归和堆栈溢出也出现了。而且我看不出如何在析构函数中不递归地实现共享指针。

编辑:

只是为了避免混淆:我想重复一下，整个列表都可以共享。所以可以称它们为树。

例子如下:

list1 包含:1,2,3,4,5,6,7。

list2 包含:6,6,6,1,2,3,4,5,6,7

list3 包含:10,11,12,1,2,3,4,5,6,7

我想在 3 个 SharedLinkedList 中表示它不会通过多次存储 1,2,3,4,5,6,7 来浪费内存，但它们指向同一个地方。这就是需要引用计数的原因。

delete list3; 应该只删除未共享的部分，即元素 10、11、12。

Answer 1

如果您使用 shared_ptr，它将为您管理所有权。当引用计数变为 0 时，它将调用指针的析构函数。现在指向的对象被破坏，作为它的一个元素，下一个共享指针破坏了下一个 ... 。这导致以递归方式释放内存。现在您可以尝试释放内存迭代。您只需要保留对下一个元素的引用以避免其破坏并在以后手动删除它:

void destroy(SharedLinkedList* l) {
  auto next=l->next;  // take 2nd element 
  delete l;           // delete first

  while (next)
    next=next->next;  // move next forward, deleting old next 
  }