From: Beman Dawes (bdawes_at_[hidden])
Date: 2001-08-30 14:19:40
At 07:47 AM 8/29/2001, Erdei Andras wrote:
>Also, is anyone interested in the following:
>- a skip list (same as map<>, but only expected log time,
> but with a smaller constant)
Do you have a skip list design which supports bidirectional
iterators? It's OK if it doesn't, but it isn't "same as map<>" if it just
supports forward iterators. (Dave Abrahams pointed this out to me some
Does your design allow specification of p (or p reciprocal)? Seems like
one of the major advantages of a skip list is the ability to tune memory
use via p.
By the way, I once tracked down skip list performance problems which turned
out to be caused by a poor implementation of std::rand(). Be sure to use a
quality RNG, like one of the Boost ones.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk