SkipList Library: SkipList<class T, class Pr = std::less<T>, class R = RNG>

Category: containers
Component type: type

Description

A SkipList is a Simple Associative Container, meaning that its value type, as well as its key type, is T.
It is a Unique Sorted Associative Container, meaning that no two elements are the same.
It is a Associative Container LOGN, meaning that erasing of a single element is logarithmic.
It is a Destructive Associative Container LOGN, meaning that destroying (delete folowed by erase) single element or a range of elements is done in logarithmic time.
It is both a Front Access Container and a Back Access Container meaning that the front and back of the list are available for retrieval, erasure and destruction in constant time.

The Unique Sorted Associative Container and Multiple Sorted Associative Container requirements guarantee that inserting a range takes only linear time if the range is already sorted. Unfortunately, this has not been implemented yet and performs in the default nlogn time.

A SkipList has the important property that inserting a new element into a SkipList does not invalidate iterators that point to existing elements. Erasing an element from a SkipList also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

A SkipList acts like a set in functionality though the performance requirements are different in a few places.

A SkipList uses a Bidirectional Iterator that is also LessThan Comparable. See SkipList::T0 for more info.

Definition

Defined in the custom header "CSSkipList.h".

Template parameters

Parameter	Description	Default
`T`	The `SkipList`'s key type and value type. This is also defined as `SkipList::key_type` and `SkipList::value_type`. `SkipList::mapped_type` is also defined to this value for convenience.
`Pr`	The key comparison function, a Strict Weak Ordering whose argument type is `key_type`; it returns `true` if its first argument is less than its second argument, and `false` otherwise. This is also defined as `SkipList::key_compare` and `SkipList::value_compare`.	`less<T>`
`R`	The `SkipList`'s random number generator, used for selection of levels per node.	RNG

Model of

Simple Associative Container, Unique Sorted Associative Container, Associative Container LOGN, Destructive Associative Container LOGN, Front Access Container and Back Access Container

Type requirements

T is Assignable.
Pr is a Strict Weak Ordering whose argument type is T.
R is an RNG (is Default Constructible and supports rand() and drand()).

Public base classes

None.

Members

