Internal container for custom multilist derived from XBidiCompositeSkipList. More...

#include <CSCompositeSkipList.h>

Inheritance diagram for XMultiAutoAccessSkipList< X, K, CT, A, Pr >:

Classes
class	value_compare
	Compares the keys found in two values. (Sorted Associative Container) 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 XMultiAutoAccessSkipList< X, K, CT, A, Pr >	container_type
	Type that represents this internal container.
typedef XIterator0< X, container_type >	T0
	iterator
typedef XIterator1< X, container_type >	T1
	const_iterator
typedef T0	iterator
	The type of iterator used to iterate through a container's elements. (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 CT::value_type	value_type
	The type of the object stored in a container. (Container)
typedef value_type	T
typedef K	key_type
	The list's key type, T. (Associative Container LOGN)
typedef T	mapped_type
	A type identical to value_type (Access Associative Container)
typedef T &	mapped_type_reference
	A type identical to reference (Access Associative Container)
typedef const value_type	const_mapped_type
	A type identical to const value_type (Access Associative Container)
typedef const value_type &	const_mapped_type_reference
	A type identical to const_reference (Access Associative Container)
typedef CT::node_type	node_type
	Internal node type.
typedef value_type *	pointer
	A type that behaves as a pointer to the container's value type. (Container)
typedef value_type &	reference
	A type that behaves as a reference to the container's value type. (Container)
typedef const value_type &	const_reference
	A type that behaves as a const reference to the container's value type. (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 CT::data_type	data_type
	Internal shared data type.
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)
Public Member Functions
	XMultiAutoAcessSkipList ()
	Default Constructor O(1) (Container)
	XMultiAutoAcessSkipList (const key_compare &comp)
	Constructor O(1) (Sorted Associative Container)
	~XMultiAutoAcessSkipList ()
	Destructor O(1) (Container)
void	setData (void *data)
	Set shared data. (Never call this) O(1)
data_type *	getData ()
	Returns shared data used by this internal container. O(1)
