Boost logo

Boost :

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
time ago.)

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, gregod at, cpdaniel at, john at