From: Andy Glew (glew_at_[hidden])
Date: 1999-10-08 16:39:16
> While we're at it, I'd like to solicit advice as to
> the interfaces for a family of such consistent structures.
> The complexity of reln_1_to_N is that the reverse map is a container.
> It is not clear to me whether that container should itself be a parameter,
> and, if so, how to parametrize it. I.e. it is straightforward to have the reverse
> data structure always be a list, but sometimes you want it to be a map
> sorted on a key, sometimes a hash_map, etc.
> reln_M_to_N is similar. Once we figure out what the proper way to
> represent 1:many relations is - or, more likely, what the proper way
> to handle multiple different desired representations - the rest follows.
Well, at least writing those diatribes last night got me thinking.
What I describe above is the real problem / interface design issue
that has got me blocked.
It is straightforward to implement once you decide what sort of
data structure you will use to go from the 1 to the many. You want
lists? Rings? A FIFO? A priority queue?
The problem is that, at least in my own code where I use such
concepts, I nearly always have some additional data structure
for the "many" that is important to my problem.
For example, in the producer/consumer example (a simplified
real example from a simulator I am working on now) I currently
want the data structure of consumers for any particular producer
to be a FIFO, i.e. sorted by request time.
At other times I want it to be sorted by consumer creation time,
and occasionally I need it to be sorted by consumer time in a
searchable way, as in a map. At other times I have needed only a
priority queue based on some key, since I haven't needed ordered
(And, oh, yeah, I want this selectable at run time, without the overhead
of virtual functions. Good luck, you say? Well, many workers in my field
do things like recompiling a special version of the program for the user
to run; I've played with using CMIX partial evaluation. Static selection
of methods at startup saves a hell of a lot of time compared to virtual
function overhead. But that's another issue.)
Conceptually, what I want is a
TEMPLATE: 1 to N
priority_queue using typename2::prio
map using typename2::key
i.e. I would like to specify at least one, and potentially several,
access paths to the "many"; I would like to be able to iterate over
any of those access paths independently; I would like an erase
using an iterator obtained from any one access path to apply to them all;
I'd like an insert to insert on all access paths; but I would like to have
the ability to rearrange access paths once created, e.g. changing the
priority of an object, changing its LRU status, etc.
It may be that the right thing is to define a template
reln_1_to_many< class T1, class T2, &T1::link1, &T2::link2, template Access_from_1_to_2>
(pardon, I don't have the syntax for passing templates as arguments quite down yet)
which creates the appropriate pallet, and then organizes those pallets as
Somehow, I need to attach the auxiliary info for the access path, such as the key to
be sorted and indexed on.
But, the basic idea would be to pass a single access path from 1 to many;
if you need multiple, you would have to define a consistent combination
of them youself and pass that in.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk