Re: Sequence container with fast random access and fast insertion/removal (wherever)
Martin Knoblauch Revuelta wrote:
Le Chaud Lapin wrote:
Your avl_array implements a
priority set where the priorities are necessarily the natural numbers.
Not as general of parameterizing the type of the priority (timestamp
for example),
I was thinking about this. What if I don't enforce natural numbers?
Then you will have a prioritized set, where the priority is
parameterized. This is very useful data structure. Many times in
coding, a priority_queue seems to be what is needed. It is discovered
later that what is really needed priority_set. For example, Dijkstra's
algorithm, contrary to what many computers science books say, cannot be
in implemented using a priority_queue in the STLL flavor. My book hand
waves on this issue. It says quickly, "Oh, by the way, Dijkstra's
algorithm requires the ability to modify priorities after insertion,
but the priority queue does not support it, but with a little work it
could." ;)
Maybe a lot of new things can be done with just two unsigned ints more,
even without parametrizing it... The most difficult thing here is
designing a good interface.
Yes, the more you suffer, the happier someone else will be using it.
but this would still be useful, say, to represent people
registered to receive free XBOX's. The order is important, but you do
not want the same person to appear twice in the registration list.
I don't see the point. Do you mean a queue in which you insert not only
at the end, but by priority position too? Sounds interesting. It would
be a good experiment.
I thought that your 'position' element was being used to keep track of
order of insertion, and not simply for fast linear iteration. If so,
then the data structure would model a first-come-first-serve situation
where each participant is not allowed to be in line more than once (at
a time).
-Le Chaud Lapin-
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]