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

Category: containers
Component type: type

Description

An IndexedTinySkipList is identical to an IndexedSSkipList except that the internal nodes use a smaller memory footprint. It does not contain the number of levels used by the node. Nodes for IndexedTinySkipList store forward pointers and the skip amount. Since most nodes have but one level, the overhead memory requirement is reduced by almost one third. A few operations will be slower, but the algorithmic complexity of all functionality remains the same as an IndexedSSkipList.

An IndexedTinySkipList acts like a vector in functionality though the performance requirements are different in a few places. An IndexedTinySkipList is a Sequence that supports random access to elements in logarithmic time, constant time insertion at the beginning and logarithmic time removal of elements at the end, with logarithmic time insertion and removal of elements in the middle. Note that repeated insertion at the end is done in linear time. Repeated erasing at the end is best done by specifying a range which is done in linear time.

An IndexedTinySkipList uses an Arbitrary Access Iterator LOGN. See IndexedTinySkipList::T0 for more info. Random access and decrementing is done in logarithmic time while incrementing is done in constant time.

An IndexedTinySkipList is an Arbitrary 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 a Front Access Container meaning that the front of the list is available for retrieval, erasure and destruction in constant time.
It is a Back Access Container LOGN meaning that the back of the list is available for retrieval, erasure and destruction in logarithmic time.
It is a Front Insertion Sequence meaning that the front of the list is available for insertion in constant time.
It is a Back Insertion Sequence LOGN meaning that the back of the list is available for insertion in logarithmic time.

IndexedTinySkipList 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 IndexedTinySkipList iterators.

All Equality Comparable comparisons.
Post and pre-increment.
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 `IndexedTinySkipList`'s value type. `IndexedTinySkipList::mapped_type` is also defined to this value for convenience.
`R`	The `IndexedTinySkipList`'s random number generator, used for selection of levels per node.	RNG

Model of

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

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 `IndexedTinySkipList`.
`container_type`	IndexedTinySkipList		Type of this container
`pointer`	Container		Pointer to `T`.
`reference`	Container		Reference to `T`
`const_reference`	Container		Const reference to `T`
`mapped_type`	IndexedTinySkipList		A type identical to `value_type` and `T`
`mapped_type_reference`	IndexedTinySkipList		A type identical to `reference`
`const_mapped_type`	IndexedTinySkipList		A type identical to `const value_type`
`const_mapped_type_reference`	IndexedTinySkipList		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 LOGN		Iterator used to iterate backwards through the container's elements. [1]
`const_reverse_iterator`	Reversible Container LOGN		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 LOGN	O(1)	Returns a `reverse_iterator` pointing to the beginning of the reversed container.
`reverse_iterator rend()`	Reversible Container LOGN	O(1)	Returns a `reverse_iterator` pointing to the end of the reversed container.
`const_reverse_iterator rbegin() const`	Reversible Container LOGN	O(1)	Returns a `const_reverse_iterator` pointing to the beginning of the reversed container.
`const_reverse_iterator rend() const`	Reversible Container LOGN	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`.
`IndexedTinySkipList()`	Container	O(1)	Creates an empty container. Default probability of 25% and 8 levels.
`IndexedTinySkipList(double probability, size_type maxLevel)`	IndexedTinySkipList	O(1)	Create an empty container with the specified probability and maximum levels.
`IndexedTinySkipList(const container_type &source)`	Container	O(n)	Copy constructor. Copies all elements along with probability and maximum levels.
`template<class InIt > IndexedTinySkipList(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 > IndexedTinySkipList(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 > IndexedTinySkipList(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.
`IndexedTinySkipList(size_type count)`	Sequence	O(n)	Creates a container with `count` elements.
`IndexedTinySkipList(size_type count, const T &val)`	Sequence	O(n)	Creates a container with `count` copies of `val`.
`IndexedTinySkipList(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.
`IndexedTinySkipList(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.
`IndexedTinySkipList(const Prob &prob)`	IndexedTinySkipList	O(1)	Creates a an empty container with the specified probability and maximum levels.
`IndexedTinySkipList(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.
`IndexedTinySkipList(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 > IndexedTinySkipList(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.
`~IndexedTinySkipList()`	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)`	IndexedTinySkipList	O(n)	Clears all elements and copies range into container.
`template<class InIt > void assign(size_type count, const T &val)`	IndexedTinySkipList	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)`	IndexedTinySkipList	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)`	IndexedTinySkipList	O(n)	Erases and deletes all elements in a range.
`void clear()`	Sequence	O(n)	Erases all of the elements.
`void destroy()`	IndexedTinySkipList	O(n)	Erases and deletes all of the elements.
`iterator erase_index(size_type index)`	IndexedTinySkipList	O(logn)	Erases the element at the specified index.
`iterator destroy_index(size_type index)`	IndexedTinySkipList	O(logn)	Deletes and erases the element at the specified index.
`template<class Pr1 > void erase_if (Pr1 pred)`	IndexedTinySkipList	O(n)	Erases all elements where pred(*where) is true.
`template<class Pr4 > void destroy_if (Pr4 pred)`	IndexedTinySkipList	O(n)	Destroys all elements where pred(*where) is true.
`void cut(const iterator &first, const iterator &last, container_type &right)`	IndexedTinySkipList	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 LOGN	O(1)	Returns the last element.
`const_reference back() const`	Back Insertion Sequence LOGN	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 LOGN	O(1C/logn)	Inserts a new element at the end.
`void pop_back()`	Back Insertion Sequence LOGN	O(1C/logn)	Removes the last element.
`void destroy_back()`	Back Access Container LOGN	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)`	IndexedTinySkipList	O(1)	Returns reference to `value`
`void reverse()`	IndexedTinySkipList	O(n)	Reverses list.
`void unique()`	IndexedTinySkipList	O(n)	Removes all but the first element in every consecutive group of equal elements.
`template<class Pr2 > void unique(Pr2 pred)`	IndexedTinySkipList	O(n)	Removes all but the first element in every consecutive group of equal elements.
`void sort()`	IndexedTinySkipList	O(n*logn)	Sorts container according to operator<.
`template<class Pr3 > void sort(Pr3 pred)`	IndexedTinySkipList	O(n*logn)	Sorts container according to predicate.
`void stable_sort()`	IndexedTinySkipList	O(n*logn)	Sorts container according to operator<.
`template<class Pr3 > void stable_sort(Pr3 pred)`	IndexedTinySkipList	O(n*logn)	Sorts container according to predicate.
`void erase_value(const T &val)`	IndexedTinySkipList	O(n)	Erases all elements that are equal to `val`.
`void splice(const iterator &where, container_type &right)`	IndexedTinySkipList	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)`	IndexedTinySkipList	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)`	IndexedTinySkipList	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.

IndexedTinySkipList<class T, class R = RNG>