From: Gordon Woodhull (gordon_at_[hidden])
Date: 2008-08-05 23:40:59
> In my case I am mostly interested into pure smart pointers and
> shared_ptr can easily be used using the modifications I am
> proposing. We
> could for example partly mix congruent lists without worrying about
> irreversable mess it could create. But a map controled partly by
> map sharing nodes is something I am mostly interested in because you
> 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk