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