On Aug 8, 2008, at 3:43 AM, Phil Bouchard wrote:
"Gordon Woodhull" <gordon@woodhull.com> wrote in message news:EC4056C7-4D91-4591-A2CC-D909A6340FF6@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++.