Slow recursive destructor call in C ++
source link: https://www.codesd.com/item/slow-recursive-destructor-call-in-c.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Slow recursive destructor call in C ++
I am using C++ do represent large graphs using reference counted objects. Something like:
// Public class
class Pointer{
public:
// Constructors
Pointer(...){ node = ...; node->counter++;}
// Copy constructor
Pointer(Pointer& const other){ node = other.node; node->counter++;}
// Destructor
~Point(){ if(--node->counter==0) delete node;}
// Other methods
...
Node* node;
};
// Node base class
class Node{
// Constructor
Node():counter(0){}
// Destructor
virtual ~Node(){}
// public:
unsigned long counter;
};
// Node derived class
class NodeDerived : public Node{
// Constructors and other methods
...
// Destructor
virtual ~NodeDerived(){ ... }
// Children
Pointer children[2];
};
There is thus a public class Pointer
which contains a pointer to a polymorphic class Node. Some classes derived from Node will contain new Pointer
instances. Note that several Pointer
instances may point to the same Node
instance.
I use this class to build up very large graphs with millions of instances, and this works fine. The problem comes when the graph is to be deleted. With the default destructor implementation this results in a stack overflow, since in the destructor of the root node, the destructors of the children are called and in the children's destructors, the destructors of the children of the children are called and so on.
I solved this by implementing a destructor for the NodeDerived
class above that avoids the recursive call by using a stack instead. This works, but is still very slow, and I am looking for a way to speed this up. Is it possible to somehow avoid declaring the destructor virtual
without causing a memory leak?
If you are dealing with millions of objects and stack overflows during destruction, then what you may want to look into is storing pointers to all your node objects in some type of container that doesn't allow duplicate values and supports iteration, like a std::set
or std::unordered_set
. Then in the graph nodes themselves, only store pointers to the connected graph nodes. At the time of deletion for the graph, don't recurse through each graph node's pointers in order to delete nodes ... instead, simply go to the container containing pointers to the set of nodes in the entire graph, and iterate through the container, destroying each node one-by-one. No recursion will be necessary since you won't need to "follow" each graph-node's set of pointers to destroy all the nodes the graph node is connected to. You also won't need to worry about the space and time overhead of a std::shared_ptr
.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK