Welcome to the CS::SkipList Template Library site for C++.

A SkipList is a multi-level linked list that allows for logn runtime complexity for most random access operations. There are a total of 20 different containers available with different functionality and performance guarantees.

While some skiplists simply replicate set, map, multiset, multimap and vector (with logn performance), the real advantage comes from the other skiplists that combine the random access functionality of a vector (in logn time) with the functionality of one of the other sorted containers. In short, you get a set, map, multiset and multimap that are numerically indexable in logn time.

• There are single linked skiplists (SSkipList) or doubly linked skiplists.
• There are sorted skiplists where a separate key is used (Keyed), like a map, and where the object is the key, like a set.
• There are skiplists where keys must be unique and where multiple identical keys can be inserted (Multi).
• There are skiplists that are automatically and numerically indexable (Auto) while others are not.

That makes a total of 16 skiplists built by adding the correct prefixes. For example, a keyed, single linked skiplist that supports multiple identical keys and is automatically indexable is called a MultiAutoKeyedSSkipList.

Multi-Auto-Keyed-S-SkipList

The first four prefixes can be used or omitted depending on your requiremnents. All containers end in SkipList. A SkipList without any prefixes acts like set.

There are three more skiplists that are indexable, but not sorted. These act much like a vector, but works in logn time for most random access operations. There is a double linked list version (IndexedSkipList) as well as a single linked version (IndexedSSkipList). There is also an extra single linked version called IndexedTinySkipList where the memory footprint is even smaller.

The last container is a multilist where you can have the same elements sorted or arranged in many different ways. There are three more internal containers available that lets the user create their own aggregate container. These are similar, but more limited than their regular verions. They are called XMultiSkipList, XMultiAutoSkipList and XIndexedSkipList.

Here are some of the features of the CS::SkipList library.

• Can be used for free or commercial use.
• Supports all OS and all C++ compilers with STL.
• Supports 20 different skiplist containers for all your needs.
• Is a generic template library and works well with STL.
• In fact, most methods are identical to existing STL containers.
• The primary advantage is having sorted lists that also allow random access in logn time.
• Extreme amount of documentation.

Webmaster: Cléo Saulnier