Re: [boost] Re: Skip List

From: Beman Dawes (bdawes_at_[hidden])
Date: 2001-11-05 17:01:56

At 02:48 PM 11/5/2001, Michael wrote:
 >--- In boost_at_y..., Beman Dawes <bdawes_at_a...> wrote:
 >>  >http://unlikely.org/mike/outbox/2001/11/04/skip_list.hpp
 >>
 >> > This is a rather naive implementation of the skip list data
 >> > structure.
 >>
 >> Always hard to tell without docs, but it looks like whatever you
 >> implemented is quite a bit different from Bill Pugh's original June,
 >> 1990, CACM description of this data structure.  The node structure
 >> looks way different, or am I just misreading your code?
 >
 >No, it's probably way different.
 >
 >> Do you have a reference to a description of your data structure and
 >> how it differs from Pugh's?
 >
 >I'm sorry, I've never read this and can't find it on ACM or Yahoo.

Hum. There is a PDF copy available from his ftp site: 
ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

Interesting reading.

 >If we picture a skip list thusly:
 >
 >1         9
 >1   4     9
 >1 3 4 5 8 9
 >
 >I can perhaps explain it like so: my goal was to be able to associate
 >data with each instance of 1 in the list.
 >
 >So.  That is probably the source of a great deal of the difference.
 >Or maybe not.  I am guessing.  Anyhow, it's probably not worth either
 >of our time to come to an understanding.  As I said in the last post,
 >upon reflection, it is probably not a broad audience who will find
 >application for this thing.

I agree with Dave Abrahams - don't take our questions as meaning we are 
uninterested.  Quite the opposite.  Skip trees have interesting performance 
trade offs (and some semantic differences) from similar containers, and 
might well have a place on Boost.  I was able to use a C implementation 
very effectively once some years ago.

--Beman