SkipList Library: IndexedSkipList<class T, class R = RNG>

Category: containers
Component type: type

Description

An IndexedSkipList acts like a vector in functionality though the performance requirements are different in a few places. An IndexedSkipList is a Sequence that supports random access to elements in logarithmic time, constant time insertion and removal of elements at the beginning and end, and logarithmic time insertion and removal of elements in the middle.

An IndexedSkipList uses a Random Access Iterator LOGN. See IndexedSkipList::T0 for more info.

An IndexedSkipList is a Random Access Container LOGN, meaning that an element may be numerically indexed in logarithmic time. Erase and Destroy may also be done by numerical index 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.
It is both a Front Insertion Sequence and a Back Insertion Sequence meaning that the front and back of the list are available for insertion in constant time.

IndexedSkipList iterators have an additional property that contains the index of the element. Erasing or inserting an element that comes after an existing iterator will have that iterator remain valid. All other iterators will have some functionality that will no longer work until the iterator is revalidated by invoking refresh(). refresh() may be called at any point in the future as long as the element pointed to by the iterator continues to exist in the container.

Here are operations that are always valid on IndexedSkipList iterators.

All Equality Comparable comparisons.
Post and pre-increment.
Post and pre-decrement.
Dereferencing.

All other operations require refresh() including all operations via the container requiring an iterator. It is recommended to not rely on the above list of functionality and simply invoke refresh() on existing iterators after inserting or deleting an element. Only Equality Comparable comparisons and dereferencing are guaranteed to be compatible with future versions.

Definition

Defined in the custom header "CSIndexedSkipList.h".

Template parameters

Parameter	Description	Default
`T`	The `IndexedSkipList`'s value type. `IndexedSkipList::mapped_type` is also defined to this value for convenience.
`R`	The `IndexedSkipList`'s random number generator, used for selection of levels per node.	RNG

Model of

Random Access Container LOGN, Front Insertion Sequence, Back Insertion Sequence, Front Access Container and Back Access Container

Type requirements

