Boost logo

Boost :

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:
>> >
>> > 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:

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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at