Indeed, lock-free data structures can be a massive pain to implement. Clojure solves this problem, quite elegantly in my opinion, by making the data structures

Indeed, lock-free data structures can be a massive pain to implement. Clojure solves this problem, quite elegantly in my opinion, by making the data structures themselves immutable, any operations yield a new instance of the data structure (with shared substructure of course). You can then update references to the data structure with the new data structure; in Clojure the idiomatic way to do this is using STM transactions, but you could do it with atomic updates or locks in any other language. Presumably, this won't scale especially well with many writers, at least not for trees and hash tables. I surveyed the GC-on-C++ situation a couple of years ago, and nothing was realistically that useful for concurrent applications. Definitely nothing anywhere near as sophisticated as, say, the JVM's garbage collector.