Classes | Public Types | Public Member Functions | Private Member Functions | Private Attributes | Friends

AutoSkipList< T, Pr, R > Class Template Reference

Random Access Double Linked SkipList that acts like a set where items are automatically indexed. More...

#include <CSAutoSkipList.h>

List of all members.

Classes

class  T0
 iterator More...
class  T1
 const_iterator More...

Public Types

typedef size_t size_type
 An unsigned integral type that can represent any nonnegative value of the container's distance type. (Container)
typedef ptrdiff_t difference_type
 A signed integral type used to represent the distance between two of the container's iterators. (Container)
typedef T value_type
 The type of the object stored in a container. (Container)
typedef BidiIdxNode< value_typenode_type
 Internal node type.
typedef AutoSkipList< T, Pr, R > container_type
 Type that represents this list.
typedef T key_type
 The list's key type, T. (Associative Container LOGN)
typedef T0 iterator
 The type of iterator used to iterate through a container's elements. (Container)
typedef T * pointer
 A type that behaves as a pointer to the container's value type. (Container)
typedef T & reference
 A type that behaves as a reference to the container's value type. (Container)
typedef T mapped_type
 A type identical to value_type (Simple Associative Container)
typedef T & mapped_type_reference
 A type identical to reference (Simple Associative Container)
typedef const T const_mapped_type
 A type identical to const value_type (Simple Associative Container)
typedef const T & const_mapped_type_reference
 A type identical to const_reference (Simple Associative Container)
typedef const T & const_reference
 A type that behaves as a const reference to the container's value type. (Container)
typedef T1 const_iterator
 A type of iterator that may be used to examine, but not to modify, a container's elements. (Container)
typedef std::reverse_iterator
< iterator
reverse_iterator
 A Reverse Iterator adaptor whose base iterator type is the container's iterator type. (Reversible Container)
typedef std::reverse_iterator
< const_iterator
const_reverse_iterator
 A Reverse Iterator adaptor whose base iterator type is the container's const iterator type. (Reversible Container)
typedef std::pair< iterator, bool > slpair
 Type for pair of iterator and bool used as return value for insert(T val).
typedef std::pair< iterator,
iterator
ipair
 Type for pair of iterators.
typedef std::pair
< const_iterator,
const_iterator
const_ipair
 Type for pair of const_iterators.
typedef Pr key_compare
 Function object that compares two keys for ordering. (Sorted Associative Container)
typedef Pr value_compare
 Function object that compares two values for ordering. (Sorted Associative Container)

Public Member Functions

 AutoSkipList ()
 Default Constructor O(1) (Container)
 AutoSkipList (size_type maxNodes)
 Constructor O(1)
 AutoSkipList (double probability, unsigned int maxLevel)
 Constructor O(1)
 AutoSkipList (const container_type &source)
 Copy Constructor O(n*logn) (Container)
template<class InIt >
 AutoSkipList (InIt first, InIt last)
 Constructor O(n*logn) (Unique Sorted Associative Container)
template<class InIt >
 AutoSkipList (InIt first, InIt last, double probability, unsigned int maxLevel)
 Constructor O(n*logn) (Unique Sorted Associative Container w/probability)
template<class InIt >
 AutoSkipList (InIt first, InIt last, size_type maxNodes)
 Constructor O(n*logn) (Unique Sorted Associative Container w/ probability)
 AutoSkipList (const key_compare &comp)
 Constructor O(1) (Sorted Associative Container)
template<class InIt >
 AutoSkipList (InIt first, InIt last, const key_compare &comp)
 Constructor O(n*logn) (Unique Sorted Associative Container)
template<class InIt >
 AutoSkipList (InIt first, InIt last, const key_compare &comp, double probability, unsigned int maxLevel)
 Constructor O(n*logn) (Unique Sorted Associative Container w/ probability)
template<class InIt >
 AutoSkipList (InIt first, InIt last, const key_compare &comp, size_type maxNodes)
 Constructor O(n*logn) (Unique Sorted Associative Container w/ probability)
 ~AutoSkipList ()
 Destructor O(n) (Container)
container_typeoperator= (const container_type &source)
 Assignment Operator O(n) (Container)
iterator begin ()
 Returns an iterator pointing to the beginning of the list. O(1) (Container)
iterator end ()
 Returns an iterator pointing to the end of the list. O(1) (Container)
const_iterator begin () const
 Returns a const_iterator pointing to the beginning of the list. O(1) (Container)
const_iterator end () const
 Returns a const_iterator pointing to the end of the list. O(1) (Container)
