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

From: Gordon Woodhull (gordon_at_[hidden])
Date: 2008-08-09 00:26:33

On Aug 8, 2008, at 3:43 AM, Phil Bouchard wrote:
> "Gordon Woodhull" <gordon_at_[hidden]> wrote in message
> news:EC4056C7-4D91-4591-A2CC-D909A6340FF6_at_woodhull.com...
>
>> I think we are working on complementary problems having to do with   
>> better
>> ways to manage systems of objects that point to each other.  In  the
>> metagraph library, I am working with fusion and intrusive to build   
>> up
>> objects that are e.g. nodes in graphs and also items in lists and   
>> also
>> nodes in trees, all at the same time.  Really the "is also" is  what
>> intrusive allows and I'm trying to describe these systems better   
>> using
>> metagraph patterns, which are metadata graphs describing object   
>> types
>> ("roles") and the other types they point to or contain   
>> ("relations").
>
> Intrusive node pointers cannot be owners of the object referred to.

True, Boost.Intrusive doesn't address ownership (except for the  
simplest case).  Usually a container doesn't own objects, and erase  
just wipes the internal pointers.  It is assumed that something else  
controls lifetime.

I think that the principles of ownership and the lifetime management  
system you are proposing could probably be applied to systems of  
intrusive containers, more quickly than a change to the c++ standard  
(perhaps via the metagraph library I'm working on ;).

> If we
> include all the necessary node pointers according to the number of
> containers pointing to the node itself then we could take advantage  
> of all
> the container properties combined at the same time:
>
> struct node : list_node, map_node, vector_node
> [...]

This looks to me like a refactoring of what Boost.Intrusive does,  
except for the ownership/lifetime management functionality, and of  
course there is no such thing as an intrusive vector!  To achieve the  
same effect (I think) as your code with Boost.Intrusive, one would put  
the properly annotated (in a similar way) objects into a std::vector  
and then insert them (which just updates internal pointers) into the  
intrusive "containers".  Of course, now the vector owns them, which  
might not be what is wanted.

Still, I think that any ownership pattern could be imposed on  
Intrusive somehow.  Your design may be more elegant, we'll see...  :-)

> Here the vector will have to support index fragmentation if we start
> inserting objects between consecutive ones:
> (l.begin() ++ ++)->insert('h');
>
By "index fragmentation," do you mean std::vector should remap indices  
to accommodate any changes?  That sounds really neat, but does that  
logic really belong there and not in some other class with different  
performance guarantees?

> I am already adapting the current Gcc Libstdc++ containers to  
> support smart
> pointers.  All the details related to explicit node access haven't  
> been
> discussed yet but any contributions to this are welcome.

I'm pretty dedicated to solutions that don't involve changing the  
standard, so I'll look into how your ownership model fits in with  
intrusive containers.

But at the same time I am really eager to see your redesign - it is  
such a dramatically different approach, and STL could surely be  
generalized better.

It sounds like you are solving some of the same multi-index problems  
as Boost.Intrusive, but also some other interesting problems:
1. opening up the internal structure of sets and lists and allowing it  
to be shared.
2. super-efficient lifetime management.

Honestly, I don't see how the structure really can be shared and  
preserve the invariants of both containers, but I would love to be  
proved wrong and it would surely be amazing and useful if it worked.   
This objection has nothing to do with shifted_ptr "extrusions" vs  
intrusive methods, just with the problems of two objects mucking about  
with the same data.

But just about everything else I heard "can't be done in C++" over the  
years, has been done.

Looking forward to learning more,
Gordon

IMO it's time for more things that can *only* be done in C++.