RE: [boost] Re: Skip List

From: Beman Dawes (bdawes_at_[hidden])
Date: 2001-11-05 20:24:34

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.

--Beman