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

From: Andy Glew (glew_at_[hidden])
Date: 1999-09-24 11:51:51

> [...multicontainers...]
> > Previous solutions have accomplished this using multiple
> > inheritance
>
> *two* lists. (Or more, but the limitation is fixed at compile
> time.)

Yep. I suppose that you could extend things to have a list
of back pointers, but in my work the overall shape of the data
structures is known at compile time.

E.g. I may have a 2-dimsional list - an X and a Y list.
Or, I may have a number of map<key1,pallet>, map<key2,pallet>
and a time ordered lru_list<pallet>, I may use
any access path to find a payload, and then I will want to
remove that payload object from all of the indexes all at
the same time. I use backpointers to avoid researching
the other map<>s.

I'm basically saying that, yes, number limited at compile time
is a limitation, but it is one that I am happy to live with.

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

And that's the problem.

"Multicontainers" nearly always involve using one
access path, and then another - e.g. searching v1,
finding an element, and then having to remove that
element from v2.

> > 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 know, this is a real pain. It considerably reduces the compile time
safety checks that can be done.

If I could say

        class c {
            bidirectional_ptr<c,c,&c::next,&c:;prev>::left next;
            bidirectional_ptr<c,c,&c::next,&c:;prev>::left next;
            ...
        };

life would be much better.

The multiple inheritance solution is better in this regard:

    class c;
    class cnext;
    class cprev;

    class cnext : bidirectional_ptr<c,c,cnext,cprev>::left;
    class cprev : bidirectional_ptr<c,c,cnext,cprev>::right;

    class c : cnext, cprev {
        // access cptr->cnext::ptr or cptr->cprev::ptr
    }

I just gag, though, at the namespace pollution this implies.
To avoid that namespace pollution I had started wrapping every such
class definition in its own namespace, and then hoisting out just
the multicontainer object class.