Feature Matrix

List	Sequence	Forward Container	Reversible Container	Reversible Container LOGN	Random Access Container LOGN	Arbitrary Access Container LOGN	Front Insertion Sequence	Back Insertion Sequence	Back Insertion Sequence LOGN	Front Access Container	Back Access Container	Back Access Container LOGN	Simple Associative Container	Pair Associative Container	Unique Sorted Associative Container	Multiple Sorted Associative Container
SkipList
SSkipList
KeyedSkipList
KeyedSSkipList
AutoSkipList
AutoSSkipList
AutoKeyedSkipList
AutoKeyedSSkipList
MultiSkipList
MultiSSkipList
MultiKeyedSkipList
MultiKeyedSSkipList
MultiAutoSkipList
MultiAutoSSkipList
MultiAutoKeyedSkipList
MultiAutoKeyedSSkipList
IndexedSkipList
IndexedSSkipList
IndexedTinySkipList
set
map
multiset
multimap
vector					O(1)
list

Algorithmic Complexity Matrix

O(1)

O(logn)

O(n)

O(nlogn)

List	insert	erase(iter)	search key	insert index	erase index	search index	++iter	--iter	iter+n	iter-n
SkipList
SSkipList
KeyedSkipList
KeyedSSkipList
AutoSkipList
AutoSSkipList
AutoKeyedSkipList
AutoKeyedSSkipList
MultiSkipList
MultiSSkipList
MultiKeyedSkipList
MultiKeyedSSkipList
MultiAutoSkipList
MultiAutoSSkipList
MultiAutoKeyedSkipList
MultiAutoKeyedSSkipList
IndexedSkipList
IndexedSSkipList
IndexedTinySkipList
set
map
multiset
multimap
vector
list

Functionality Matrix

This is a rough indication of the functionality available in the different skiplists. For example, if both set and vector are properties of a container (AutoSkipList), insertion will be based on the key value, not on the index. However, random access will be available (usually in logn time). It is a guide to get a rough idea of the functionality without the implications of algorithmic complexity. Nothing more.

List	Double[1]	Single[2]	set	map	multiset	multimap	vector
SkipList
SSkipList
KeyedSkipList
KeyedSSkipList
AutoSkipList
AutoSSkipList
AutoKeyedSkipList
AutoKeyedSSkipList
MultiSkipList
MultiSSkipList
MultiKeyedSkipList
MultiKeyedSSkipList
MultiAutoSkipList
MultiAutoSSkipList
MultiAutoKeyedSkipList
MultiAutoKeyedSSkipList
IndexedSkipList
IndexedSSkipList
IndexedTinySkipList

[1] Double Linked List.

[2] Single Linked List.