reverse_iterator rbegin ()
 Returns a reverse_iterator pointing to the beginning of the reversed list. O(1) (Reversible Container)
reverse_iterator rend ()
 Returns a reverse_iterator pointing to the end of the reversed list. O(1) (Reversible Container)
const_reverse_iterator rbegin () const
 Returns a const_reverse_iterator pointing to the beginning of the reversed list. O(1) (Reversible Container)
const_reverse_iterator rend () const
 Returns a reverse_iterator pointing to the end of the reversed list. O(1) (Reversible Container)
size_type size () const
 Returns the size of the list. O(1) (Container)
bool empty () const
 Returns true if the list's size is 0. O(1) (Container)
reference front ()
 Returns the first element. O(1) (Front Access Container)
const_reference front () const
 Returns the first element. O(1) (Front Access Container)
reference back ()
 Returns the last element. O(1) (Back Access Container)
const_reference back () const
 Returns the last element. O(1) (Back Access Container)
void pop_front ()
 Removes the first element. O(1C) (Front Access Container)
void destroy_front ()
 Deletes the first pointer element. O(1C) (Front Access Container)
void pop_back ()
 Removes the last element. O(1C) (Back Access Container)
void destroy_back ()
 Deletes the last pointer element. O(1C) (Back Access Container)
template<class InIt >
void assign (InIt first, InIt last)
 Clear list and copy element in iterator range [first,last) O(n*logn).
slpair insert (const value_type &val)
 Inserts value into the list O(logn). (Unique Associative Container)
iterator insert (const iterator &where, const value_type &val)
 Inserts value into the list. O(logn) (Unique Sorted Associative Container)
template<class InIt >
void insert (InIt first, InIt last)
 Inserts values from the range [first,last) into the list by calling insert(*where). O(n*logn) (Unique Sorted Associative Container)
void clear ()
 Erases all of the elements. O(n) (Associative Container LOGN)
void destroy ()
 Deletes and erases all of the pointer elements. O(n) (Destructive Associative Container LOGN)
iterator erase (const iterator &where)
 Erases the element pointed to by where. O(logn) (Associative Container LOGN)
iterator destroy (const iterator &where)
 Deletes and erases the pointer element pointed to by where. O(logn) (Destructive Associative Container LOGN)
iterator erase (const iterator &first, const iterator &last)
 Erases all elements in a range. O(n) (Associative Container LOGN)
iterator destroy (const iterator &first, const iterator &last)
 Deletes and erases all pointer elements in a range. O(n) (Destructive Associative Container LOGN)
size_type erase (const key_type &keyval)
 Erases the element whose key is keyval. O(logn) (Associative Container LOGN)
size_type destroy (const key_type &keyval)
 Deletes and erases the element whose key is keyval. O(logn) (Destructive Associative Container LOGN)
iterator erase_index (size_type index)
 Erases the element at the specified index. O(logn)
iterator destroy_index (size_type index)
 Deletes and erases the element at the specified index. O(logn)
void swap (container_type &right)
 Swaps the contents of two lists. O(1) (Container)
template<class Pr1 >
void erase_if (Pr1 pred)
 Erases all elements where pred(*where) is true. O(n)
template<class Pr4 >
void destroy_if (Pr4 pred)
 Destroys all elements where pred(*where) is true. O(n)
void cut (const iterator &first, const iterator &last, container_type &right)
 Extract nodes in the specified range [first,last) into right. O(logn)
mapped_type_reference operator[] (size_type index)
 Returns a reference to the element located at the specified index. O(logn) (Random Access Container LOGN)
const_mapped_type_reference operator[] (size_type index) const
 Returns a reference to the element located at the specified index. O(logn) (Random Access Container LOGN)
mapped_type_reference at (size_type off)
 Returns a reference to the element located at the specified index. O(logn) (Random Access Container LOGN)
const_mapped_type_reference at (size_type off) const
 Returns a reference to the element located at the specified index. O(logn) (Random Access Container LOGN)
key_compare key_comp () const
 Returns current key comparison predicate. O(1) (Sorted Associative Container)
value_compare value_comp () const
 Returns current value comparison predicate. O(1) (Sorted Associative Container)
size_type max_size () const
 Returns the largest possible size of the list. O(1) (Container)
const key_typekey (const value_type &value) const
 Returns key from within the value. O(1)
mapped_typevalue (value_type &value)
 Returns mapped_type from within the value. O(1)
iterator find (const key_type &keyval)
 Finds an element whose key is keyval. O(logn) (Associative Container LOGN)
const_iterator find (const key_type &keyval) const
 Finds an element whose key is keyval. O(logn) (Associative Container LOGN)
