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 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.
Defined in the custom header "CSIndexedSkipList.h".
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 |
Arbitrary Access Container LOGN, Front Insertion Sequence, Back Insertion Sequence LOGN, Front Access Container and Back Access Container LOGN
T
is Assignable. R
is an RNG (is Default Constructible and supports rand() and drand()). None.
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 > | Sequence | O(n) | Creates a container with a copy of the range. Probability is 25% and maximum levels is 8. |
template<class InIt > | 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 > | 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, | 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, | 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, | Sequence /w probability | O(n) | Creates a container with count elements.Container is created with specified probability and maximum level. |
template<class InIt > | 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& | Container | O(n) | The assignment operator. |
void swap(container_type &right) | Container | O(1) | Swaps the contents of two containers. |
template<class InIt > | IndexedTinySkipList | O(n) | Clears all elements and copies range into container. |
template<class InIt > | IndexedTinySkipList | O(n) | Clears all elements and inserts count copies of val . |
iterator insert(const iterator &where, | Sequence | O(logn) | Inserts a copy of val into the container before where . |
iterator insert(const iterator &where, | Sequence | O(n) | Inserts count > copies of val into the container before where . |
template<class InIt > | 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 > | IndexedTinySkipList | O(n) | Erases all elements where pred(*where) is true. |
template<class Pr4 > | IndexedTinySkipList | O(n) | Destroys all elements where pred(*where) is true. |
void cut(const iterator &first, const iterator &last, | 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 | Random Access Container LOGN | O(logn) | Returns a reference to the element located at the specified index. |
const_mapped_type_reference | 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 > | 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 > | IndexedTinySkipList | O(n*logn) | Sorts container according to predicate. |
void stable_sort() | IndexedTinySkipList | O(n*logn) | Sorts container according to operator<. |
template<class Pr3 > | 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, | 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, | IndexedTinySkipList | O(logn) | Moves the elements in [first, last) from right to current container, inserting them before where . |
bool operator==(const container&, | Forward Container | O(n) | Tests two maps for equality. This is a global function, not a member function. |
bool operator<(const container&, | Forward Container | O(n) | Lexicographical comparison. This is a global function, not a member function. |
Iterator Overview, Arbitrary Access Iterator LOGN, IndexedSkipList, IndexedSSkipList, Sequence, Container, Random Access Container LOGN Simple Associative Container, Unique Sorted Associative Container, Multiple Sorted Associative Container, Associative Container, Associative Container LOGN, Sorted Associative Container, Destructive Associative Container LOGN, Pair Associative Container, Forward Container, Reversible Container, Reversible Container LOGN, Front Insertion Sequence, Back Insertion Sequence, Back Insertion Sequence LOGN, Front Access Container, Back Access Container and Back Access Container LOGN