[adrianratnapala]

In most of the graph problems I have ever dealt with, the graph is constructed piecemeal but destroyed as a whole after you are finished with it.

It is true there are specific problems (e.g git repos) where you want a mutable graph over the long term -- but I have never actually had to deal with those cases, unless it was a special case with a obvious solution (like a doubly-linked list or tree).

[nanolith]

Even in the case of a mutable graph, one can use copy-on-write semantics to create a DAG of graph revisions that can be managed or compacted. I believe this was the strategy used by Subversion.

Compaction and collection can both be trivially performed on such a structure by making a deep copy of the latest revision of the graph to a new memory arena, just as is commonly done with a Cheney collector. Old locations are back-patched with pointers to the new locations, which solves the cycle problem.

[gpderetta]

hey, that's a generational GC :)

[nanolith]

Well, it's a Cheney GC. To be generational, there would need to be more than two heaps. But, that's hair splitting. Heh.

I doubt one would find many C++ folks who would disagree that GC is useful some of the time. It's all about controlling when and where GC is used, which sort of hits home with Sutter's point.