size_type count (const key_type &keyval) const
 Counts the number of elements whose key is keyval. O(logn) (Unique Associative Container)
iterator lower_bound (const key_type &keyval)
 Finds the first element whose key is not less than keyval. O(logn) (Sorted Associative Container)
const_iterator lower_bound (const key_type &keyval) const
 Finds the first element whose key is not less than keyval. O(logn) (Sorted Associative Container)
iterator upper_bound (const key_type &keyval)
 Finds the first element whose key is greater than keyval. O(logn) (Sorted Associative Container)
const_iterator upper_bound (const key_type &keyval) const
 Finds the first element whose key is greater than keyval. O(logn) (Sorted Associative Container)
ipair equal_range (const key_type &keyval)
 Finds a range containing all elements whose key is keyval. O(logn) (Sorted Associative Container)
const_ipair equal_range (const key_type &keyval) const
 Finds a range containing all elements whose key is keyval. O(logn) (Sorted Associative Container)

Private Member Functions

void Init (double probability, unsigned int maxLevel)
 Set probability for number of levels in a new node and maximum number of levels in the entire list. O(1)
node_typeAlloc (unsigned int level, const T &obj)
 Allocate a node and copy object. O(1)
node_typeAlloc (unsigned int level)
 Allocate a dummy node. O(1)
void Free (node_type *item)
 Delete a node. O(1)
unsigned int GenerateRandomLevel () const
 Generate random level number. O(1)
void adjust_levels ()
 Makes sure to reduce the internal number of levels. O(1C)
void scan (const value_type &val) const
 Scan by value. O(logn)
void scan (size_type index) const
 Scan by index. O(logn)
void scan (const node_type *nodex) const
 Scan by node. O(logn)
void scan (const iterator &where) const
 Scan by iterator. O(logn)

Private Attributes

rng
 Random number generator to specify level number of new nodes.
Pr Compare
 LessThan Comparison predicate.
unsigned int maxLevel
 Maximum number of levels possible for forward pointers.
unsigned int level
 The maximum number of levels for forward pointers currently in use on any given node.
node_typehead
 Start node.
node_typetail
 End node.
double probability
 Probability to go to the next level.
size_type items
 Number of items in the list.
size_type scan_index
 Cache index.
std::pair< size_type,
node_type * > * 
update
 Cache.

Friends

class T0
class T1

Detailed Description

template<class T, class Pr = std::less<T>, class R = RNG>
class AutoSkipList< T, Pr, R >

Random Access Double Linked SkipList that acts like a set where items are automatically indexed.

Iterators for skiplist can never be completely invalidated unless the element for that iterator is erased. If you insert or remove an element that is located before iterator X, you will need to call X.refresh() to revalidate the iterator. This will simply recalculate the index.

Certain iterator operations do not require the index (ie. do not require revalidation).
For SkipLists that use a key, all iterator comparisons are safe on invalidated iterators.
For SkipLists that don't use a key, less than comparisons (<,<=,>,>=) only work on validated iterators.
For SkipLists that use a key, all increment and decrement operations are safe on invalidated iterators.
For SkipLists that do not have a key and only have an index, incrementing is always safe on invalidated iterators.
For SkipLists that do not have a key and only have an index, decrementing is safe on invalidated iterators on lists that use reverse pointers. Invalidated iterators for IndexedSSkipList (note the extra S) cannot decrement without refreshing first.
Random access always requires a validated iterator.
Distance between two iterators always requires two validated iterators.
Accessing an element via an iterator is always safe.
Equality comparisons (==,!=) are always safe.

Asymptotic worst case performance are specified for each method. The following performances are possible.

Note that updating the list will always require from 1 to logn operations since there are between 1 to logn levels. In the performance specifications, updating all levels of the list for a single node is stated as O(1) since there will always be a small finite number of levels. Note that this does NOT include searching for the appropriate nodes to update at each level. This will always take O(logn) and is specified as such.

For example, removing a node from the front of the list will require logn operations, yet it is specified as O(1) because only a small finite amount of forward pointers need be updated which are readily available. But deleting in the middle of the list would require searching for the forward pointers that need updating and this would be indicated as O(logn).

It is up to the user to take these differences into account and use O(logn) OR O(1) as required when operations work on elements at the front or end of the list as well as any other time where all forward pointers are readily available. Also note that caching is enabled which will also speed up many operations.

The operations that are marked O(1), but take logn operations will be indicated as O(1C)


Member Typedef Documentation

template<class T, class Pr = std::less<T>, class R = RNG>
typedef ptrdiff_t AutoSkipList< T, Pr, R >::difference_type

