共享指针递归删除数据结构时可能会导致堆栈溢出。

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无关。我不在乎使用哪种shared pointers的实现方式。我甚至已经实现了自己的共享指针。这允许我拥有稍长的链接列表，但析构函数中的递归和堆栈溢出也出现了。我不知道共享指针如何在没有析构函数递归的情况下实现。

编辑：

只是为了避免混淆：我想重申，整个列表可以共享。因此，可以称它们为树。

以下是示例： 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。

- John Bumper

---

据我所知，问题在于您的SharedLinkedList析构函数的实现。它显然调用了第一个项的析构函数，然后递归地调用下一个项的析构函数，以此类推。您应该很容易地改变SharedLinkedList析构函数的实现方式，使其不使用递归函数调用（例如，使用while循环遍历列表中的元素）。 - jogojapan

为什么不使用标准的std::list(或std::vector)和std::shared_ptr？ - Some programmer dude

@jogojapan，看起来SharedLinkList使用了编译器生成的析构函数。你不能真正添加一个迭代所有剩余列表的析构函数；整个重点是节点被引用计数。 - jamesdlin

@jamesdlin 好的，你需要将列表的实现与列表项的实现分开。然后你就可以避免递归了。（我的理解是引用计数是必要的，因为同一项可能被多个列表持有，而不是因为它们本身促进了列表的实现。如果只是这样的话，unique-ptr 就足够了。） - jogojapan

@jogojapan 我不确定你是否理解我分享的内容。请查看我所做的编辑。 - John Bumper

Answer 1

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

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 
  }

- Jan Herrmann

---

删除l;会减少底层共享指针中的引用计数，并且会触发递归。 - John Bumper

@JohnBumper 不是，首先会创建next的副本。因此第二个元素的引用计数至少为2. 当删除“l”时，它变成1。想法是在丢失第一个元素之前，复制对第二个元素的shared_ptr。这样，在删除第一个元素时不会删除第二个元素。 - Jan Herrmann

你是对的。我简直不敢相信这么短的代码真的能够工作。但它确实可以工作。就像一个奇迹一样。特别是 next=next->next; 这一行，一开始看起来很奇怪，但它确实可以删除东西。我只需要特别小心，不要在共享部分中迭代，以节省时间。将你的代码移动到析构函数中也很棘手，因为 next=next->next 这一行也会调用析构函数。但我设法做到了，它运行得快速、无缺陷，并且不会导致堆栈溢出。祝贺你的天才和感谢你的帮助。 - John Bumper

在 next=next->next 之后添加 if(next.use_count() > 1) break;。这将大大加快速度，将潜在的指数删除时间加速为节点数量的线性时间。 - ithenoob

@ithenoob，你能解释一下如何得出可能指数级的删除时间吗？添加 if (next.use_count ()> 1) break; 将导致潜在的竞争条件。即使测试通过，其他所有者在 destroy 析构 next 之前可能已经释放了对象。 - Marc

@Marc，我是通过比现在少5年的经验才发现这个问题的:P。我曾经错误地认为destroy是析构函数，或者是要在每个SharedLinkedList实例上调用的函数，而不是每个“head”。实际上，这只会导致最坏情况下二次时间复杂度。我相信shared_ptr的“共享状态”是线程安全的（维护引用计数的逻辑+状态），因此只有在启动了糟糕的递归删除行为时才会出现竞争条件。当时没有考虑到线程。我的评论应该被删除。 - ithenoob

Answer 2

通常情况下，在链表中，shared_ptr 可能不是一个好的选择，因为你指出了其中的原因。在这种情况下，你可能需要手动操作，每个节点都需要维护一个父级计数器。(也许可以通过一些循环方式避免使用 shared_ptr 导致堆栈溢出的问题，但结果可能比手动管理内存更加复杂。)

- James Kanze