XIndexedSkipList<unsigned int X, class CT>

Category: containers
Component type: type

Description

An XIndexedSkipList is a delegate container. It does not actually contain any elements. Instead, it is declared within a derived class of a composite container like XBidiCompositeSkipList. There is a delegate container for each ordering of the list that the user requires. Note that performance is affected by how many orderings are affected. If only the current ordering is affected, then standard performance will apply. If all m orderings are affected, then the performance will be proportional to m. Not only that, but even if the performance for the current ordering is faster than another ordering, an action that affects all orderings will have a performance proportional to the worst performance of all the orderings. So instead of O(1) for one ordering being O(m) for all orderings can acutally become O(m*n*logn). This is reflected in the grid below.

Iterators for different delegate containers can be converted using the assignment operator or passing the existing iterator as an argument to the constuctor of the newly created iterator. When converting to an indexed iterator, it takes logarithmic time. When converting to a non-indexed iterator, it takes constant time.

An XIndexedSkipList acts like a vector in functionality though the performance requirements are different in a few places. An XIndexedSkipList 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 XIndexedSkipList uses a Random Access Iterator LOGN. See XIndexedSkipList::T0 for more info.

An XIndexedSkipList 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.

XIndexedSkipList 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 XIndexedSkipList 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 "CSCompositeSkipList.h".

Template parameters

Parameter	Description	Default
X	The XIndexedSkipList's index within the composite container of type XBidiCompositeContainer.
CT	The custom composite container class.

Model of

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

Type requirements

• X is unsigned int.
• CT is derived from XBidiCompositeSkipList.

Public base classes

None.

Members

In the performance notation, m is N, the number of internal containers. And n is the number of elements.

