共享指针递归删除递归数据结构，堆栈溢出 [英] Shared pointers delete recursive data structures recursively and the stack overflows
问题描述
我有一些长链接列表（他们有多达20,000个项目）。他们有不同的起点，但他们最终可以指向从某个节点向前的同一个节点。我已经决定让这样的链表一起成长，共享它们之间的内存。
I have a number of long linked lists (they have up to 20,000 items). They have different beginnings but they can eventually point to the same node from some node onwards. I've decided to let such linked list to grow together and share the memory between them.
这就是为什么我决定用共享指针实现链表：
That is why I ve decided to implement linked list with shared pointers:
#include <memory>
struct SharedLinkedList {
int someData;
std::shared_ptr<SharedLinkedList> next;
};
这种方式一切正常。删除不再需要的链接列表。如果他们与其他链接列表共享某些部分，则只有其未共享部分被删除。
This way everything works fine. The linked lists which are no longer needed are deleted. If they share some part with other linked list only their un-shared part is deleted.
当没有共享部分的更长的链接列表即将被删除时，问题出现。删除从第一个元素开始。这减少了对下一个可以被删除的元素的引用次数，并且这会重复递归直到堆栈溢出。
The problem apears when longer linked lists without shared parts are about to be deleted. Deleting starts with the first element. This decreases the number of references to the next element which can be also deleted and this repeats recursively until the stack overflows.
下面是创建长链表的代码示例然后失败删除它。
Here is the example of code which creates long linked list and then fails deleting it.
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;
我预先感谢以下任一者：
I thank in advance for either of the following:
- shared_pointers和我缺少的内容的说明。如何使用它们？甚至可以使用它们吗？
- 建议如何重新实现我的代码
- 这个代码将被使用对于将在我的计算机上运行的科学计算。我可以以某种方式调整以获得更大的堆栈大小吗？
请注意，这个问题不是c ++ 11具体的。我不在乎使用共享点的哪个实现。我甚至实现了我自己的共享指针。这使我有一个更长的链表，但在析构函数和堆栈溢出的递归也出现了。我没有看到任何方式如何可以共享指针实现没有递归的析构函数。
Note that this question is not c++11 specific. I don't care which implementation of shared pointes is used. I even implemented my own shared pointers. This allowed me to have a little longer linked lists but the recursion in destructors and stack overflowing also appeared. And I don't see any way how could be shared pointers implemented without recursion in destructors.
编辑：
只是为了aviod混乱：我想重复，整个列表可以共享。
Just to aviod confusions: I want to repeat that the whole lists can be shared. So one could call them trees.
这里是一个例子：
list1包含：1,2,3 ，4,5,6,7。
list1 contains: 1,2,3,4,5,6,7.
list2包含：6,6,6,1,2,3,4,5,6,7
list2 contains: 6,6,6,1,2,3,4,5,6,7
list3包含：10,11,12,1,2,3,4,5,6,7
list3 contains: 10,11,12,1,2,3,4,5,6,7
我想要在3 SharedLinkedList中表示它，它不会通过存储1,2,3,4,5,6,7几次而浪费单词，但是它们指向同一个地方。
I want to represent this in 3 SharedLinkedList which do not waste momory by storing 1,2,3,4,5,6,7 several times but they point to the same place. That is why reference counting is needed.
删除list3; 应该只删除不共享的部分即元素10,11,12。
delete list3; is supposed to delete only the part which is not shared i.e. elements 10,11,12.
推荐答案
如果使用 shared_ptr 它将管理您的所有权。当引用计数变为0时，它将调用委托的析构函数。现在指向对象被破坏，作为它的一个元素的下一个共享指针，破坏下一个...。这导致解除分配内存的递归方式。现在你可以尝试解除内存迭代的分配。您只需要保留对下一个元素的引用，以避免其被销毁，并在以后手动删除它：
If you use shared_ptr it will manage ownership for you. When reference count goes to 0 it will call the destructor of the pointee. Now the pointed to object gets destructed and as an element of it the next shared pointer which destructs the next ... . This results in a recursive way of deallocating memory. Now you could try to deallocate the memory iterative. You only have to keep a reference to next element to avoid its destruction and delete it manually later:
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
}
这篇关于共享指针递归删除递归数据结构，堆栈溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
