共享指针以递归方式删除递归数据结构,并且堆栈溢出

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_poin的解释以及我缺少的内容.我该如何使用它们？它甚至可以使用它们吗？是不是这样的内存共享是分享指针发明的东西？
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 
  }

Answer 2

一般来说,链接列表shared_ptr可能不是一个好主意,因为你指出了这一点.在这种情况下,您可能需要手动完成,在每个节点中维护父计数.(可能有可能找出某种循环,避免堆栈溢出shared_ptr,但结果可能比手动管理内存更复杂.)