RE: [boost] Re: Skip List

From: Duane Murphy (duanemurphy_at_[hidden])
Date: 2001-11-05 20:59:09

--- At Mon, 5 Nov 2001 20:24:34 -0500, Beman Dawes wrote:

>At 04:54 PM 11/5/2001, Sofus Mortensen wrote:
>
> >I wonder what skip list's will bring us that we don't already have with
> >either set/multiset or map/multimap ?
> >
> >Am I correct in thinking that skip list's is nothing but an (randomized)
> >alternative to the usual red-black tree implementation of STL set/map?
>
>A skip list can be tuned to deliver good speed at quite a bit less storage 
>cost. An skip list average of as low as 1.2 pointers per node can still 
>perform quite well.  At least in theory, the speed of insertion can also be 
>faster than a red-black tree, IIRC.  So a skip list with a lot of 
>insertions, but only a few lookups, might perform quite a bit better than a 
>red-black tree.  OTOH, deletes may be expensive, although I'm not 100% sure 
>of that.
>
>It would take some testing to see if the differences were at all 
>significant. Note that the original skip list only supported forward 
>iterators.

That's partially because the skip list is optimized for lookup and not
necessarily for iteration. I imagine iterating over a skip list would be
similar to iterating over a hash table; its not really meant to work that way.

..Duane