Re: [boost] additions

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.

--Beman