A signed integral type used to represent the distance between two of the container's iterators. (Container)

This type must be the same as the iterator's distance type.

template<class T, class Pr = std::less<T>, class R = RNG>
typedef T0 AutoSkipList< T, Pr, R >::iterator

The type of iterator used to iterate through a container's elements. (Container)

The iterator's value type is expected to be the container's value type. A conversion from the iterator type to the const iterator type must exist. The iterator type must be an input iterator.

template<class T, class Pr = std::less<T>, class R = RNG>
typedef std::reverse_iterator<iterator> AutoSkipList< T, Pr, R >::reverse_iterator

A Reverse Iterator adaptor whose base iterator type is the container's iterator type. (Reversible Container)

Incrementing an object of type reverse_iterator moves backwards through the container: the Reverse Iterator adaptor maps operator++ to operator--.


Constructor & Destructor Documentation

template<class T, class Pr = std::less<T>, class R = RNG>
AutoSkipList< T, Pr, R >::AutoSkipList ( ) [inline]

Default Constructor O(1) (Container)

Probability is 0.25. Maximum level is set to 8.

template<class T, class Pr = std::less<T>, class R = RNG>
AutoSkipList< T, Pr, R >::AutoSkipList ( size_type  maxNodes) [inline, explicit]

Constructor O(1)

Probability is 0.25. Automatically generate probability based on maximum number of nodes.

Parameters:
maxNodesNumber of nodes to calculate maximum level for this list.
template<class T, class Pr = std::less<T>, class R = RNG>
AutoSkipList< T, Pr, R >::AutoSkipList ( double  probability,
unsigned int  maxLevel 
) [inline]

Constructor O(1)

Parameters:
probabilityProbability for number of levels in a new node.
maxLevelMaxmimum number of levels for this list.
template<class T, class Pr = std::less<T>, class R = RNG>
AutoSkipList< T, Pr, R >::AutoSkipList ( const container_type source) [inline]

Copy Constructor O(n*logn) (Container)

TODO: This could be recoded to be O(n).

Parameters:
sourceAutoSkipList to copy from.
template<class T, class Pr = std::less<T>, class R = RNG>
template<class InIt >
AutoSkipList< T, Pr, R >::AutoSkipList ( InIt  first,
InIt  last 
) [inline]

Constructor O(n*logn) (Unique Sorted Associative Container)

Probability is 0.25. Maximum level is set to 8.

Parameters:
firstiterator to first element to copy.
lastiterator just beyond last element to copy.
template<class T, class Pr = std::less<T>, class R = RNG>
template<class InIt >
AutoSkipList< T, Pr, R >::AutoSkipList ( InIt  first,
InIt  last,
double  probability,
unsigned int  maxLevel 
) [inline]

Constructor O(n*logn) (Unique Sorted Associative Container w/probability)

Parameters:
firstiterator to first element to copy.
lastiterator just beyond last element to copy.
probabilityProbability for number of levels in a new node.
maxLevelMaxmimum number of levels for this list.
template<class T, class Pr = std::less<T>, class R = RNG>
template<class InIt >
AutoSkipList< T, Pr, R >::AutoSkipList ( InIt  first,
InIt  last,
size_type  maxNodes 
) [inline]

Constructor O(n*logn) (Unique Sorted Associative Container w/ probability)

Probability is 0.25. Automatically generate probability based on maximum number of nodes.

Parameters:
firstiterator to first element to copy.
lastiterator just beyond last element to copy.
maxNodesNumber of nodes to calculate maximum level for this list.
template<class T, class Pr = std::less<T>, class R = RNG>
AutoSkipList< T, Pr, R >::AutoSkipList ( const key_compare comp) [inline, explicit]

Constructor O(1) (Sorted Associative Container)

Probability is 0.25. Maximum level is set to 8.

Parameters:
compPredicate for LessThan comparison.
template<class T, class Pr = std::less<T>, class R = RNG>
template<class InIt >
AutoSkipList< T, Pr, R >::AutoSkipList ( InIt  first,
InIt  last,
const key_compare comp 
) [inline]

Constructor O(n*logn) (Unique Sorted Associative Container)

Probability is 0.25. Maximum level is set to 8.

Parameters:
firstiterator to first element to copy.
lastiterator just beyond last element to copy.
compPredicate for LessThan comparison.
template<class T, class Pr = std::less<T>, class R = RNG>
template<class InIt >
AutoSkipList< T, Pr, R >::AutoSkipList ( InIt  first,
InIt  last,
const key_compare comp,
double  probability,
unsigned int  maxLevel 
) [inline]

