[boost] Re: Two way maps/multimaps

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.