Boost logo

Boost :

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
[the homepage of the original skip list author]
and a lot more around

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


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