[Design] Interface of SkipList

[rapiz1]

SkipList / SkipListMap

Red-Black Tree alternative.

I'm also proposing a kind of Map built on SkipList.

Used in many popular projects like LevelDB, Reddis, Bigtable

vs Red-Black Tree

SkipList	Red-Black Tree
Larger constant factor, but fast in practice
Easy to implement	Very difficut to implement
Could be lock-free	Need a lock
With expected time complexity, not stable	With upper bound complexity

And Skip List will on expectation use less space than all balanced trees.

In practice, it's fairly fast

So between Skip List and Treap, it's a time-space trade off ( though SkipList sometimes is actually faster )

Interface

• eltType
• record comparator
• size
• insert(x: eltType): insert an element.
• contains(x: eltType): bool: return if x is in the list
• lower_bound(x: eltType, out result: eltType): bool same as std::lower_bound(), return false if no occurence.
• upper_bound(x: eltType, out result: eltType): bool same as std::upper_bound(), return false if no occurence.
• remove(x: eltType): bool: remove x in the list. Does nothing if not present
• these(): iterate over the list
• kth(idx: int): return k-th element in the sorted sequence, throw an error if out of range
• toArray: convert to an array
• clear()
• predecessor(x: eltType, out result: eltType): bool return the predecessor of one element, return false if it's the first one.
• successor(x: eltType, out result: eltType): bool return the successor of one element, return false if it's the last one.

SkipListMap same as Map but with SkipList as the underlying structure

[e-kayrakli]

Issues somewhat related to your questions:

#15394
#14423

[cassella]

Why are lower_bound() and upper_bound() here?

[rapiz1]

Why are lower_bound() and upper_bound() here?

SkipList has all the functionality of a search tree. Or think it as a sorted array. lower_bound and upper_bound are useful for searching elements closest to the target.

[rapiz1]

Closed by #15921