Member	Where defined	Performance	Description
`value_type`	Container		The type of object, T, stored in the `SkipList`.
`key_type`	Associative Container LOGN		The key type, T, associated with value_type.
`key_compare`	Sorted Associative Container		Function object that compares two keys for ordering.
`value_compare`	Sorted Associative Container		Function object that compares two values for ordering.
`container_type`	`SkipList`		Type of this container
`pointer`	Container		Pointer to `T`.
`reference`	Container		Reference to `T`
`const_reference`	Container		Const reference to `T`
`mapped_type`	Simple Associative Container		A type identical to `value_type` and `T`
`mapped_type_reference`	Simple Associative Container		A type identical to `reference`
`const_mapped_type`	Simple Associative Container		A type identical to `const value_type`
`const_mapped_type_reference`	Simple Associative Container		A type identical to `const reference`
`size_type`	Container		An unsigned integral type.
`difference_type`	Container		A signed integral type.
`iterator`	Container		Iterator used to iterate through the container's elements. [1]
`const_iterator`	Container		Const iterator used to iterate through the container's elements.
`reverse_iterator`	Reversible Container		Iterator used to iterate backwards through the container's elements. [1]
`const_reverse_iterator`	Reversible Container		Const iterator used to iterate backwards through the container's elements.
`slpair`	`SkipList`		std::pair< iterator, bool >
`iterator begin()`	Container	O(1)	Returns an `iterator` pointing to the beginning of the container.
`iterator end()`	Container	O(1)	Returns an `iterator` pointing to the end of the container.
`const_iterator begin() const`	Container	O(1)	Returns a `const_iterator` pointing to the beginning of the container.
`const_iterator end() const`	Container	O(1)	Returns a `const_iterator` pointing to the end of the container.
`reverse_iterator rbegin()`	Reversible Container	O(1)	Returns a `reverse_iterator` pointing to the beginning of the reversed container.
`reverse_iterator rend()`	Reversible Container	O(1)	Returns a `reverse_iterator` pointing to the end of the reversed container.
`const_reverse_iterator rbegin() const`	Reversible Container	O(1)	Returns a `const_reverse_iterator` pointing to the beginning of the reversed container.
`const_reverse_iterator rend() const`	Reversible Container	O(1)	Returns a `const_reverse_iterator` pointing to the end of the reversed container.
`size_type size() const`	Container	O(1)	Returns the size of the container.
`size_type max_size() const`	Container	O(1)	Returns the largest possible size of the container.
`bool empty() const`	Container	O(1)	`true` if the container's size is `0`.
`key_compare key_comp() const`	Sorted Associative Container	O(1)	Returns the `key_compare` object used by the container.
`value_compare value_comp() const`	Sorted Associative Container	O(1)	Returns the `value_compare` object used by the container.
`SkipList()`	Container	O(1)	Creates an empty container. Default probability of 25% and 8 levels.
`SkipList(size_type maxNodes)`	`SkipList`	O(1)	Creates an empty container. Default probability of 25%. Maximum levels based on maxNodes.
`SkipList(double probability, size_type maxLevel)`	`SkipList`	O(1)	Create an empty container with the specified probability and maximum levels.
`SkipList(const container_type &source)`	Container	O(n*logn)	Copy constructor. Copies all elements along with probability and maximum levels.
`template<class InIt > SkipList(InIt first, InIt last)`	Unique Sorted Associative Container	O(n*logn)	Creates a container with a copy of the range. Probability is 25% and maximum levels is 8.
`template<class InIt > SkipList(InIt first, InIt last, double probability, size_type maxLevel)`	Unique Sorted Associative Container w/ probability	O(n*logn)	Creates a container with the specified probability and maximum levels along with a copy of the range.
`template<class InIt > SkipList(InIt first, InIt last, size_type maxNodes)`	Unique Sorted Associative Container w/ probability	O(n*logn)	Creates a container with a copy of the range. Default probability of 25%. Maximum levels based on maxNodes.
`SkipList(const key_compare &comp)`	Sorted Associative Container	O(1)	Creates an empty container, using `comp` as the `key_compare` object.
`template<class InIt > SkipList(InIt first, InIt last, const key_compare &comp)`	Unique Sorted Associative Container	O(n*logn)	Creates a container with a copy of a range, using comp as the key_compare object.
`template<class InIt > SkipList(InIt first, InIt last, const key_compare &comp, double probability, size_type maxLevel)`	Unique Sorted Associative Container /w probability	O(n*logn)	Creates a container with a copy of a range, using comp as the key_compare object. Container is created with specified probability and maximum level.
`template<class InIt > SkipList(InIt first, InIt last, const key_compare &comp, size_type maxNodes)`	Unique Sorted Associative Container /w probability	O(n*logn)	Creates a container with a copy of a range, using comp as the key_compare object. Default probability of 25%. Maximum levels based on maxNodes.
`~SkipList()`	Container	O(n)	Destructor. Clears list.
`container_type& operator=(const container_type &source)`	Container	O(n)	The assignment operator
`void swap(container_type &right)`	Container	O(1)	Swaps the contents of two containers.
`template<class InIt > void assign(InIt first, InIt last)`	SkipList	O(n*logn)	Clears all elements and copies range into container.
`std::pair< iterator, bool > insert(const value_type &val)`	Unique Associative Container	O(logn)	Inserts `val` into the container.
`iterator insert(const iterator &where, const value_type &val)`	Unique Sorted Associative Container	O(logn)	DO NOT USE THIS!!! Inserts `val` into the container, using `where` as a hint to where it will be inserted.
`template<class InIt > void insert(InIt first, InIt last)`	Unique Sorted Associative Container	O(n*logn)	Inserts a range into the container. Should be fixed to support O(n) when range is sorted.
`iterator erase(const iterator &where)`	Associative Container LOGN	O(logn)	Erases the element pointed to by `where`.
`iterator destroy(const iterator &where)`	Destructive Associative Container LOGN	O(logn)	Erases and deletes the element pointed to by `where`.
`size_type erase(const key_type &keyval)`	Associative Container LOGN	O(logn)	Erases the element whose key is `keyval`.
`size_type destroy(const key_type &keyval)`	Destructive Associative Container LOGN	O(logn)	Erases and deletes the element whose key is `keyval`.
`iterator erase(const iterator &first, const iterator &last)`	Associative Container LOGN	O(n)	Erases all elements in a range.
`iterator destroy(const iterator &first, const iterator &last)`	Destructive Associative Container LOGN	O(n)	Erases and deletes all elements in a range.
`void clear()`	Associative Container LOGN	O(n)	Erases all of the elements.
`void destroy()`	Destructive Associative Container LOGN	O(n)	Erases and deletes all of the elements.
`template<class Pr1 > void erase_if (Pr1 pred)`	SkipList	O(n)	Erases all elements where pred(*where) is true.
`template<class Pr4 > void destroy_if (Pr4 pred)`	SkipList	O(n)	Destroys all elements where pred(*where) is true.
`void cut(const iterator &first, const iterator &last, container_type &right)`	SkipList	O(logn)	Extract nodes in the specified range [first,last) into right.
`reference front()`	Front Access Container	O(1)	Returns the first element.
`const_reference front() const`	Front Access Container	O(1)	Returns the first element.
`reference back()`	Back Access Container	O(1)	Returns the last element.
`const_reference back() const`	Back Access Container	O(1)	Returns the last element.
`void pop_front()`	Front Access Container	O(1C/logn)	Removes the first element.
`void destroy_front()`	Front Access Container	O(1C/logn)	Removes and deletes the first pointer element.
`void pop_back()`	Back Access Container	O(1C/logn)	Removes the last element.
`void destroy_back()`	Back Access Container	O(1C/logn)	Removes and deletes the last pointer element.
`iterator find(const key_type &keyval)`	Associative Container LOGN	O(logn)	Finds an element whose key is `keyval`.
`const_iterator find(const key_type &keyval) const`	Associative Container LOGN	O(logn)	Finds an element whose key is `keyval`.
`size_type count(const key_type &keyval) const`	Unique Associative Container	O(logn)	Counts the number of elements whose key is `keyval` (0 or 1).
`iterator lower_bound(const key_type &keyval)`	Sorted Associative Container	O(logn)	Finds the first element whose key is not less than `keyval`.
`const_iterator lower_bound(const key_type &keyval) const`	Sorted Associative Container	O(logn)	Finds the first element whose key is not less than `keyval`.
`iterator upper_bound(const key_type &keyval)`	Sorted Associative Container	O(logn)	Finds the first element whose key greater than `keyval`.
`const_iterator upper_bound(const key_type &keyval) const`	Sorted Associative Container	O(logn)	Finds the first element whose key greater than `keyval`.
`std::pair< iterator, iterator > equal_range(const key_type &keyval)`	Sorted Associative Container	O(logn)	Finds a range containing all elements whose key is `keyval`.
`std::pair< const_iterator, const_iterator > equal_range(const key_type &keyval) const`	Sorted Associative Container	O(logn)	Finds a range containing all elements whose key is `keyval`.
`bool operator==(const container&, const container&)`	Forward Container	O(n)	Tests two maps for equality. This is a global function, not a member function.
`bool operator<(const container&, const container&)`	Forward Container	O(n)	Lexicographical comparison. This is a global function, not a member function.

Notes

[1] SkipList::iterator is not a mutable iterator, because SkipList::value_type is not Assignable. That is, if i is of type SkipList::iterator and p is of type SkipList::value_type, then *i = p is not a valid expression. However, SkipList::iterator isn't a constant iterator either, because it can be used to modify the object that it points to for members that aren't used as part of the key. Using the same notation as above, i->member = p is a valid expression, but care must be taken to retain all original values related to the key in order to keep the list sorted. The same point applies to SkipList::reverse_iterator.

SkipList<class T, class Pr = std::less<T>, class R = RNG>