T is Assignable.
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 `IndexedSkipList`.
`container_type`	IndexedSkipList		Type of this container
`pointer`	Container		Pointer to `T`.
`reference`	Container		Reference to `T`
`const_reference`	Container		Const reference to `T`
`mapped_type`	IndexedSkipList		A type identical to `value_type` and `T`
`mapped_type_reference`	IndexedSkipList		A type identical to `reference`
`const_mapped_type`	IndexedSkipList		A type identical to `const value_type`
`const_mapped_type_reference`	IndexedSkipList		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.
`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`.
`IndexedSkipList()`	Container	O(1)	Creates an empty container. Default probability of 25% and 8 levels.
`IndexedSkipList(double probability, size_type maxLevel)`	IndexedSkipList	O(1)	Create an empty container with the specified probability and maximum levels.
`IndexedSkipList(const container_type &source)`	Container	O(n)	Copy constructor. Copies all elements along with probability and maximum levels.
`template<class InIt > IndexedSkipList(InIt first, InIt last)`	Sequence	O(n)	Creates a container with a copy of the range. Probability is 25% and maximum levels is 8.
`template<class InIt > IndexedSkipList(InIt first, InIt last, double probability, size_type maxLevel)`	Sequence w/ probability	O(n)	Creates a container with the specified probability and maximum levels along with a copy of the range.
`template<class InIt > IndexedSkipList(InIt first, InIt last, size_type maxNodes)`	Sequence w/ probability	O(n)	Creates a container with a copy of the range. Default probability of 25%. Maximum levels based on maxNodes.
`IndexedSkipList(size_type count)`	Sequence	O(n)	Creates a container with `count` elements.
`IndexedSkipList(size_type count, const T &val)`	Sequence	O(n)	Creates a container with `count` copies of `val`.
`IndexedSkipList(size_type count, const T &val, double probability, size_type maxLevel)`	Sequence /w probability	O(n)	Creates a container with `count` copies of `val`. Container is created with specified probability and maximum level.
`IndexedSkipList(size_type count, const T &val, size_type maxNodes)`	Sequence /w probability	O(n)	Creates a container with `count` copies of `val`. Default probability of 25%. Maximum levels based on maxNodes.
`IndexedSkipList(const Prob &prob)`	IndexedSkipList	O(1)	Creates a an empty container with the specified probability and maximum levels.
`IndexedSkipList(size_type count, const Prob &prob)`	Sequence /w probability	O(n)	Creates a container with `count` copies of `val`. Container is created with specified probability and maximum level.
`IndexedSkipList(size_type count, const T &val, const Prob &prob)`	Sequence /w probability	O(n)	Creates a container with `count` elements. Container is created with specified probability and maximum level.
`template<class InIt > IndexedSkipList(InIt first, InIt last, const Prob &prob)`	Sequence /w probability	O(n)	Creates a container with a copy of a range. Container is created with specified probability and maximum level.
`~IndexedSkipList()`	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)`	IndexedSkipList	O(n)	Clears all elements and copies range into container.
`template<class InIt > void assign(size_type count, const T &val)`	IndexedSkipList	O(n)	Clears all elements and inserts `count` copies of `val`.
`iterator insert(const iterator &where, const T &val)`	Sequence	O(logn)	Inserts a copy of `val` into the container before `where`.
`iterator insert(const iterator &where, size_type count, const T &val)`	Sequence	O(n)	Inserts `count`> copies of `val` into the container before `where`.
`template<class InIt > void insert(const iterator &where, InIt first, InIt last)`	Sequence	O(n)	Inserts a range into the container before `where`.
`iterator erase(const iterator &where)`	Sequence	O(logn)	Erases the element pointed to by `where`.
`iterator destroy(const iterator &where)`	IndexedSkipList	O(logn)	Erases and deletes the element pointed to by `where`.
`iterator erase(const iterator &first, const iterator &last)`	Sequence	O(n)	Erases all elements in a range.
`iterator destroy(const iterator &first, const iterator &last)`	IndexedSkipList	O(n)	Erases and deletes all elements in a range.
`void clear()`	Sequence	O(n)	Erases all of the elements.
`void destroy()`	IndexedSkipList	O(n)	Erases and deletes all of the elements.
`iterator erase_index(size_type index)`	IndexedSkipList	O(logn)	Erases the element at the specified index.
`iterator destroy_index(size_type index)`	IndexedSkipList	O(logn)	Deletes and erases the element at the specified index.
`template<class Pr1 > void erase_if (Pr1 pred)`	IndexedSkipList	O(n)	Erases all elements where pred(*where) is true.
`template<class Pr4 > void destroy_if (Pr4 pred)`	IndexedSkipList	O(n)	Destroys all elements where pred(*where) is true.
`void cut(const iterator &first, const iterator &last, container_type &right)`	IndexedSkipList	O(logn)	Extract nodes in the specified range [first,last) into right.
`reference front()`	Front Insertion Sequence	O(1)	Returns the first element.
`const_reference front() const`	Front Insertion Sequence	O(1)	Returns the first element.
`reference back()`	Back Insertion Sequence	O(1)	Returns the last element.
`const_reference back() const`	Back Insertion Sequence	O(1)	Returns the last element.
`void push_front(const T &val)`	Front Insertion Sequence	O(1C/logn)	Inserts a new element at the beginning.
`void pop_front()`	Front Insertion Sequence	O(1C/logn)	Removes the first element.
`void destroy_front()`	Front Access Container	O(1C/logn)	Removes and deletes the first pointer element.
`void push_back(const T &val)`	Back Insertion Sequence	O(1C/logn)	Inserts a new element at the end.
`void pop_back()`	Back Insertion Sequence	O(1C/logn)	Removes the last element.
`void destroy_back()`	Back Access Container	O(1C/logn)	Removes and deletes the last pointer element.
`void resize(size_type newsize)`	Sequence	O(n)	Inserts or erases elements at the end such that the size becomes `newsize`.
`void resize(size_type newsize, const T &val)`	Sequence	O(n)	Inserts copies of `val` or erases elements at the end such that the size becomes `newsize`.
`mapped_type_reference operator[](size_type index)`	Random Access Container LOGN	O(logn)	Returns a reference to the element located at the specified index.
`const_mapped_type_reference operator[](size_type index) const`	Random Access Container LOGN	O(logn)	Returns a reference to the element located at the specified index.
`mapped_type_reference at(size_type off)`	Random Access Container LOGN	O(logn)	Returns a reference to the element located at the specified index.
`const_mapped_type_reference at(size_type off) const`	Random Access Container LOGN	O(logn)	Returns a reference to the element located at the specified index.
`mapped_type_reference value(T &value)`	IndexedSkipList	O(1)	Returns reference to `value`
`void reverse()`	IndexedSkipList	O(n)	Reverses list.
`void unique()`	IndexedSkipList	O(n)	Removes all but the first element in every consecutive group of equal elements.
`template<class Pr2 > void unique(Pr2 pred)`	IndexedSkipList	O(n)	Removes all but the first element in every consecutive group of equal elements.
`void sort()`	IndexedSkipList	O(n*logn)	Sorts container according to operator<.
`template<class Pr3 > void sort(Pr3 pred)`	IndexedSkipList	O(n*logn)	Sorts container according to predicate.
`void stable_sort()`	IndexedSkipList	O(n*logn)	Sorts container according to operator<.
`template<class Pr3 > void stable_sort(Pr3 pred)`	IndexedSkipList	O(n*logn)	Sorts container according to predicate.
`void erase_value(const T &val)`	IndexedSkipList	O(n)	Erases all elements that are equal to `val`.
`void splice(const iterator &where, container_type &right)`	IndexedSkipList	O(logn)	All of the elements of `right` are inserted before `where` and removed from `right`.
`void splice(const iterator &where, container_type &right, iterator first)`	IndexedSkipList	O(logn)	Moves the element pointed to by `first` from `right` to current container, inserting it before `where`.
`void splice(const iterator &where, container_type &right, iterator first, iterator last)`	IndexedSkipList	O(logn)	Moves the elements in [first, last) from `right` to current container, inserting them before `where`.
`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.

IndexedSkipList<class T, class R = RNG>