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.

 All Classes Files Functions Variables Typedefs