container_type &	operator= (const container_type &source)
	Assignment Operator *O(mnlogn)* (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(mlogn)** (Front Access Container)
void	destroy_front ()
	Deletes the first pointer element. *O(mlogn)** (Front Access Container)
void	pop_back ()
	Removes the last element. *O(mlogn)** (Back Access Container)
void	destroy_back ()
	Deletes the last pointer element. *O(mlogn)** (Back Access Container)
template<class InIt >
void	assign (InIt first, InIt last)
	Clear list and copy element in iterator range [first,last) *O(mnlogn)*.
iterator	insert (const value_type &val)
	Inserts value into the list *O(mlogn)**. (Multiple Associative Container)
iterator	insert (const iterator &where, const value_type &val)
	Inserts value into the list. *O(mlogn)** (Multiple 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(mnlogn)* (Multiple Sorted Associative Container)
iterator	erase (const iterator &where)
	Erases the element pointed to by where. *O(mlogn)** (Associative Container LOGN)
iterator	destroy (const iterator &where)
	Deletes and erases the pointer element pointed to by where. *O(mlogn)** (Destructive Associative Container LOGN)
iterator	erase (const iterator &first, const iterator &last)
	Erases all elements in a range. *O(mnlogn)* (Associative Container LOGN)
iterator	destroy (const iterator &first, const iterator &last)
	Deletes and erases all pointer elements in a range. *O(mnlogn)* (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+k²) (Destructive Associative Container LOGN)
iterator	erase_index (size_type index)
	Erases the element at the specified index. *O(mlogn)**
iterator	destroy_index (size_type index)
	Deletes and erases the element at the specified index. *O(mlogn)**
void	clear ()
	Erases all of the elements. O(m+n) (Associative Container LOGN)
void	destroy ()
	Deletes and erases all of the pointer elements. O(m+n) (Destructive Associative Container LOGN)
void	swap (container_type &right)
	Swaps the contents of two lists. NOT IMPLEMENTED YET!!! *O(mnlogn)* (Container)
template<class Pr1 >
void	erase_if (Pr1 pred)
	Erases all elements where pred(where) is true. O(mnlogn)*
template<class Pr4 >
void	destroy_if (Pr4 pred)
	Destroys all elements where pred(where) is true. O(mnlogn)*
void	unique ()
	Removes all but the first element in every consecutive group of equal elements. *O(mnlogn)*
template<class Pr2 >
void	unique (Pr2 pred)
	Removes all but the first element in every consecutive group of equivalent elements. *O(mnlogn)*
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_type &	key (const value_type &value) const
	Returns key from within the value. O(1)
mapped_type_reference	value (reference value) const
	Returns mapped_type from within the value. O(1)
const_mapped_type_reference	value (const_reference value) const
	Returns const_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) (Associative Container LOGN)
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 Types
typedef std::pair< size_type, node_type * > *	pair_t
	Type for cache entry.
Private Member Functions
void	scan (size_type index) const
	Scan by index current internal container. O(logn)
void	scanAll (size_type index) const
	Scan by index current internal container and update ALL caches. *O(mlogn)**
void	scan (const iterator &where) const
	Scan by iterator current internal container. O(logn)
void	scanAll (const iterator &where) const
	Scan by iterator current internal container and update ALL caches. *O(mlogn)**
void	scan (node_type *nodex)
	Scan by node current internal container. O(logn)
void	scanAll (node_type *nodex)
	Scan by node current internal container and update ALL caches. *O(mlogn)**
void	scan_val (const value_type &val) const
	Scan by value current internal container. O(logn)
void	scanAll_val (const value_type &val) const
	Scan by value current internal container and update ALL caches. *O(mlogn)**
void	scan_val (const key_type &val) const
	Scan by key current internal container. O(logn)
void	scanAll_val (const key_type &val) const
	Scan by key current internal container and update ALL caches. *O(mlogn)**
size_type &	getItems ()
	Returns reference to number of elements in container.
void	setItems (const size_type sz)
	Updates the number of elements in container.
std::pair< size_type, node_type * > *	getUpdate ()
	Returns current cache array for this internal container.
size_type	getScanIndex () const
	Returns cache index for this internal container.
void	setScanIndex (const size_type sz)
	Sets current cache index for this internal container.
Private Attributes
data_type *	data
	Internal shared data.
A	a
	Predicate to read the key.
key_compare	KeyCompare
	LessThan Comparison predicate.
value_compare	ValueCompare
	LessThan Comparison predicate.
Friends
class	XIterator0< X, container_type >
class	XIterator1< X, container_type >

Detailed Description

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

Internal container for custom multilist derived from XBidiCompositeSkipList.

Almost identical to MultiAutoAccessSkipList in functionality. Only default constructors available.

Acts much like a map where elements are automatically indexed. IOW, it's a sorted random access container accessible in logn time where the key is a member of the element.

Template Parameters:

X	Index of the internal container within data_type for this iterator.
K	Key type.
CT	Type of custom composite container.
A	Predicate to access the key from CT::value_type.
Pr	Predicate for sorting elements.

Member Typedef Documentation

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

typedef ptrdiff_t XMultiAutoAccessSkipList< X, K, CT, A, Pr >::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<unsigned int X, class K , class CT , class A = XAccessSelf<K,typename CT::value_type>, class Pr = std::less<K>>

typedef T0 XMultiAutoAccessSkipList< X, K, CT, A, Pr >::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<unsigned int X, class K , class CT , class A = XAccessSelf<K,typename CT::value_type>, class Pr = std::less<K>>

typedef CT::value_type XMultiAutoAccessSkipList< X, K, CT, A, Pr >::value_type

The type of the object stored in a container. (Container)

The value type must be Assignable, but need not be DefaultConstructible.

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

typedef std::reverse_iterator<iterator> XMultiAutoAccessSkipList< X, K, CT, A, Pr >::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--.

Member Function Documentation

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

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::scan ( size_type index ) const [inline, private]

Scan by index current internal container. 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.

Only the current internal container is scanned.

Parameters:

index Index to search.

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

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::scanAll ( size_type index ) const [inline, private]

Scan by index current internal container and update ALL caches. O(m*logn)

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

Cache for ALL internal containers are updated.

Parameters:

index Index to search.

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

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::scan ( const iterator & where ) const [inline, private]

Scan by iterator current internal container. 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.

Only the current internal container is scanned.

Parameters:

where Iterator location to search.

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

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::scanAll ( const iterator & where ) const [inline, private]

Scan by iterator current internal container and update ALL caches. O(m*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.

Cache for ALL internal containers are updated.

Parameters:

where Iterator location to search.

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

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::scan ( node_type * nodex ) [inline, private]

Scan by node current internal container. 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.

Only the current internal container is scanned.

Parameters:

nodex Node to search.

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

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::scanAll ( node_type * nodex ) [inline, private]

Scan by node current internal container and update ALL caches. O(m*logn)

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

Cache for ALL internal containers are updated.

Parameters:

nodex Node to search.

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

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::scan_val ( const value_type & val ) const [inline, private]

Scan by value current internal container. 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.

Only the current internal container is scanned.

Parameters:

val	Value to search.

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

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::scanAll_val ( const value_type & val ) const [inline, private]

Scan by value current internal container and update ALL caches. O(m*logn)

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

Cache for ALL internal containers are updated.

Parameters:

val	Value to search.

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

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::scan_val ( const key_type & val ) const [inline, private]

Scan by key current internal container. 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.

Only the current internal container is scanned.

Parameters:

val	Value to search.

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

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::scanAll_val ( const key_type & val ) const [inline, private]

Scan by key current internal container and update ALL caches. O(m*logn)

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

Cache for ALL internal containers are updated.

Parameters:

val	Value to search.

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

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::setItems ( const size_type sz ) [inline, private]

Updates the number of elements in container.

Parameters:

sz	New size of list.

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

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::setScanIndex ( const size_type sz ) [inline, private]

Sets current cache index for this internal container.

Parameters:

sz	New cache index.

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

XMultiAutoAccessSkipList< X, K, CT, A, Pr >::XMultiAutoAcessSkipList ( const key_compare & comp ) [inline, explicit]

Constructor O(1) (Sorted Associative Container)

Parameters:

comp	Predicate for LessThan comparison.

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

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::setData ( void * data ) [inline, virtual]

Set shared data. (Never call this) O(1)

This is for internal use only to set the shared data. The multilist constructor should invoke data->InitData() instead. The data parameter is void* to allow different shared types.

Parameters:

data	Shared data usually of type XData.

Implements XList< CT::value_type, CT::node_type >.

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

container_type& XMultiAutoAccessSkipList< X, K, CT, A, Pr >::operator= ( const container_type & source ) [inline]

Assignment Operator O(m*n*logn) (Container)

Clears current list and copies source elements to current list.

Parameters:

source list to copy from.

Returns:: reference to current list.

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

iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::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<unsigned int X, class K , class CT , class A = XAccessSelf<K,typename CT::value_type>, class Pr = std::less<K>>

iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::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<unsigned int X, class K , class CT , class A = XAccessSelf<K,typename CT::value_type>, class Pr = std::less<K>>

const_iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::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<unsigned int X, class K , class CT , class A = XAccessSelf<K,typename CT::value_type>, class Pr = std::less<K>>

const_iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::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<unsigned int X, class K , class CT , class A = XAccessSelf<K,typename CT::value_type>, class Pr = std::less<K>>

reverse_iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::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<unsigned int X, class K , class CT , class A = XAccessSelf<K,typename CT::value_type>, class Pr = std::less<K>>

reverse_iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::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<unsigned int X, class K , class CT , class A = XAccessSelf<K,typename CT::value_type>, class Pr = std::less<K>>

const_reverse_iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::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<unsigned int X, class K , class CT , class A = XAccessSelf<K,typename CT::value_type>, class Pr = std::less<K>>

const_reverse_iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::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<unsigned int X, class K , class CT , class A = XAccessSelf<K,typename CT::value_type>, class Pr = std::less<K>>

size_type XMultiAutoAccessSkipList< X, K, CT, A, Pr >::size ( ) const [inline]

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

Returns:: size of the list.

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

bool XMultiAutoAccessSkipList< X, K, CT, A, Pr >::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<unsigned int X, class K , class CT , class A = XAccessSelf<K,typename CT::value_type>, class Pr = std::less<K>>

reference XMultiAutoAccessSkipList< X, K, CT, A, Pr >::front ( ) [inline]

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

Returns:: the first element.

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

const_reference XMultiAutoAccessSkipList< X, K, CT, A, Pr >::front ( ) const [inline]

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

Returns:: the first element.

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

reference XMultiAutoAccessSkipList< X, K, CT, A, Pr >::back ( ) [inline]

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

Returns:: the last element.

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

const_reference XMultiAutoAccessSkipList< X, K, CT, A, Pr >::back ( ) const [inline]

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

Returns:: the last element.

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

template<class InIt >

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::assign	(	InIt	first,
		InIt	last
	)		`[inline]`

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

For non-sorted, indexed internal containers, the elements are inserted at the end of the list. For sorted internal containers, the elements are inserted at the proper location.

Parameters:

first	iterator at beginning of copy range.
last	iterator just beyond the end of copy range.

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

iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::insert ( const value_type & val ) [inline]

Inserts value into the list O(m*logn). (Multiple Associative Container)

Parameters:

val	value to insert.

Returns:: iterator that points to the inserted element.

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

iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::insert	(	const iterator &	where,
		const value_type &	val
	)		`[inline]`

Inserts value into the list. O(m*logn) (Multiple Sorted Associative Container)

DO NOT USE THIS.

Returns:: insert(val)

See also:: insert(const value_type& val)

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

template<class InIt >

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::insert	(	InIt	first,
		InIt	last
	)		`[inline]`

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

Parameters:

first	iterator to first element to copy.
last	iterator just beyond last element to copy.

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

iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::erase ( const iterator & where ) [inline]

Erases the element pointed to by where. O(m*logn) (Associative Container LOGN)

Parameters:

where Iterator that points to element to erase.

Returns:: iterator located after the element that was erased.

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

iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::destroy ( const iterator & where ) [inline]

Deletes and erases the pointer element pointed to by where. O(m*logn) (Destructive Associative Container LOGN)

Parameters:

where Iterator that points to element to destroy.

Returns:: iterator located after the element that was destroyed.

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

iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::erase	(	const iterator &	first,
		const iterator &	last
	)		`[inline]`

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

iterator last will remain valid after the call.

Parameters:

first	iterator to first element to erase.
last	iterator just beyond last element to erase.

Returns:: first element beyond range (last).

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

iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::destroy	(	const iterator &	first,
		const iterator &	last
	)		`[inline]`

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

iterator last will remain valid after the call.

Parameters:

first	iterator to first pointer element to destroy.
last	iterator just beyond last pointer element to destroy.

Returns:: first element beyond range (last).

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

size_type XMultiAutoAccessSkipList< X, K, CT, A, Pr >::erase ( const key_type & keyval ) [inline]

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

Parameters:

keyval key of element to erase.

Returns:: number of elements that were erased.

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

size_type XMultiAutoAccessSkipList< X, K, CT, A, Pr >::destroy ( const key_type & keyval ) [inline]

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

Parameters:

keyval key of element to destroy.

Returns:: number of elements that were destroyed.

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

iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::erase_index ( size_type index )

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

Parameters:

index index of element to erase.

Returns:: iterator following the erased element.

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

iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::destroy_index ( size_type index )

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

Parameters:

index index of element to destroy.

Returns:: iterator following the destroyed element.

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

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::swap ( container_type & right ) [inline]

Swaps the contents of two lists. NOT IMPLEMENTED YET!!! O(m*n*logn) (Container)

Parameters:

right list with which to swap contents.

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

template<class Pr1 >

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::erase_if ( Pr1 pred )

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

The relative order of elements that are not erased is unchanged, and iterators to elements that are not erased remain partially valid.

Parameters:

pred Predicate

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

template<class Pr4 >

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::destroy_if ( Pr4 pred )

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

The relative order of elements that are not removed is unchanged, and iterators to elements that are not erased remain partially valid.

Parameters:

pred Predicate

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

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::unique ( ) [inline]

Removes all but the first element in every consecutive group of equal elements. O(m*n*logn)

The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly size() - 1 comparisons for equality. Existing iterators are partially invalidated and a refresh() must be done.

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

template<class Pr2 >

void XMultiAutoAccessSkipList< X, K, CT, A, Pr >::unique ( Pr2 pred ) [inline]

Removes all but the first element in every consecutive group of equivalent elements. O(m*n*logn)

Two elements *i and *j are considered equivalent if pred(*i, *j) is true. The relative order of elements that are not removed remain valid. it performs exactly size() - 1 comparisons for equality. Existing iterators are partially invalidated and a refresh() must be done.

Parameters:

pred	Comparison predicate.

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

mapped_type_reference XMultiAutoAccessSkipList< X, K, CT, A, Pr >::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:

index index of element to retrieve.

Returns:: element at specified index.

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

const_mapped_type_reference XMultiAutoAccessSkipList< X, K, CT, A, Pr >::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:

index index of element to retrieve.

Returns:: element at specified index.

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

mapped_type_reference XMultiAutoAccessSkipList< X, K, CT, A, Pr >::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:

off	index of element to retrieve.

Returns:: element at specified index.

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

const_mapped_type_reference XMultiAutoAccessSkipList< X, K, CT, A, Pr >::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:

off	index of element to retrieve.

Returns:: element at specified index.

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

const key_type& XMultiAutoAccessSkipList< X, K, CT, A, Pr >::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. For indexed SkipLists, the key is the value.

Parameters:

value value to extract the key from.

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

mapped_type_reference XMultiAutoAccessSkipList< X, K, CT, A, Pr >::value ( reference value ) const [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. For indexed SkipLists, the mapped_type is the value.

Parameters:

value value to extract the mapped_type from.

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

const_mapped_type_reference XMultiAutoAccessSkipList< X, K, CT, A, Pr >::value ( const_reference value ) const [inline]

Returns const_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. For indexed SkipLists, the mapped_type is the value.

Parameters:

value value to extract the mapped_type from.

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

iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::find ( const key_type & keyval ) [inline]

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

Parameters:

keyval key of element to find.

Returns:: iterator pointing to element whose key is keyval.

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

const_iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::find ( const key_type & keyval ) const [inline]

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

Parameters:

keyval key of element to find.

Returns:: const_iterator pointing to element whose key is keyval.

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

size_type XMultiAutoAccessSkipList< X, K, CT, A, Pr >::count ( const key_type & keyval ) const [inline]

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

Parameters:

keyval key of elements to count.

Returns:: amount of elements found.

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

iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::lower_bound ( const key_type & keyval ) [inline]

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

Parameters:

keyval key of element to find.

Returns:: iterator pointing to first element whose key is not less than keyval.

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

const_iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::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:

keyval key of element to find.

Returns:: iterator pointing to first element whose key is not less than keyval.

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

iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::upper_bound ( const key_type & keyval ) [inline]

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

Parameters:

keyval key of element to find.

Returns:: iterator pointing to first element whose key is greater than keyval.

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

const_iterator XMultiAutoAccessSkipList< X, K, CT, A, Pr >::upper_bound ( const key_type & keyval ) const [inline]

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

Parameters:

keyval key of element to find.

Returns:: iterator pointing to first element whose key is greater than keyval.

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

ipair XMultiAutoAccessSkipList< X, K, CT, A, Pr >::equal_range ( const key_type & keyval ) [inline]

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

Parameters:

keyval key of elements to find.

Returns:: pair containing range.

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

const_ipair XMultiAutoAccessSkipList< X, K, CT, A, Pr >::equal_range ( const key_type & keyval ) const [inline]

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

Parameters:

keyval key of elements to find.

Returns:: pair containing range.

The documentation for this class was generated from the following file:

CSCompositeSkipList.h

XMultiAutoAccessSkipList< X, K, CT, A, Pr > Class Template Reference

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Friends

Detailed Description

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

Member Typedef Documentation

Member Function Documentation

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