我有很多长链表(它们最多有20000个项目)。它们有不同的起点,但最终可以从某个节点开始指向同一个节点。我决定让这样的链表一起成长,分享他们之间的记忆。
这就是为什么我决定实现带有共享指针的链表:
#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;
我提前感谢以下任何一项:
- shared_pointers和我缺少什么的解释。我该如何使用它们?甚至可以用它们来完成吗?这样的内存共享难道不是共享指针发明的目的吗
- 建议如何重新实现我的代码
- 这段代码将用于科学计算,并将在我的计算机上运行。我能以某种方式调整一些东西以获得更大的堆栈大小吗
请注意,这个问题不是c++11特有的。我不在乎使用共享指针的哪个实现。我甚至实现了自己的共享指针。这使我可以拥有更长的链表,但析构函数和堆栈溢出中的递归也出现了。我看不出在析构函数中如何在没有递归的情况下实现共享指针。
编辑:
为了避免混淆:我想重复一遍,整个列表都可以共享。所以人们可以称它们为树。
以下是示例:
列表1包含:1,2,3,4,5,6,7。
列表2包含:6,6,1,2,3,4,5,6,7
列表3包含:10,11,12,1,2,3,4,5,6,7
我想在3 SharedLinkedList中表示这一点,它不会因为存储1、2、3、4、5、6、7几次而浪费内存,但它们指向同一个地方。这就是为什么需要参考计数。
假定delete list3;
仅删除未共享的部分,即元素10、11、12。
如果您使用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
}
一般来说,shared_ptr
可能不是链接列表,因为你指出的原因。在这种情况下可能必须手动完成,并在每个节点。(也许有可能循环,避免了shared_ptr
的堆栈溢出,但结果可能比管理内存更复杂手动操作。)