Boost logo

Boost :

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

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