Skip List

From: Michael (f-boost_at_[hidden])
Date: 2001-11-04 21:46:45

Regarding:
http://unlikely.org/mike/2001/11/04/skip_list.hpp

This is a rather naive implementation of the skip list data structure.
 The skip_list::iterator interface is questionable.  Each entry in the
skip list is accessible (ie, if the value four is in six lists, all
six values are accessible through the iterator interface).  Each value
is distinct.  Were this not true, skip_list would be nothing other
than a weird implementation of the simple associative container
concept.

I wrote this container for a specific purpose (authentication
dictionaries[1]) and I'm not sure what use it has outside of that
domain, but I thought that I'd let you all take a look at it.

A summary of usage might go like this:

struct foo
{
    int rank;
    int note;
    foo (int r, int n) : rank (r), note (n) { }
    foo () : rank (0), note (0) { }
    bool operator< (const foo &f) const
    {
        return rank < f.rank;
    }
};

skip_list<foo> l;

l.insert (foo (5, 1));
skip_list<foo>::iterator it = l.find (foo (5, 7));
assert (it != l.end ());
skip_list<foo>::iterator it2 = it;
it2.up ();
// this assertion might be false (it's arbitrary) but let's
// assume that it's going to be true...
assert (it2.valid ());
const_cast<foo&> (*it2).note = 3;
assert (it->note == 1);
assert (it2->note == 3);

So... That's the jist.  Probably no use to anyone, eh?

[1] http://www.cs.jhu.edu/~goodrich/cgc/pubs/discex2001.pdf