AutoKeyedSkipList<class K, class T, class Pr = std::less<K>, class R = RNG>

Category: containers
Component type: type

Description

An AutoKeyedSkipList acts like a combination of a map and vector in functionality though the performance requirements are different in a few places. It can be accessed by key or numerical index. The index is the automatically calculated position in the sorted list.

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

An AutoKeyedSkipList is a Sorted Associative Container that associates objects of type K, the key, with objects of type T, the data.
It is a Pair Associative Container, meaning that its value type is pair<const K, T>.
It 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 a Unique Sorted Associative Container, meaning that no two elements have the same key.
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.

AutoKeyedSkipList 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 AutoKeyedSkipList 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.

WARNING: If key_type is size_t, then avoid using operator[](key). Use operator()(key) instead. operator[](size_t index) is used for accessing via index. So there is a collision in method definition. This means that operator[](TWrap<size_t>(key)) or operator()(size_t key) should be used instead. Not adhering to this warning will mean the key being used as a linear index instead.

Definition

Defined in the custom header "CSAutoKeyedSkipList.h".

Template parameters

Parameter Description Default
K The AutoKeyedSkipList's key type. This is also defined as AutoKeyedSkipList::key_type.  
T The AutoKeyedSkipList's data type. This is also defined as AutoKeyedSkipList::data_type. AutoKeyedSkipList::mapped_type is also defined to this value for convenience.  
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 AutoKeyedSkipList::key_compare. AutoKeyedSkipList::value_compare compares the key, but takes AutoKeyedSkipList::value_type as parameters. 		less<K>
R The AutoKeyedSkipList's random number generator, used for selection of levels per node. RNG

Model of

Random Access Container LOGN, Pair Associative Container, Unique Sorted Associative Container, Associative Container LOGN, Destructive Associative Container LOGN, Front Access Container and Back Access Container

Type requirements

Public base classes

None.

Members

Member Where defined Performance Description
key_type Associative Container LOGN The key type, K.
data_type Pair Associative Container The type of object, T, associated with the keys.
value_type Pair Associative Container The type of object, pair<const key_type, data_type>, stored in the AutoKeyedSkipList.
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 AutoKeyedSkipList Type of this container
pointer Container Pointer to value_type.
reference Container Reference to value_type
const_reference Container Const reference to value_type
mapped_type Pair Associative Container A type identical to data_type and T.
mapped_type_reference Pair Associative Container Reference to data_type and T
const_mapped_type Pair Associative Container Const version of data_type and T
const_mapped_type_reference Pair Associative Container Const reference to data_type and T
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.
slpair AutoKeyedSkipList 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.
AutoKeyedSkipList() Container O(1) Creates an empty container. Default probability of 25% and 8 levels.
AutoKeyedSkipList(size_type maxNodes) AutoKeyedSkipList O(1) Creates an empty container. Default probability of 25%. Maximum levels based on maxNodes.
AutoKeyedSkipList(double probability, size_type maxLevel) AutoKeyedSkipList O(1) Create an empty container with the specified probability and maximum levels.
AutoKeyedSkipList(const container_type &source) Container O(n*logn) Copy constructor. Copies all elements along with probability and maximum levels.
template<class InIt >
AutoKeyedSkipList(InIt first, InIt last) 		Unique Sorted Associative Container O(n*logn) Creates a container with a copy of the range.
Probability is 25% and maximum levels is 8.
template<class InIt >
AutoKeyedSkipList(InIt first, InIt last,
         double probability, size_type maxLevel) 		Unique Sorted Associative Container
w/ probability 		O(n*logn) Creates a container with the specified probability and maximum levels
along with a copy of the range.
template<class InIt >
AutoKeyedSkipList(InIt first, InIt last,
         size_type maxNodes) 		Unique Sorted Associative Container
w/ probability 		O(n*logn) Creates a container with a copy of the range.
Default probability of 25%. Maximum levels based on maxNodes.
AutoKeyedSkipList(const key_compare &comp) Sorted Associative Container O(1) Creates an empty container, using comp as the key_compare object.
template<class InIt >
AutoKeyedSkipList(InIt first, InIt last,
         const key_compare &comp) 		Unique Sorted Associative Container O(n*logn) Creates a container with a copy of a range, using comp as the key_compare object.
