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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk