Re: [boost] [shifted_ptr] STL support: 99%

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  
> 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