Constructor O(n*logn) (Unique Sorted Associative Container w/ probability)

Parameters:
firstiterator to first element to copy.
lastiterator just beyond last element to copy.
compPredicate for LessThan comparison.
probabilityProbability for number of levels in a new node.
maxLevelMaxmimum number of levels for this list.
template<class T, class Pr = std::less<T>, class R = RNG>
template<class InIt >
AutoSkipList< T, Pr, R >::AutoSkipList ( InIt  first,
InIt  last,
const key_compare comp,
size_type  maxNodes 
) [inline]

Constructor O(n*logn) (Unique Sorted Associative Container w/ probability)

Probability is 0.25. Automatically generate probability based on maximum number of nodes.

Parameters:
firstiterator to first element to copy.
lastiterator just beyond last element to copy.
compPredicate for LessThan comparison.
maxNodesNumber of nodes to calculate maximum level for this list.
template<class T, class Pr = std::less<T>, class R = RNG>
AutoSkipList< T, Pr, R >::~AutoSkipList ( ) [inline]

Destructor O(n) (Container)

Clears list.


Member Function Documentation

template<class T, class Pr = std::less<T>, class R = RNG>
void AutoSkipList< T, Pr, R >::Init ( double  probability,
unsigned int  maxLevel 
) [inline, private]

Set probability for number of levels in a new node and maximum number of levels in the entire list. O(1)

Parameters:
probabilityProbability for number of levels in a new node.
maxLevelMaxmimum number of levels for this list.
template<class T, class Pr = std::less<T>, class R = RNG>
node_type* AutoSkipList< T, Pr, R >::Alloc ( unsigned int  level,
const T &  obj 
) [inline, private]

Allocate a node and copy object. O(1)

Parameters:
levelNumber of levels for this node.
objObject to store in this node.
Returns:
The allocated node.
template<class T, class Pr = std::less<T>, class R = RNG>
node_type* AutoSkipList< T, Pr, R >::Alloc ( unsigned int  level) [inline, private]

Allocate a dummy node. O(1)

Parameters:
levelNumber of levels for this node.
Returns:
The allocated node.
template<class T, class Pr = std::less<T>, class R = RNG>
void AutoSkipList< T, Pr, R >::Free ( node_type item) [inline, private]

Delete a node. O(1)

Parameters:
itemNode to delete.
template<class T, class Pr = std::less<T>, class R = RNG>
unsigned int AutoSkipList< T, Pr, R >::GenerateRandomLevel ( ) const [inline, private]

Generate random level number. O(1)

Returns:
Random level number.
template<class T, class Pr = std::less<T>, class R = RNG>
void AutoSkipList< T, Pr, R >::scan ( const value_type val) const [inline, private]

Scan by value. O(logn)

This will update the cache so that all levels point to the item just before val. This allows the list to be updated.

Parameters:
valValue to search.
template<class T, class Pr = std::less<T>, class R = RNG>
void AutoSkipList< T, Pr, R >::scan ( size_type  index) const [inline, private]

Scan by index. O(logn)

This will update the cache so that all levels point to the item just before index. This allows the list to be updated.

Parameters:
indexIndex to search.
template<class T, class Pr = std::less<T>, class R = RNG>
void AutoSkipList< T, Pr, R >::scan ( const node_type nodex) const [inline, private]

Scan by node. O(logn)

This will update the cache so that all levels point to the item just before nodex. This allows the list to be updated.

Parameters:
nodexNode to search.
template<class T, class Pr = std::less<T>, class R = RNG>
void AutoSkipList< T, Pr, R >::scan ( const iterator where) const [inline, private]

Scan by iterator. O(logn)

This will update the cache so that all levels point to the item just before where. This allows the list to be updated. This will invoke a scan by index.

Parameters:
whereIterator location to search.
template<class T, class Pr = std::less<T>, class R = RNG>
container_type& AutoSkipList< T, Pr, R >::operator= ( const container_type source) [inline]

Assignment Operator O(n) (Container)

Clears current list and copies source elements to current list.

Parameters:
sourcelist to copy from.
Returns:
reference to current list.
template<class T, class Pr = std::less<T>, class R = RNG>
iterator AutoSkipList< T, Pr, R >::begin ( ) [inline]

Returns an iterator pointing to the beginning of the list. O(1) (Container)

Returns:
iterator pointing to the beginning of the list.
template<class T, class Pr = std::less<T>, class R = RNG>
iterator AutoSkipList< T, Pr, R >::end ( ) [inline]

