[boost] Re: Bidirectional relation pointers using C++ templates with member pointer parameters

From: Valentin Bonnard (Bonnard.V_at_[hidden])
Date: 1999-09-24 10:49:53

Andy Glew wrote:
> 
> A whole slew of us are creating one-of idiosyncratic solutions.
> This is why I would like to create a generic framework.
> 
> For example, if I understand the docs and code correctly,
> your
>     IntrusiveList<T>
> works fine, so long as an object is on only one list.
> The object has to inherit from ListNode<T>.

This is absolutely correct.

> Trouble is, most interesting data structures have objects
> on multiple lists simultaneously, and want to "cross over"
> from one to the other. 

Actually, I have often been in the "one container-can inherit" 
case before I wrote IntrusiveList.

> Previous solutions have accomplished this using multiple
> inheritance - IMHO polluting the namespace by adding
> intermediate classes for the different types of links an object
> can be on.
>         template<class T> class ListNode1<T> : ListNode<T> {}
                                              ^^^
                                   This is where non virtual 
                                   inheritance is helpfull !

>         template<class T> class ListNode2<T> : ListNode<T> {}
>         struct Data : ListNode1<T>, ListNode2<T> {}
> Now Data can be on multiple lists...

*two* lists. (Or more, but the limitation is fixed at compile 
time.)

One can also try:

std::vector<boost::shared_ptr<T> > v1, v2, v3;
shared_ptr<T> p (new T);
v1.push_back (p);
v2.push_back (p);
v3.push_back (p);

*p is in three vectors !

(Of course, there is no way to get the vector's address from p.)

> I much prefer the pointer to member solution:
>     IntrusiveList<class T, IntrusiveListLinkage T::*linkage>
> Particularly if a default can be used (I haven't tried this).

With the problem that when instanciate it, T must be defined.
If you took a pointer a member at runtime (instead of as a template 
parameter), T should be only defined only at the time the IntrusiveList 
is constructed.

> I'd like to extend this to all STL containers, in the easiest possible
> (least coding) way. Although I recognize that STL containers may
> not be the optimal data structures for this sort of application, they
> are something.

something what ?

(Yes, STL containers aren't optimal for everything. We should 
be able to appreciate them, and at the same time to understand 
their limitations.)

> Valentin Bonnard wrote:
> 
> > > At this time I invite those of you who have in the past expressed
> > > interest in such data structures to contact me, so that we can explore
> > > the space of useful and convenient interfaces.
> >
> > See my IntrusiveList STL container, at:
> >
> > http://www.eleves.ens.fr:8080/home/bonnard/IntrusiveList/
> >
> > Summary: it's basically a std::list, except that each
> > element has a back-link to the list. (So that
> > list.front().get_container() is list.)

-- 
Valentin Bonnard