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