Returns an iterator pointing to the end of the list. O(1) (Container)

Returns:
iterator pointing to the end of the list.
template<class T, class Pr = std::less<T>, class R = RNG>
const_iterator AutoSkipList< T, Pr, R >::begin ( ) const [inline]

Returns a const_iterator pointing to the beginning of the list. O(1) (Container)

Returns:
const_iterator pointing to the beginning of the list.
template<class T, class Pr = std::less<T>, class R = RNG>
const_iterator AutoSkipList< T, Pr, R >::end ( ) const [inline]

Returns a const_iterator pointing to the end of the list. O(1) (Container)

Returns:
const_iterator pointing to the end of the list.
template<class T, class Pr = std::less<T>, class R = RNG>
reverse_iterator AutoSkipList< T, Pr, R >::rbegin ( ) [inline]

Returns a reverse_iterator pointing to the beginning of the reversed list. O(1) (Reversible Container)

Returns:
reverse_iterator pointing to the beginning of the list.
template<class T, class Pr = std::less<T>, class R = RNG>
reverse_iterator AutoSkipList< T, Pr, R >::rend ( ) [inline]

Returns a reverse_iterator pointing to the end of the reversed list. O(1) (Reversible Container)

Returns:
reverse_iterator pointing to the end of the list.
template<class T, class Pr = std::less<T>, class R = RNG>
const_reverse_iterator AutoSkipList< T, Pr, R >::rbegin ( ) const [inline]

Returns a const_reverse_iterator pointing to the beginning of the reversed list. O(1) (Reversible Container)

Returns:
const_reverse_iterator pointing to the beginning of the list.
template<class T, class Pr = std::less<T>, class R = RNG>
const_reverse_iterator AutoSkipList< T, Pr, R >::rend ( ) const [inline]

Returns a reverse_iterator pointing to the end of the reversed list. O(1) (Reversible Container)

Returns:
reverse_iterator pointing to the end of the list.
template<class T, class Pr = std::less<T>, class R = RNG>
size_type AutoSkipList< T, Pr, R >::size ( ) const [inline]

Returns the size of the list. O(1) (Container)

Returns:
size of the list.
template<class T, class Pr = std::less<T>, class R = RNG>
bool AutoSkipList< T, Pr, R >::empty ( ) const [inline]

Returns true if the list's size is 0. O(1) (Container)

Returns:
true if the list's size is 0, false otherwise.
template<class T, class Pr = std::less<T>, class R = RNG>
reference AutoSkipList< T, Pr, R >::front ( ) [inline]

Returns the first element. O(1) (Front Access Container)

Returns:
the first element.
template<class T, class Pr = std::less<T>, class R = RNG>
const_reference AutoSkipList< T, Pr, R >::front ( ) const [inline]

Returns the first element. O(1) (Front Access Container)

Returns:
the first element.
template<class T, class Pr = std::less<T>, class R = RNG>
reference AutoSkipList< T, Pr, R >::back ( ) [inline]

Returns the last element. O(1) (Back Access Container)

Returns:
the last element.
template<class T, class Pr = std::less<T>, class R = RNG>
const_reference AutoSkipList< T, Pr, R >::back ( ) const [inline]

Returns the last element. O(1) (Back Access Container)

Returns:
the last element.
template<class T, class Pr = std::less<T>, class R = RNG>
template<class InIt >
void AutoSkipList< T, Pr, R >::assign ( InIt  first,
InIt  last 
) [inline]

Clear list and copy element in iterator range [first,last) O(n*logn).

Parameters:
firstiterator at beginning of copy range.
lastiterator just beyond the end of copy range.
template<class T, class Pr = std::less<T>, class R = RNG>
slpair AutoSkipList< T, Pr, R >::insert ( const value_type val) [inline]

Inserts value into the list O(logn). (Unique Associative Container)

Attempts to locate an element with the same ordering as val. if it is not found, a new element initialized with val is inserte into the list. In either case, an iterator where is designated for the element. If an insertion occurred, pair(where,true) is returned. Otherwise, pair(where,false) is returned.

Parameters:
valvalue to insert.
Returns:
pair with insertion results.
template<class T, class Pr = std::less<T>, class R = RNG>
iterator AutoSkipList< T, Pr, R >::insert ( const iterator where,
const value_type val 
) [inline]

Inserts value into the list. O(logn) (Unique Sorted Associative Container)

DO NOT USE THIS.

Returns:
insert(val).first
See also:
insert(const value_type& val)
template<class T, class Pr = std::less<T>, class R = RNG>
template<class InIt >
void AutoSkipList< T, Pr, R >::insert ( InIt  first,
InIt  last 
) [inline]

