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
It would take some testing to see if the differences were at all
significant. Note that the original skip list only supported forward
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk