Re: Skip List

From: Erdei Andras (ccg_at_[hidden])
Date: 2001-11-06 06:13:02

Michael wrote:

> I'm sorry, I've never read this and can't find it on ACM or Yahoo.

you can find the some articles at http://www.cs.umd.edu/~pugh/ 
[the homepage of the original skip list author]
and a lot more around http://citeseer.nj.nec.com/messeguer97skip.html

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 ?

customizable memory complexity, additional functionality
(like utilizing the locality of searches), and (at least in theory)
greater speed -- i'm toying around with my own skip list
implementation, but so far i'm stuck speed-wise. it is supposed
to be faster than the red-black tree set in my STL, but right
now the debug skip list is about 10 times faster than the
debug red-black tree, while the release (optimized) version
is slightly faster for insert and delete, but about 10% slower for
search... most likely i'm not too good at writing fast code :O)
also, there is a bug either in my test suite or in the M$ STL,
because stl::set does some random memory overwrites for some
of the test data

br,
andras