Hi everyone!

I recently read about such an interesting data structure as skip-list. It seemed to me, the structure is very interesting and at the same time easy to use. That is the reason I decided to experiment with the structure in various problems and try to implement the various modifications of it. "Basic" operations are well described in this entry from wikipedia. So I will not give them too much time.

Basic implementation.

Here is "pure" variant of skip-list — implemented only the basic operations — find, insert, erase.

code

Adding order statistics functions.

Now we need to add two new functions find_by_order() and order_of_key(). In order to do this, in balanced binary trees we used to store the size of subtrees. But here we just should store the length of links. After this both functions can be implemented easy enough. In first function we change binary predicate and comparing not elements themselves, but length of the prefixes they are ending in. In the second function we do everything just like in usual find(), but we also store the length of prefix that lead to current element.

code

Make the structure use implicit key.

When we added find_by_order() we also got an opportunity to make skip-list use implicit key, i.e. key=order of element in set. Everything we need in order to use it is using find_by_order() instead of find().

code

P.S. What do you think about this data structure? How wise is it to use skip-lists on the contests? What other modifications do you know? Also, my implementation is pretty weak, do you know the better one?