C ++ garbage collection and circular-referenced data

Question

I am currently implementing a garbage collector (in C ++) using the reference counting method. However, the big problem is that if the data is cyclically referenced, it is never collected, since their reference counts are always non-zero.

I tried searching and found these things called trash garbage collector, marking and sweep algorithm, etc. Is it possible to implement it? And how exactly do they work?

Answer 1

This is a classic garbage collector design problem. Take a look at the article , it is really good at presenting various trade-offs in the design of the garbage collector. The more advanced algorithms, such as tri-color marking, are actually quite simple and easy to implement. I used these instructions to implement a trace collector for my own Lisp implementation in C.

The most difficult thing to handle when tracing garbage collectors is the trees of running objects (for example, finding links to "live" objects). If you write a translator for another language, this is not so difficult, because you can connect the means to this in your class of root objects (or another common denominator for all objects). However, if you write a garbage collector for C ++ in C ++, it will be difficult for you to do this because you need to check the contents of the object to find pointers to other allocated memory areas.

If you are writing a garbage collector for educational purposes, I recommend that you study translating the interpreter into another language (one that does not have direct access to pointers). If you are writing a collector for C ++ in C ++ in order to use it in production software, I strongly recommend that you use the existing implementation of production quality .

Answer 2

http://www.boost.org/doc/libs/1_48_0/libs/smart_ptr/weak_ptr.htm

The weak_ptr class template stores a weak link to an object that is already managed by shared_ptr. To access the object, weak_ptr can be converted to shared_ptr using the shared_ptr constructor or blocking a member function. When the last shared_ptr object leaves, and the object is deleted, try to get shared_ptr from weak_ptr instances that reference the remote object will fail: the constructor will throw an exception like boost :: bad_weak_ptr, and weak_ptr :: lock will return an empty shared_ptr ".

You should not really have circular links, but if you work with a design where you cannot reorganize it (which sometimes happens), try placing weak pointers in one direction so that they do not prevent destruction.