Clojure solves this particularly elegantly by using persistent data structures. This works really well if you've got automatic garbage collection, but is almost impossible to pull off when managing memory manually. Java has some decent concurrent/atomic data structures.
I've written implementations of lock-free data structures in C++ before, and in the end it's always the memory management that complicates everything immensely because you have to watch out for dangling references and need to make up arbitrary, hard-to-enforce access rules as a consequence.
As far as I'm concerned, this is the biggest nail in the coffin of C++. Not the insanely complex syntax, not the compiler niggles, but, ironically, the inability to scale and perform well in a concurrent environment - and C++ has been the domain of those wanting the highest possible speed in serial code. And memory management is one of the arguments that's often been used in C/C++'s favour and is now actually killing it.
I'm generally against any complex lock-free data structures, because they're extremely difficult to prove to be reliable (and I mean prove in ACL2 sense of proof).
Have you tried any of the garbage collection libraries for C++? I've never used them for any of my projects, but I currently work in the mobile industry and they would potentially solve two problems. One being the concurrency issue, but then also memory fragmentation. (Windows Mobile 6 allows 32 MB of memory max per process, so this is a big one for mobile)
I know they can cause a lot of cache misses, but it seems like all but the most primitive of low end devices would run into a problem with it in most situations at this point.
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.
I've written implementations of lock-free data structures in C++ before, and in the end it's always the memory management that complicates everything immensely because you have to watch out for dangling references and need to make up arbitrary, hard-to-enforce access rules as a consequence.
As far as I'm concerned, this is the biggest nail in the coffin of C++. Not the insanely complex syntax, not the compiler niggles, but, ironically, the inability to scale and perform well in a concurrent environment - and C++ has been the domain of those wanting the highest possible speed in serial code. And memory management is one of the arguments that's often been used in C/C++'s favour and is now actually killing it.