Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk