In my case I am mostly interested into pure smart pointers and hopefully shared_ptr can easily be used using the modifications I am proposing. We could for example partly mix congruent lists without worrying about the irreversable mess it could create. But a map controled partly by another map sharing nodes is something I am mostly interested in because you can access the same nodes but using "shortcuts" or different roots...
That's neat and I would like to see an implementation - I think you would end up with something like the Furnas/Zacks "multitrees" - quoting from their paper, the multitree "has the unusual property that although it is not a tree, the descendents of any node form a tree... Multi-trees are DAGs, not trees, and as a result a node in the structure can have multiple parents... Not only does the set of descendents of any node form a tree, the set of its ancestors also form an inverted tree." But to get there wouldn't you need to change the public interface of set/map? Right now it won't even admit it's holding a tree. Wouldn't you have to teach it how to reuse nodes rather than creating new ones? I also think there might be overlap issues between an inserted tree and its new siblings. For list, you *might* be able to keep the same interface, but the invariants would be much stranger if one list could modify another. In sum, I'm very interested in these data structures, I just wonder if they might be better served by new classes rather than modifications to STL. Your original application in garbage collection seems valid to me, although I am no allocator expert. Cheers, Gordon