Inserts values from the range [first,last) into the list by calling insert(*where). O(n*logn) (Unique Sorted Associative Container)

Parameters:
firstiterator to first element to copy.
lastiterator just beyond last element to copy.
template<class T, class Pr = std::less<T>, class R = RNG>
iterator AutoSkipList< T, Pr, R >::erase ( const iterator first,
const iterator last 
) [inline]

Erases all elements in a range. O(n) (Associative Container LOGN)

iterator last will remain valid after the call.

Parameters:
firstiterator to first element to erase.
lastiterator just beyond last element to erase.
Returns:
first element beyond range (last).
template<class T, class Pr = std::less<T>, class R = RNG>
iterator AutoSkipList< T, Pr, R >::destroy ( const iterator first,
const iterator last 
) [inline]

Deletes and erases all pointer elements in a range. O(n) (Destructive Associative Container LOGN)

iterator last will remain valid after the call.

Parameters:
firstiterator to first pointer element to destroy.
lastiterator just beyond last pointer element to destroy.
Returns:
first element beyond range (last).
template<class T, class Pr = std::less<T>, class R = RNG>
size_type AutoSkipList< T, Pr, R >::erase ( const key_type keyval) [inline]

Erases the element whose key is keyval. O(logn) (Associative Container LOGN)

Parameters:
keyvalkey of element to erase.
Returns:
number of elements that were erased (0 or 1).
template<class T, class Pr = std::less<T>, class R = RNG>
size_type AutoSkipList< T, Pr, R >::destroy ( const key_type keyval) [inline]

Deletes and erases the element whose key is keyval. O(logn) (Destructive Associative Container LOGN)

Parameters:
keyvalkey of element to destroy.
Returns:
number of elements that were destroyed (0 or 1).
template<class T, class Pr = std::less<T>, class R = RNG>
iterator AutoSkipList< T, Pr, R >::erase_index ( size_type  index)

Erases the element at the specified index. O(logn)

Parameters:
indexindex of element to erase.
Returns:
iterator following the erased element.
template<class T, class Pr = std::less<T>, class R = RNG>
iterator AutoSkipList< T, Pr, R >::destroy_index ( size_type  index)

Deletes and erases the element at the specified index. O(logn)

Parameters:
indexindex of element to destroy.
Returns:
iterator following the destroyed element.
template<class T, class Pr = std::less<T>, class R = RNG>
void AutoSkipList< T, Pr, R >::swap ( container_type right) [inline]

Swaps the contents of two lists. O(1) (Container)

Parameters:
rightlist with which to swap contents.
template<class T, class Pr = std::less<T>, class R = RNG>
template<class Pr1 >
void AutoSkipList< T, Pr, R >::erase_if ( Pr1  pred)

Erases all elements where pred(*where) is true. O(n)

Parameters:
predPredicate
template<class T, class Pr = std::less<T>, class R = RNG>
template<class Pr4 >
void AutoSkipList< T, Pr, R >::destroy_if ( Pr4  pred)

Destroys all elements where pred(*where) is true. O(n)

Parameters:
predPredicate
template<class T, class Pr = std::less<T>, class R = RNG>
void AutoSkipList< T, Pr, R >::cut ( const iterator first,
const iterator last,
container_type right 
)

Extract nodes in the specified range [first,last) into right. O(logn)

This method works directly on nodes. If the current level number is greater than the maximum level number of right, a level_exception will be thrown.

Container right will be cleared before extraction begins.

Parameters:
firstiterator to first node to extract.
lastiterator just beyond last node to extract.
rightdestination list to hold extracted range.
template<class T, class Pr = std::less<T>, class R = RNG>
mapped_type_reference AutoSkipList< T, Pr, R >::operator[] ( size_type  index) [inline]

Returns a reference to the element located at the specified index. O(logn) (Random Access Container LOGN)

If index is invalid, behaviour is undefined.

Parameters:
indexindex of element to retrieve.
Returns:
element at specified index.
template<class T, class Pr = std::less<T>, class R = RNG>
const_mapped_type_reference AutoSkipList< T, Pr, R >::operator[] ( size_type  index) const [inline]

Returns a reference to the element located at the specified index. O(logn) (Random Access Container LOGN)

If index is invalid, behaviour is undefined.

Parameters:
indexindex of element to retrieve.
Returns:
element at specified index.
template<class T, class Pr = std::less<T>, class R = RNG>
mapped_type_reference AutoSkipList< T, Pr, R >::at ( size_type  off) [inline]

