Boost logo

Boost :

From: Andy Glew (glew_at_[hidden])
Date: 1999-10-08 19:59:05


(Sorry to bother y'all again; if this is excessive, tell me, and I'll
shut up; if there is anyone else interested in discussing / designing
such automatically coherent multicontainers, please tell me.
It's sometimes hard to work on something like this in a crowd
of people who think that C is a high level language.)

Anyway, I'm slowly making gedanken-progress:

If I have several different access paths, then "automatic consistency:" means
a) if I insert into one, I insert into all
b) if I delete from one, I delete from all

Actually, I am not 100% sure about this all or nothing bit:
- often a data structure has more than one separate subcomponent,
e.g. an age list, a freelist, and an active list.
But those can be considered internal structure for a larger
consistent object.

Similarly, if I assume that the object has whatever
key an access path is supposed to be sorted on
embedded within it, then
c) a function to extract whatever key information is necessary

And, similarly, a function to notify all access paths that might
need to adjust the position of an object, e.g. when a key change has occurs.

Here's a non-declarative approach:
Define a template class system that wraps virtual functions
around the insert and erase methods of any container:

        template< class Container, class Containee>
        VirtualContainer : AbstractVirtualContainer {
        public:
                virtual void insert( Containee& item ) { this->Container::insert( item ); }
                virtual void erase( Container::iterator& place ) { this->Container::erase( place ); }
                        // actually, probably want to return iterators, like underlying containers do
                        // (although not all STL containers seem consistent)
        }

Unfortunately, slightly different wrappers wil be necessary for keyed containers
such as maps, to perform the extraction

        template< class Container, class Containee, &Containee::key>
        VirtualKeyedContainer : AbstractVirtualContainer {
        public:
                virtual void insert( Containee& item ) { this->Container::insert( pair(item.key,item) ); }
                virtual void erase( Container::iterator& place ) { this->Container::erase( place ); }
                        // actually, probably want to return iterators, like underlying containers do
                        // (although not all STL containers seem consistent)
        }

(Actually, might just define a functor, if no loss in performance.)

Then define the relation, and "register" an object for each access method in a list of
AbstractVirtualContainers. On every insert, call each access path's insert method, etc.

As usual, it probably would be appropriate to provide a pallet with an iterator for each access
path, unless intrusive containers are being used, and provide access to such a pallet
from the access path iterators - i.e. have the access paths not be Container<Containee>,
but Container< pallet<Containee> > (which is inconsistent with the template parameters
up above, sigh.)

As usual^2, I am somewhat unhappy at using virtual functions, although that is the only way
I see to get such data structures built at run time.

The usual^3 trick, of creating templates with 1, 2, 3, 4 .... access path arguments can be used to
simulate the concept of having an arbitrary number of access paths.


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