As someone who spent some significant time in a previous life working on a parallel programming framework that involved lock-free data structures, you've really

As someone who spent some significant time in a previous life working on a parallel programming framework that involved lock-free data structures, you've really hit the nail on the head here. The whole experience totally changed my views on garbage collection, because without GC problems like this can be so painful to solve. The only thing I really have to add is that, while we had to do pretty much what you describe here, I didn't think it felt that bad for the end user in the context of a framework built on top of C++11's features. A combination of RAII and lambdas can allow you to solve (1) and (3) pretty elegantly. (As you say, though, it's not very cleanly composable. This is one of many reasons why we were creating a framework in the first place and not a set of independent libraries.)