XMultiAccessSkipList<int X, class K, class CT, class A = XAccessSelf<K,typename CT::value_type>, class Pr = std::less<K> >

Category: containers
Component type: type

Description

A XMultiAccessSkipList acts like a multimap in functionality though the performance requirements are different in a few places.

A XMultiAutoSkipList uses a Random Access Iterator LOGN. See XMultiAccessSkipList::T0 for more info. A XMultiAccessSkipList is an Access Associative Container, meaning that its key is a member of type T.
It is a Multiple Sorted Associative Container, meaning that two or more elements may be identical.
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 XMultiAccessSkipList has the important property that inserting a new element into a XMultiAccessSkipList does not invalidate iterators that point to existing elements. Erasing an element from a XMultiAccessSkipList also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

A XMultiAccessSkipList acts like a multimap in functionality though the performance requirements are different in a few places.

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

Definition

Defined in the custom header "CSXMultiAccessSkipList.h".

Template parameters

Parameter	Description	Default
X	The XMultiAccessSkipList's index within the composite container of type XBidiCompositeSkipList.
K	The XMultiAccessSkipList's key type. This is also defined as XMultiAccessSkipList::key_type.
CT	The custom composite container class.
A	The XMultiAccessSkipList's predicate for accessing the key via an object of type T.	XAccessSelf<K,T>
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 XMultiAccessSkipList::key_compare. XMultiAccessSkipList::value_compare compares the key, but takes XMultiAccessSkipList::value_type as parameters.	less<K>

Model of

Access Associative Container, Multiple Sorted Associative Container, Associative Container LOGN, Destructive Associative Container LOGN, Front Access Container and Back Access Container

Type requirements

• X is unsigned int.
• CT is derived from XBidiCompositeSkipList.
• A is a predicate whose argument is CT::value_type and returns type K.
• Pr is a Strict Weak Ordering whose argument type is T.

Public base classes

None.

Members

Member	Where defined	Performance	Description
value_type	Container		The type of object, T, stored in the XMultiAccessSkipList. T is CT::value_type.
key_type	Associative Container LOGN		The key type, K.
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	XMultiAccessSkipList		Type of this container
pointer	Container		Pointer to T.
reference	Container		Reference to T
const_reference	Container		Const reference to T
mapped_type	Access Associative Container		A type identical to value_type and T
mapped_type_reference	Access Associative Container		A type identical to reference
const_mapped_type	Access Associative Container		A type identical to const value_type
const_mapped_type_reference	Access 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.
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.
slpair	XMultiAccessSkipList		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.
XMultiAccessSkipList()	Container	O(1)	Creates an empty container. Default probability of 25% and 8 levels.
XMultiAccessSkipList(const key_compare &comp)	Sorted Associative Container	O(1)	Creates an empty container, using comp as the key_compare object.
~XMultiAccessSkipList()	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.
template<class InIt > void assign(InIt first, InIt last)	XMultiAccessSkipList	O(m*n*logn)	Clears all elements and copies range into container.
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 value_type &val)	Multiple Associative Container	O(m*logn)	Inserts val into the container.
iterator insert(const iterator &where,                 const value_type &val)	Multiple Sorted Associative Container	O(m*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)	Multiple Sorted Associative Container	O(m*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(m*logn)	Erases the element pointed to by where.
iterator destroy(const iterator &where)	Destructive Associative Container LOGN	O(m*logn)	Erases and deletes the element pointed to by where.
size_type erase(const key_type &keyval)	Associative Container LOGN	O(m*logn)	Erases the element whose key is keyval.
size_type destroy(const key_type &keyval)	Destructive Associative Container LOGN	O(m*logn)	Erases and deletes the element whose key is keyval.
iterator erase(const iterator &first, const iterator &last)	Associative Container LOGN	O(m*n*logn)	Erases all elements in a range.
iterator destroy(const iterator &first, const iterator &last)	Destructive Associative Container LOGN	O(m*n*logn)	Erases and deletes all elements in a range.
void clear()	Associative Container LOGN	O(m+n)	Erases all of the elements.
void destroy()	Destructive Associative Container LOGN	O(m+n)	Erases and deletes all of the elements.
template<class Pr1 > void erase_if (Pr1 pred)	XMultiAccessSkipList	O(m*n*logn)	Erases all elements where pred(*where) is true.
template<class Pr4 > void destroy_if (Pr4 pred)	XMultiAccessSkipList	O(m*n*logn)	Destroys all elements where pred(*where) is true.
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(m*logn)	Removes the first element.
void destroy_front()	Front Access Container	O(m*logn)	Removes and deletes the first pointer element.
void pop_back()	Back Access Container	O(m*logn)	Removes the last element.
void destroy_back()	Back Access Container	O(m*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	Multiple 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

• XMultiAutoSkipList is defined as being a Container and a Multiple Sorted Associative 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. Also, the range constructors do not exist for the same reason.

See also

XBidiCompositeSkipList, XMultiAutoSkipList, XIndexedSkipList, MultiSkipList, Iterator Overview, Bidirectional Iterator, Container, 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, Access Associative Container, Random Access Container LOGN Reversible Container, Reversible Container LOGN, Front Access Container, Back Access Container and Back Access Container LOGN