> The problem with shared_ptr is the fact that it uses atomics even in single-threaded code, which is obviously an overkill.

On the other hand imagine the security issues if shared_ptr was not thread-safe - you could just not reliably destroy a shared_ptr in any thread.

If you really know that you're going to get a graph of shared_ptr that do not move of a single thread, you can use boost::local_shared_ptr explicitely.