Shared pointers recursively delete recursive data structures and stack overflows

Question

I have several long linked lists (they have up to 20,000 items). They have different beginnings, but they may end up pointing to the same node from some node onwards. I decided to let this linked list grow together and share memory between them.

This is why I decided to implement a linked list with shared pointers:

#include <memory> struct SharedLinkedList { int someData; std::shared_ptr<SharedLinkedList> next; }; 

Thus, everything is working fine. Linked lists that are no longer needed are deleted. If they share some part with another linked list, only their non-shared part is deleted.

The problem arises when longer linked lists without shared parts are deleted. Deletion starts from the first item. This reduces the number of links to the next element, which can also be deleted, and it repeats recursively until the stack overflows.

Here is an example of code that creates a long linked list and then does not delete 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 you in advance for one of the following:

• Explanation of shared_pointers and what I am missing. How can i use them? And can this be done with their help? Wasn't that memory sharing what sharing pointers were invented for?
• recommendations for redefining my code
• This code will be used for scientific calculations to be performed on my computer. Can I somehow customize to have a larger stack size?

Note that this question is not specific to C ++ 11. I don’t care what kind of common points implementation is used. I even implemented my own generic pointers. This allowed me to have several longer linked lists, but there was also recursion in destructors and stack overflows. And I don’t see how common pointers without recursion in destructors could be used.

EDIT:

Just to the anomalies of aviod: I want to repeat that all lists can be shared. Thus, you can call them trees.

Here is an example:

list1 contains: 1,2,3,4,5,6,7.

list2 contains: 6,6,6,1,2,3,4,5,6,7

list3 contains: 10,11,12,1,2,3,4,5,6,7

I want to represent this in 3 SharedLinkedList, which do not lose memory, saving 1,2,3,4,5,6,7 several times, but they point to the same place. This is why reference counting is required.

delete list3; should remove only the part that is not shared, i.e. elements 10, 11, 12.

Answer 1

If you use shared_ptr , it will manage your property. When the reference count is 0, it will call the pointer destructor. Now the pointer to the object is destroyed as well as an element of its next common pointer, which destroys the next .... This leads to a recursive way to free memory. Now you can try to free iterative memory. You only need to save the link to the next element in order 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 } 

Answer 2

In general, shared_ptr is probably not a good idea for linked lists, for the reason that you specify. In this case, you probably have to do this manually, maintaining a parent account in each node. (It may be possible to work out some that avoids using shared_ptr , but the results are likely to be more complex than managing memory by hand.)