RE: [boost] 'stable' priority queue

From: Geurt Vos (G.Vos_at_[hidden])
Date: 2001-04-17 09:13:20

> >> This problem seems to come up so now and then
> >> at several places. For what I know, also boost
> >> doesn't provide a stable one (right?).
> > 
> > 
> > - Add a time stamp to the element and make it part of the priority key:
> >   If the priority is identical, compare the time stamp. This is the way
> >   to go and a viable approach with all priority queues I have provided.
> >   It desired, it should be reasonably simple to create a wrapper which
> >   aides in doing so.
> 
> I recently considered using this approach but rejected it
> as completely not viable.
> Just think, we can not use precision of one second for timestamps
> (i.e. time() function), because it is very much possible that several
> events happen in one second and with this approach they will have
> the same timestamp. On the other hand, we can not use higher
> precision (i.e. clock() function) because of overflow problems
> (our applications can run for a very long time unattended, but
> millisecond-precision timers will overflow in about 49 days).
> 
> So timestamp is not an option for reliable queue.
> 

The question is: what's a timestamp? 

To name two, which might do the trick:

- You could have a simple counter, which is incremented every time
an element is inserted. It'll overflow in 2^32 operations, which
is probably enough.

- CPU specific timestamp: the Pentium and newer come with a 64-bit
timestamp counter, which is incremented every clock cycle. So when
you take, say, a 2Ghz CPU, it overflows in 292 years (didn't take
leap years into account :)

There's always a timestamp that is suitable, which implies it
should be configurable.

Geurt