8

我有许多长链表（它们最多有 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。

4

2 回答 2

8

如果您使用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 
  }
于 2013-07-23T08:17:41.880 回答
6

一般来说，由于您指出的原因，对于链表shared_ptr来说可能不是一个好主意。在这种情况下，您可能必须手动完成，在每个节点中维护一个父计数。（可能可以使用 来解决某种避免堆栈溢出的循环shared_ptr，但结果可能比手动管理内存更复杂。）

于 2013-07-23T08:03:44.163 回答