This is an implementation of William Pugh's skip lists as an associative container with unique keys. At the lowest level, it is a doubly linked list to allow bidirectional iterators, but at higher levels it is only singly linked as they are used for searching only.

The operator << has been overloaded to print the skip lists as is shown here:

Size:     75
Height:   6
Total:    1008
Average:  13.44
5-----------------------------------------------------------|-----------------> 0
4------------------|----------------------------------------|----|------------> 0
3------------|-----|----------------------------------------|----|-|---|------> 0
2-------|---||--|--|-|-------------|--|-----------|-|-------|----|-|---|------> 0
1-----|-|--|||--||-||||-------||--||--|--|---|-||||-|---|---|----|||-|-|-|--|-> 0
0-***************************************************************************-> 0

Size:     75
Height:   5
Total:    965
Average:  12.8667
4-----------------------------------------|-----------------------------------> 0
3----||------------|----------------------|---------------------------------|-> 0
2----||-|--||----|-|-----|-----|----|--|--|----------------|---||-----------|-> 0
1---|||-||-||----|-||----|---|-|--|-|--|--||-|------|-|--|-|-|-||---||--|---|-> 0
0-***************************************************************************-> 0

These are two randomly generated skip lists created by the source test.cpp. The values total and average indicate the total and average number of comparisons necessary to find entries in the skip list. Surprisingly, it is very economical: on the same order as a binary search and not significantly worse, as is shown in Figure 1.

Figure 1. Average number of comparisons for successful searches in a binary search (blue) and the best-fitting curve using skip lists.

The output of a larger example with approximately 1000 nodes is shown here.

Here is the class description:

Skip List
class Skip_list<K, Type>

Accessors

bool empty() const

Returns true if the skip list is empty. (Θ(1))

int size() const

The size function returns the number of objects stored within the skip list. (Θ(1))

int count( K const &key ) const

The count function returns the number of instances of key—either 0 or 1. (Θ(ln(n))

Type operator[]( K const &key ) const

Returns a copy of the entry associated with key returning Type() if the key is not stored in the skip list. (O(ln(n)))

int total_search() const
double average_search() const
bool validate() const

These three functions are used to investigate the structure and run times. The first returns the total number of nodes which must be inspected to required each of the keys in the skip list; the second divides this result by the number of objects in the skip list; and the third ensures that the skip list structure is internally consistent. (O(n ln(n)))

Mutators

Type &operator[]( K const &key )

Returns a reference to the entry associated with key within the skip list. (O(ln(n)))

void clear() const

The clear function removes all objects from the skip list. (Θ(n))

Iterator Functions

iterator begin()

Returns an iterator referring to the first entry in the skip list. (Θ(1))

iterator end()

Returns an iterator referring to one-past-the-last entry in the skip list. (Θ(1))

iterator find( K const &key )

If key is in the skip list, it returns an iterator which references that entry; otherwise, it returns end(). (O(ln(n)))

Pair
class Skip_list<K, Type>::pair

The class pair has two public member variables: first, a constant reference to the key; and second, a reference to the associated value.

Iterator
class Skip_list<K, Type>::iterator

The iterator class stores a reference to a node within the skip list and access to ordered pairs of (key, value).

iterator &operator++()
++itr

Set the reference to the next node (if any) and return a reference to this iterator. (Θ(1))

iterator &operator++( int )
itr++

Set the reference to the next node (if any) but return an iterator referring to the original node. (Θ(1))

iterator &operator--()
--itr

Set the reference to the previous node (if any) and return a reference to this iterator. (Θ(1))

iterator &operator--( int )
itr--

Set the reference to the previous node (if any) but return an iterator referring to the original node. (Θ(1))

iterator &operator*()
*itr

Return a pair consisting of a constant reference to the key and a reference to the value of the referred node. (Θ(1))

bool operator==( iterator const &rhs )

Return true if the two iterators are referring to the same node and false otherwise. (Θ(1))

bool operator!=( iterator const &rhs )

Return true if the two iterators are referring to different nodes and false otherwise. (Θ(1))