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.