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.