template<class InIt >
AutoKeyedSkipList(InIt first, InIt last,
         const key_compare &comp,
         double probability, size_type maxLevel) 		Unique Sorted Associative Container
/w probability 		O(n*logn) Creates a container with a copy of a range, using comp as the key_compare object.
Container is created with specified probability and maximum level.
template<class InIt >
AutoKeyedSkipList(InIt first, InIt last,
         const key_compare &comp,
         size_type maxNodes) 		Unique Sorted Associative Container
/w probability 		O(n*logn) Creates a container with a copy of a range, using comp as the key_compare object.
Default probability of 25%. Maximum levels based on maxNodes.
~AutoKeyedSkipList() 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) 		AutoKeyedSkipList O(n*logn) Clears all elements and copies range into container.
std::pair< iterator, bool >
insert(const value_type &val) 		Unique Associative Container O(logn) Inserts val into the container.
iterator insert(const iterator &where,
                const value_type &val) 		Unique Sorted Associative Container O(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) 		Unique Sorted Associative Container O(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(logn) Erases the element pointed to by where.
iterator destroy(const iterator &where) Destructive Associative Container LOGN O(logn) Erases and deletes the element pointed to by where.
size_type erase(const key_type &keyval) Associative Container LOGN O(logn) Erases the element whose key is keyval.
size_type destroy(const key_type &keyval) Destructive Associative Container LOGN O(logn) Erases and deletes the element whose key is keyval.
iterator erase(const iterator &first, const iterator &last) Associative Container LOGN O(n) Erases all elements in a range.
iterator destroy(const iterator &first, const iterator &last) Destructive Associative Container LOGN O(n) Erases and deletes all elements in a range.
void clear() Associative Container LOGN O(n) Erases all of the elements.
void destroy() Destructive Associative Container LOGN O(n) Erases and deletes all of the elements.
iterator erase_index(size_type index) AutoKeyedSkipList O(logn) Erases the element at the specified index.
iterator destroy_index(size_type index) AutoKeyedSkipList O(logn) Deletes and erases the element at the specified index.
template<class Pr1 >
void erase_if (Pr1 pred) 		AutoKeyedSkipList O(n) Erases all elements where pred(*where) is true.
template<class Pr4 >
void destroy_if (Pr4 pred) 		AutoKeyedSkipList O(n) Destroys all elements where pred(*where) is true.
void cut(const iterator &first, const iterator &last,
         container_type &right) 		AutoKeyedSkipList O(logn) Extract nodes in the specified range [first,last) into right.
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(1C/logn) Removes the first element.
void destroy_front() Front Access Container O(1C/logn) Removes and deletes the first pointer element.
void pop_back() Back Access Container O(1C/logn) Removes the last element.
void destroy_back() Back Access Container O(1C/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 Unique 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.
mapped_type_reference
operator[](const key_type &key) 		AutoKeyedSkipList O(logn) Returns a reference to the data associated with the specified key.
const_mapped_type_reference
operator[](const key_type &key) 		AutoKeyedSkipList O(logn) Returns a const_reference to the data associated with the specified key.
mapped_type_reference
operator()(const key_type &key) 		AutoKeyedSkipList O(logn) Returns a reference to the data associated with the specified key.
const_mapped_type_reference
operator()(const key_type &key) 		AutoKeyedSkipList O(logn) Returns a const_reference to the data associated with the specified key.
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.
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

[1] AutoKeyedSkipList::iterator is not a mutable iterator, because AutoKeyedSkipList::value_type is not Assignable. That is, if i is of type AutoKeyedSkipList::iterator and p is of type AutoKeyedSkipList::value_type, then *i = p is not a valid expression. However, AutoKeyedSkipList::iterator isn't a constant iterator either, because it can be used to modify the object that it points to for members that aren't used as part of the key. Using the same notation as above, i->member = p is a valid expression. The same point applies to AutoKeyedSkipList::reverse_iterator.

See also

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

 All Classes Files Functions Variables Typedefs
Generated on Thu Jan 6 2011 15:52:40 for SkipList Library by  doxygen 1.7.3