RE: [boost] Re: Skip List

From: Sofus Mortensen (list_at_[hidden])
Date: 2001-11-06 01:37:24

A skip list still have the functionality and average case (not worst
case) asymptotical performance as red-black trees. Actually I think
there is quite a few different structures with the same average case as
red-black trees, possibly all with their (minor) size/speed advantages
and disadvantages. For every new structure we would probably get X_map,
X_set, X_multimap and X_multiset.

Instead I think it would be better to design an extension to (multi)map
and (multi)set, that takes an extra template argument either specifying
the implementation or some type/value specifying the wanted
size/speed/insertion/lookup/deletion tradeoff.

I don't think the normal C++ user is interesting in knowing what a skip
list is, or even that such a thing exists, but he might be interested in
boosting his map performance a little if possible.

Best regards,

Sofus Mortensen

Comet - Grunge free COM programming in C++
http://www.lambdasoft.dk/comet 

> -----Original Message-----
> From: Beman Dawes [mailto:bdawes_at_[hidden]] 
> Sent: Tuesday, November 06, 2001 2:25 AM
> To: boost_at_[hidden]; boost_at_[hidden]
> Subject: RE: [boost] Re: Skip List
> 
> 
> 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 
> of that.
> 
> It would take some testing to see if the differences were at all 
> significant. Note that the original skip list only supported forward 
> iterators.
> 
> --Beman
> 
> 
> Info: http://www.boost.org  Unsubscribe: 
> <mailto:boost-unsubscribe_at_[hidden]> 
> 
> Your use of 
> Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 
> 
> 
>