Returns a reference to the element located at the specified index. O(logn) (Random Access Container LOGN)

If index is invalid, out_of_range exception is thrown.

Parameters:
offindex of element to retrieve.
Returns:
element at specified index.
template<class T, class Pr = std::less<T>, class R = RNG>
const_mapped_type_reference AutoSkipList< T, Pr, R >::at ( size_type  off) const [inline]

Returns a reference to the element located at the specified index. O(logn) (Random Access Container LOGN)

If index is invalid, out_of_range exception is thrown.

Parameters:
offindex of element to retrieve.
Returns:
element at specified index.
template<class T, class Pr = std::less<T>, class R = RNG>
const key_type& AutoSkipList< T, Pr, R >::key ( const value_type value) const [inline]

Returns key from within the value. O(1)

For SkipLists that act like a set, the key, value and mapped_type are all the same. For SkipLists that act like a map, the value is a pair. The key is value.first and the mapped_type is value.second.

Parameters:
valuevalue to extract the key from.
template<class T, class Pr = std::less<T>, class R = RNG>
mapped_type& AutoSkipList< T, Pr, R >::value ( value_type value) [inline]

Returns mapped_type from within the value. O(1)

For SkipLists that act like a set, the key, value and mapped_type are all the same. For SkipLists that act like a map, the value is a pair. The key is value.first and the mapped_type is value.second.

Parameters:
valuevalue to extract the mapped_type from.
template<class T, class Pr = std::less<T>, class R = RNG>
iterator AutoSkipList< T, Pr, R >::find ( const key_type keyval) [inline]

Finds an element whose key is keyval. O(logn) (Associative Container LOGN)

Parameters:
keyvalkey of element to find.
Returns:
iterator pointing to element whose key is keyval.
template<class T, class Pr = std::less<T>, class R = RNG>
const_iterator AutoSkipList< T, Pr, R >::find ( const key_type keyval) const [inline]

Finds an element whose key is keyval. O(logn) (Associative Container LOGN)

Parameters:
keyvalkey of element to find.
Returns:
const_iterator pointing to element whose key is keyval.
template<class T, class Pr = std::less<T>, class R = RNG>
size_type AutoSkipList< T, Pr, R >::count ( const key_type keyval) const [inline]

Counts the number of elements whose key is keyval. O(logn) (Unique Associative Container)

Parameters:
keyvalkey of elements to count.
Returns:
amount of elements found.
template<class T, class Pr = std::less<T>, class R = RNG>
iterator AutoSkipList< T, Pr, R >::lower_bound ( const key_type keyval) [inline]

Finds the first element whose key is not less than keyval. O(logn) (Sorted Associative Container)

Parameters:
keyvalkey of element to find.
Returns:
iterator pointing to first element whose key is not less than keyval.
template<class T, class Pr = std::less<T>, class R = RNG>
const_iterator AutoSkipList< T, Pr, R >::lower_bound ( const key_type keyval) const [inline]

Finds the first element whose key is not less than keyval. O(logn) (Sorted Associative Container)

Parameters:
keyvalkey of element to find.
Returns:
iterator pointing to first element whose key is not less than keyval.
template<class T, class Pr = std::less<T>, class R = RNG>
iterator AutoSkipList< T, Pr, R >::upper_bound ( const key_type keyval) [inline]

Finds the first element whose key is greater than keyval. O(logn) (Sorted Associative Container)

Parameters:
keyvalkey of element to find.
Returns:
iterator pointing to first element whose key is greater than keyval.
template<class T, class Pr = std::less<T>, class R = RNG>
const_iterator AutoSkipList< T, Pr, R >::upper_bound ( const key_type keyval) const [inline]

Finds the first element whose key is greater than keyval. O(logn) (Sorted Associative Container)

Parameters:
keyvalkey of element to find.
Returns:
iterator pointing to first element whose key is greater than keyval.
template<class T, class Pr = std::less<T>, class R = RNG>
ipair AutoSkipList< T, Pr, R >::equal_range ( const key_type keyval) [inline]

Finds a range containing all elements whose key is keyval. O(logn) (Sorted Associative Container)

Parameters:
keyvalkey of elements to find.
Returns:
pair containing range.
template<class T, class Pr = std::less<T>, class R = RNG>
const_ipair AutoSkipList< T, Pr, R >::equal_range ( const key_type keyval) const [inline]

Finds a range containing all elements whose key is keyval. O(logn) (Sorted Associative Container)

Parameters:
keyvalkey of elements to find.
Returns:
pair containing range.

The documentation for this class was generated from the following file:
 All Classes Files Functions Variables Typedefs