Member	Where defined	Performance	Description
value_type	Container		The type of object, T, stored in the XIndexedSkipList. T is CT::value_type.
container_type	XIndexedSkipList		Type of this container
pointer	Container		Pointer to T.
reference	Container		Reference to T
const_reference	Container		Const reference to T
mapped_type	XIndexedSkipList		A type identical to value_type and T
mapped_type_reference	XIndexedSkipList		A type identical to reference
const_mapped_type	XIndexedSkipList		A type identical to const value_type
const_mapped_type_reference	XIndexedSkipList		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.
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.
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.
XIndexedSkipList()	Container	O(1)	Creates an empty delegate container.
~XIndexedSkipList()	Container	O(n)	Destructor. Clears list.
container_type& operator=(const container_type &source)	Container	O(m*n*logn)	The assignment operator.
void swap(container_type &right)	Container	O(m*n*logn)	Swaps the contents of two containers. NOT IMPLEMENTED YET!!!
template<class InIt > void assign(InIt first, InIt last)	XIndexedSkipList	O(m*n*logn)	Clears all elements and copies range into container.
template<class InIt > void assign(size_type count, const T &val)	XIndexedSkipList	O(m*n*logn)	Clears all elements and inserts count copies of val.
void insert(node_type *node)	XIndexedSkipList	O(1C)	Adds node to end of list.
void erase(node_type *node)	XIndexedSkipList	O(1C)	Erases the specified node.
iterator insert(const T &val)	XIndexedSkipList	O(m*logn)	Inserts element to end of list. Invokes push_back().
iterator insert(const iterator &where,                 const T &val)	Sequence	O(m*logn)	Inserts a copy of val into the container before where.
iterator insert(const iterator &where,                 size_type count, const T &val)	Sequence	O(m*n*logn)	Inserts count> copies of val into the container before where.
template<class InIt > void insert(const iterator &where,             InIt first, InIt last)	Sequence	O(m*n*logn)	Inserts a range into the container before where.
iterator erase(const iterator &where)	Sequence	O(m*logn)	Erases the element pointed to by where.
iterator destroy(const iterator &where)	XIndexedSkipList	O(m*logn)	Erases and deletes the element pointed to by where.
iterator erase(const iterator &first, const iterator &last)	Sequence	O(m*n*logn)	Erases all elements in a range.
iterator destroy(const iterator &first, const iterator &last)	XIndexedSkipList	O(m*n*logn)	Erases and deletes all elements in a range.
void clear()	Sequence	O(m+n)	Erases all of the elements.
void destroy()	XIndexedSkipList	O(m+n)	Erases and deletes all of the elements.
iterator erase_index(size_type index)	XIndexedSkipList	O(m*logn)	Erases the element at the specified index.
iterator destroy_index(size_type index)	XIndexedSkipList	O(m*logn)	Deletes and erases the element at the specified index.
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(m*logn)	Inserts a new element at the beginning.
void pop_front()	Front Insertion Sequence	O(m*logn)	Removes the first element.
void destroy_front()	Front Access Container	O(m*logn)	Removes and deletes the first pointer element.
void push_back(const T &val)	Back Insertion Sequence	O(m*logn)	Inserts a new element at the end.
void pop_back()	Back Insertion Sequence	O(m*logn)	Removes the last element.
void destroy_back()	Back Access Container	O(m*logn)	Removes and deletes the last pointer element.
void resize(size_type newsize)	Sequence	O(m*n)	Inserts or erases elements at the end such that the size becomes newsize.
void resize(size_type newsize, const T &val)	Sequence	O(m*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)	XIndexedSkipList	O(1)	Returns reference to value
void reverse()	XIndexedSkipList	O(n)	Reverses list.
void unique()	XIndexedSkipList	O(m*n*logn)	Removes all but the first element in every consecutive group of equal elements.
template<class Pr2 > void unique(Pr2 pred)	XIndexedSkipList	O(m*n*logn)	Removes all but the first element in every consecutive group of equal elements.
void sort()	XIndexedSkipList	O(n*logn)	Sorts container according to operator<.
template<class Pr3 > void sort(Pr3 pred)	XIndexedSkipList	O(n*logn)	Sorts container according to predicate.
void stable_sort()	XIndexedSkipList	O(n*logn)	Sorts container according to operator<.
template<class Pr3 > void stable_sort(Pr3 pred)	XIndexedSkipList	O(n*logn)	Sorts container according to predicate.
void erase_value(const T &val)	XIndexedSkipList	O(m*n*logn)	Erases all elements that are equal to val.
template<class Pr1 > void erase_if (Pr1 pred)	XIndexedSkipList	O(m*n*logn)	Erases all elements where pred(*where) is true.
template<class Pr4 > void destroy_if (Pr4 pred)	XIndexedSkipList	O(m*n*logn)	Destroys all elements where pred(*where) is true.
void move(const iterator &dest, const iterator &source)	XIndexedSkipList	O(logn)	Moves the node at source to immediately before dest.
void move(const iterator &dest,           const iterator &first, const iterator &last)	XIndexedSkipList	O(logn)	Moves the range [first,last) to immediately before dest.
void swap(const iterator &left, const iterator &right)	XIndexedSkipList	O(logn)	Swap nodes of two elements.
void swap(const iterator &first1, const iterator &last1,           const iterator &first2, const iterator &last2)	XIndexedSkipList	O(logn)	Swap nodes of two ranges.
void cut(const iterator &first, const iterator &last,          tmp_container_type &right)	XIndexedSkipList	O(logn)	Internal method to extract nodes in the specified range [first,last) into right.
void cut(const iterator &where, tmp_container_type &right)	XIndexedSkipList	O(logn)	Internal method to extract the node pointed to by where into right.
void splice(const iterator &where, tmp_container_type &right)	XIndexedSkipList	O(logn)	All of the elements of right are inserted before where and removed from right.
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

• XIndexedSkipList is defined as being a Container. However, the copy constructor should not be used. This is because delegate containers are not meant to be copied as they do not acutally contain any elements.

See also

XBidiCompositeSkipList, XMultiAutoSkipList, XMultiSkipList, IndexedSkipList, Iterator Overview, Random Access Iterator LOGN, 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