Random Access Double Linked SkipList that acts like a vector. More...

#include <CSIndexedSkipList.h>

Classes
struct	Prob
	Used to initialize probability in list constructor. More...
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 IndexedSkipList< T, R >	container_type
	Type that represents this list.
typedef T	value_type
	The type of the object stored in a container. (Container)
typedef value_type	mapped_type
	A type identical to value_type.
typedef value_type &	mapped_type_reference
	A type identical to reference.
typedef const value_type	const_mapped_type
	A type identical to const value_type.
typedef const value_type &	const_mapped_type_reference
	A type identical to const_reference.
typedef BidiIdxNode< value_type >	node_type
	Internal node type.
typedef T0	iterator
	The type of iterator used to iterate through a container's elements. (Container)
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 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)
Public Member Functions
	IndexedSkipList ()
	Default Constructor O(1) (Container)
	IndexedSkipList (double probability, unsigned int maxLevel)
	Constructor O(1)
	IndexedSkipList (const container_type &source)
	Copy Constructor O(n) (Container)
template<class InIt >
	IndexedSkipList (InIt first, InIt last)
	Constructor O(n) (Sequence)
template<class InIt >
	IndexedSkipList (InIt first, InIt last, double probability, unsigned int maxLevel)
	Constructor O(n) (Sequence w/ probability)
template<class InIt >
	IndexedSkipList (InIt first, InIt last, size_type maxNodes)
	Constructor O(n) (Sequence w/ probability)
	IndexedSkipList (size_type count)
	Constructor O(n) (Sequence)
	IndexedSkipList (size_type count, const T &val)
	Constructor O(n) (Sequence)
	IndexedSkipList (size_type count, const T &val, double probability, unsigned int maxLevel)
	Constructor O(n) (Sequence w/ probability)
	IndexedSkipList (size_type count, const T &val, size_type maxNodes)
	Constructor O(n) (Sequence w/ probability)
	IndexedSkipList (const Prob &prob)
	Constructor O(1)
	IndexedSkipList (size_type count, const Prob &prob)
	Constructor O(n) (Sequence w/ prob)
	IndexedSkipList (size_type count, const T &val, const Prob &prob)
	Constructor O(n) (Sequence w/ prob)
template<class InIt >
	IndexedSkipList (InIt first, InIt last, const Prob &prob)
	Constructor O(n) (Sequence w/ prob)
	~IndexedSkipList ()
	Destructor O(n) (Container)
container_type &	operator= (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 Insertion Sequence)
const_reference	front () const
	Returns the first element. O(1) (Front Insertion Sequence)
reference	back ()
	Returns the last element. O(1) (Back Insertion Sequence)
const_reference	back () const
	Returns the last element. O(1) (Back Insertion Sequence)
void	push_front (const value_type &val)
	Inserts a new element at the beginning. O(1C) (Front Insertion Sequence)
void	pop_front ()
	Removes the first element. O(1C) (Front Insertion Sequence)
void	destroy_front ()
	Deletes the first pointer element. O(1C) (Front Access Container)
void	push_back (const value_type &val)
	Inserts a new element at the end. O(1C) (Back Insertion Sequence)
void	pop_back ()
	Removes the last element. O(1C) (Back Insertion Sequence)
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).
void	assign (size_type count, const T &val)
	Clear list and copy count elements of val. O(n).
iterator	insert (const iterator &where, const value_type &val)
	Inserts a copy of val before where. O(logn). (Sequence)
void	insert (const iterator &where, size_type count, const T &val)
	Inserts count copies of val before where. O(n). (Sequence)
template<class InIt >
void	insert (const iterator &where, InIt first, InIt last)
	Inserts values from the range [first,last) before specified iterator. O(n). (Sequence)
void	clear ()
	Erases all of the elements. O(n) (Sequence)
void	destroy ()
	Deletes and erases all of the pointer elements. O(n)
iterator	erase (const iterator &where)
	Erases the element pointed to by where. O(logn) (Sequence)
iterator	destroy (const iterator &where)
	Deletes and erases the pointer element pointed to by where. O(logn)
iterator	erase (const iterator &first, const iterator &last)
	Erases all elements in a range. O(n) (Sequence)
iterator	destroy (const iterator &first, const iterator &last)
	Deletes and erases all pointer elements in a range. O(n)
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	resize (size_type newsize)
	Inserts or erases elements at the end such that the size becomes newsize. O(n) (Sequence)
void	resize (size_type newsize, const value_type &val)
	Inserts or erases elements at the end such that the size becomes newsize. O(n) (Sequence)
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)
size_type	max_size () const
	Returns the largest possible size of the list. O(1) (Container)
mapped_type &	value (value_type &value)
	Returns mapped_type from within the value. O(1)
void	reverse ()
	Reverse list. O(n)
void	unique ()
	Removes all but the first element in every consecutive group of equal elements. O(n)
template<class Pr2 >
void	unique (Pr2 pred)
	Removes all but the first element in every consecutive group of equivalent elements. O(n)
void	sort ()
	Sorts this according to operator<. O(nlogn)**
template<class Pr3 >
void	sort (Pr3 pred)
	Sorts this according to predicate. O(nlogn)**
void	stable_sort ()
	Sorts this according to operator<. O(nlogn)**
template<class Pr3 >
void	stable_sort (Pr3 pred)
	Sorts this according to predicate. O(nlogn)**
void	erase_value (const value_type &val)
	Erases all elements that compare equal to val. O(n)
void	splice (const iterator &where, container_type &right)
	All of the elements of right are inserted before where and removed from right. O(logn)
void	splice (const iterator &where, container_type &right, iterator first)
	Moves the element pointed to by first from right to this, inserting it before where. O(logn)*
void	splice (const iterator &where, container_type &right, iterator first, iterator last)
	Splice moves the elements in [first, last) from right to this, inserting them before where. O(logn)*
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_type *	Alloc (unsigned int level, const T &obj)
	Allocate a node and copy object. O(1)
node_type *	Alloc (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 (size_type index) const
	Scan by index. O(logn)
void	scan (const iterator &where) const
	Scan by iterator. O(logn)
Private Attributes
R	rng
	Random number generator to specify level number of new nodes.
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_type *	head
	Start node.
node_type *	tail
	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 R = RNG>
class IndexedSkipList< T, R >

Random Access Double Linked SkipList that acts like a vector.

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.

O(1) Constant time.
O(logn) Logarithmic time.
O(n) Linear time.

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 R = RNG>

typedef ptrdiff_t IndexedSkipList< T, 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 R = RNG>

typedef T IndexedSkipList< T, R >::value_type

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

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

template<class T, class R = RNG>

typedef T0 IndexedSkipList< T, 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 R = RNG>

typedef std::reverse_iterator<iterator> IndexedSkipList< T, 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 R = RNG>

IndexedSkipList< T, R >::IndexedSkipList ( ) [inline]

Default Constructor O(1) (Container)

Probability is 0.25. Maximum level is set to 8.

template<class T, class R = RNG>

IndexedSkipList< T, R >::IndexedSkipList	(	double	probability,
		unsigned int	maxLevel
	)		`[inline]`

Constructor O(1)

Parameters:

probability	Probability for number of levels in a new node.
maxLevel	Maxmimum number of levels for this list.

template<class T, class R = RNG>

IndexedSkipList< T, R >::IndexedSkipList ( const container_type & source ) [inline]

Copy Constructor O(n) (Container)

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

Parameters:

source IndexedSkipList to copy from.

template<class T, class R = RNG>

template<class InIt >

IndexedSkipList< T, R >::IndexedSkipList	(	InIt	first,
		InIt	last
	)		`[inline]`

Constructor O(n) (Sequence)

Probability is 0.25. Maximum level is set to 8.

Parameters:

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

template<class T, class R = RNG>

template<class InIt >

IndexedSkipList< T, R >::IndexedSkipList	(	InIt	first,
		InIt	last,
		double	probability,
		unsigned int	maxLevel
	)		`[inline]`

Constructor O(n) (Sequence w/ probability)

Parameters:

first	iterator to first element to copy.
last	iterator just beyond last element to copy.
probability	Probability for number of levels in a new node.
maxLevel	Maxmimum number of levels for this list.

template<class T, class R = RNG>

template<class InIt >

IndexedSkipList< T, R >::IndexedSkipList	(	InIt	first,
		InIt	last,
		size_type	maxNodes
	)		`[inline]`

Constructor O(n) (Sequence w/ probability)

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

Parameters:

first	iterator to first element to copy.
last	iterator just beyond last element to copy.
maxNodes	Number of nodes to calculate maximum level for this list.

template<class T, class R = RNG>

IndexedSkipList< T, R >::IndexedSkipList ( size_type count ) [inline, explicit]

Constructor O(n) (Sequence)

Probability is 0.25. Maximum level is set to 8.

Parameters:

count Creates list with count elements created with default constructor.

template<class T, class R = RNG>

IndexedSkipList< T, R >::IndexedSkipList	(	size_type	count,
		const T &	val
	)		`[inline]`

Constructor O(n) (Sequence)

Probability is 0.25. Maximum level is set to 8.

Parameters:

count	Creates list with count elements.
val	Value to copy for each element created.

template<class T, class R = RNG>

IndexedSkipList< T, R >::IndexedSkipList	(	size_type	count,
		const T &	val,
		double	probability,
		unsigned int	maxLevel
	)		`[inline]`

Constructor O(n) (Sequence w/ probability)

Probability is 0.25. Maximum level is set to 8.

Parameters:

count	Creates list with count elements.
val	Value to copy for each element created.
probability	Probability for number of levels in a new node.
maxLevel	Maxmimum number of levels for this list.

template<class T, class R = RNG>

IndexedSkipList< T, R >::IndexedSkipList	(	size_type	count,
		const T &	val,
		size_type	maxNodes
	)		`[inline]`

Constructor O(n) (Sequence w/ probability)

Probability is 0.25. Maximum level is set to 8.

Parameters:

count	Creates list with count elements.
val	Value to copy for each element created.
maxNodes	Number of nodes to calculate maximum level for this list.

template<class T, class R = RNG>

IndexedSkipList< T, R >::IndexedSkipList ( const Prob & prob ) [inline]

Constructor O(1)

Parameters:

prob	probability for node levels.

template<class T, class R = RNG>

IndexedSkipList< T, R >::IndexedSkipList	(	size_type	count,
		const Prob &	prob
	)		`[inline]`

Constructor O(n) (Sequence w/ prob)

Parameters:

count	Creates list with count elements created with default constructor.
prob	probability for node levels.

template<class T, class R = RNG>

IndexedSkipList< T, R >::IndexedSkipList	(	size_type	count,
		const T &	val,
		const Prob &	prob
	)		`[inline]`

Constructor O(n) (Sequence w/ prob)

Parameters:

count	Creates list with count elements.
val	Value to copy for each element created.
prob	probability for node levels.

template<class T, class R = RNG>

template<class InIt >

IndexedSkipList< T, R >::IndexedSkipList	(	InIt	first,
		InIt	last,
		const Prob &	prob
	)		`[inline]`

Constructor O(n) (Sequence w/ prob)

Parameters:

first	iterator to first element to copy.
last	iterator just beyond last element to copy.
prob	probability for node levels.

template<class T, class R = RNG>

IndexedSkipList< T, R >::~IndexedSkipList ( ) [inline]

Destructor O(n) (Container)

Clears list.

Member Function Documentation

template<class T, class R = RNG>

void IndexedSkipList< T, 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:

probability	Probability for number of levels in a new node.
maxLevel	Maxmimum number of levels for this list.

template<class T, class R = RNG>

node_type* IndexedSkipList< T, R >::Alloc	(	unsigned int	level,
		const T &	obj
	)		`[inline, private]`

Allocate a node and copy object. O(1)

Parameters:

level	Number of levels for this node.
obj	Object to store in this node.

Returns:: The allocated node.

template<class T, class R = RNG>

node_type* IndexedSkipList< T, R >::Alloc ( unsigned int level ) [inline, private]

Allocate a dummy node. O(1)

Parameters:

level Number of levels for this node.

Returns:: The allocated node.

template<class T, class R = RNG>

void IndexedSkipList< T, R >::Free ( node_type * item ) [inline, private]

Delete a node. O(1)

Parameters:

item	Node to delete.

template<class T, class R = RNG>

unsigned int IndexedSkipList< T, R >::GenerateRandomLevel ( ) const [inline, private]

Generate random level number. O(1)

Returns:: Random level number.

template<class T, class R = RNG>

void IndexedSkipList< T, 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:

index Index to search.

template<class T, class R = RNG>

void IndexedSkipList< T, 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:

where Iterator location to search.

template<class T, class R = RNG>

container_type& IndexedSkipList< T, R >::operator= ( const container_type & source ) [inline]

Assignment Operator O(n) (Container)

Clears current list and copies source elements to current list.

Parameters:

source list to copy from.

Returns:: reference to current list.

template<class T, class R = RNG>

iterator IndexedSkipList< T, 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 R = RNG>

iterator IndexedSkipList< T, 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 R = RNG>

const_iterator IndexedSkipList< T, 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 R = RNG>

const_iterator IndexedSkipList< T, 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 R = RNG>

reverse_iterator IndexedSkipList< T, 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 R = RNG>

reverse_iterator IndexedSkipList< T, 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 R = RNG>

const_reverse_iterator IndexedSkipList< T, 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 R = RNG>

const_reverse_iterator IndexedSkipList< T, 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 R = RNG>

size_type IndexedSkipList< T, R >::size ( ) const [inline]

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

Returns:: size of the list.

template<class T, class R = RNG>

bool IndexedSkipList< T, 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 R = RNG>

reference IndexedSkipList< T, R >::front ( ) [inline]

Returns the first element. O(1) (Front Insertion Sequence)

Returns:: the first element.

template<class T, class R = RNG>

const_reference IndexedSkipList< T, R >::front ( ) const [inline]

Returns the first element. O(1) (Front Insertion Sequence)

Returns:: the first element.

template<class T, class R = RNG>

reference IndexedSkipList< T, R >::back ( ) [inline]

Returns the last element. O(1) (Back Insertion Sequence)

Returns:: the last element.

template<class T, class R = RNG>

const_reference IndexedSkipList< T, R >::back ( ) const [inline]

Returns the last element. O(1) (Back Insertion Sequence)

Returns:: the last element.

template<class T, class R = RNG>

void IndexedSkipList< T, R >::push_front ( const value_type & val ) [inline]

Inserts a new element at the beginning. O(1C) (Front Insertion Sequence)

Parameters:

val	Copy of object to be inserted into the container.

template<class T, class R = RNG>

void IndexedSkipList< T, R >::push_back ( const value_type & val ) [inline]

Inserts a new element at the end. O(1C) (Back Insertion Sequence)

Parameters:

val	Copy of object to be inserted into the container.

template<class T, class R = RNG>

template<class InIt >

void IndexedSkipList< T, R >::assign	(	InIt	first,
		InIt	last
	)		`[inline]`

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

Parameters:

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

template<class T, class R = RNG>

void IndexedSkipList< T, R >::assign	(	size_type	count,
		const T &	val
	)		`[inline]`

Clear list and copy count elements of val. O(n).

Parameters:

count	Creates list with count elements.
val	Value to copy for each element created.

template<class T, class R = RNG>

iterator IndexedSkipList< T, R >::insert	(	const iterator &	where,
		const value_type &	val
	)		`[inline]`

Inserts a copy of val before where. O(logn). (Sequence)

Parameters:

where	value gets inserted before where iterator.
val	value to insert.

Returns:: iterator of inserted element.

template<class T, class R = RNG>

void IndexedSkipList< T, R >::insert	(	const iterator &	where,
		size_type	count,
		const T &	val
	)		`[inline]`

Inserts count copies of val before where. O(n). (Sequence)

Parameters:

where	values gets inserted before where iterator.
count	number of copies to insert.
val	value to insert.

template<class T, class R = RNG>

template<class InIt >

void IndexedSkipList< T, R >::insert	(	const iterator &	where,
		InIt	first,
		InIt	last
	)		`[inline]`

Inserts values from the range [first,last) before specified iterator. O(n). (Sequence)

Parameters:

where	values get inserted before where iterator.
first	iterator to first element to copy.
last	iterator just beyond last element to copy.

template<class T, class R = RNG>

iterator IndexedSkipList< T, R >::erase ( const iterator & where ) [inline]

Erases the element pointed to by where. O(logn) (Sequence)

Parameters:

where Iterator that points to element to erase.

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

template<class T, class R = RNG>

iterator IndexedSkipList< T, R >::destroy ( const iterator & where ) [inline]

Deletes and erases the pointer element pointed to by where. O(logn)

Parameters:

where Iterator that points to element to destroy.

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

template<class T, class R = RNG>

iterator IndexedSkipList< T, R >::erase	(	const iterator &	first,
		const iterator &	last
	)		`[inline]`

Erases all elements in a range. O(n) (Sequence)

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<class T, class R = RNG>

iterator IndexedSkipList< T, R >::destroy	(	const iterator &	first,
		const iterator &	last
	)		`[inline]`

Deletes and erases all pointer elements in a range. O(n)

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<class T, class R = RNG>

iterator IndexedSkipList< T, R >::erase_index ( size_type index )

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

Parameters:

index index of element to erase.

Returns:: iterator following the erased element.

template<class T, class R = RNG>

iterator IndexedSkipList< T, R >::destroy_index ( size_type index )

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

Parameters:

index index of element to destroy.

Returns:: iterator following the destroyed element.

template<class T, class R = RNG>

void IndexedSkipList< T, R >::swap ( container_type & right ) [inline]

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

Parameters:

right list with which to swap contents.

template<class T, class R = RNG>

template<class Pr1 >

void IndexedSkipList< T, R >::erase_if ( Pr1 pred )

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

Parameters:

pred Predicate

template<class T, class R = RNG>

template<class Pr4 >

void IndexedSkipList< T, R >::destroy_if ( Pr4 pred )

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

Parameters:

pred Predicate

template<class T, class R = RNG>

void IndexedSkipList< T, 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:

first	iterator to first node to extract.
last	iterator just beyond last node to extract.
right	destination list to hold extracted range.

template<class T, class R = RNG>

mapped_type_reference IndexedSkipList< T, 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:

index index of element to retrieve.

Returns:: element at specified index.

template<class T, class R = RNG>

const_mapped_type_reference IndexedSkipList< T, 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:

index index of element to retrieve.

Returns:: element at specified index.

template<class T, class R = RNG>

mapped_type_reference IndexedSkipList< T, 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:

off	index of element to retrieve.

Returns:: element at specified index.

template<class T, class R = RNG>

const_mapped_type_reference IndexedSkipList< T, 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:

off	index of element to retrieve.

Returns:: element at specified index.

template<class T, class R = RNG>

mapped_type& IndexedSkipList< T, 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. For indexed SkipLists, the mapped_type is the value.

Parameters:

value value to extract the mapped_type from.

template<class T, class R = RNG>

void IndexedSkipList< T, R >::reverse ( ) [inline]

Reverse list. O(n)

Existing iterators are partially invalidated and a refresh() must be done.

template<class T, class R = RNG>

void IndexedSkipList< T, R >::unique ( ) [inline]

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

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<class T, class R = RNG>

template<class Pr2 >

void IndexedSkipList< T, R >::unique ( Pr2 pred ) [inline]

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

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<class T, class R = RNG>

void IndexedSkipList< T, R >::sort ( ) [inline]

Sorts *this according to operator<. O(n*logn)

The sort is not stable, that is, the relative order of equivalent elements is not preserved. All iterators remain valid and continue to point to the same elements. The number of comparisons is approximately N log N, where N is the list's size.

Existing iterators are partially invalidated and a refresh() must be done.

template<class T, class R = RNG>

template<class Pr3 >

void IndexedSkipList< T, R >::sort ( Pr3 pred ) [inline]

Sorts *this according to predicate. O(n*logn)

Pred must be a comparison function that induces a strict weak ordering (as defined in the LessThan Comparable requirements on objects of type T. This function sorts the list *this according to pred. The sort is not stable, that is, the relative order of equivalent elements is not preserved. All iterators remain valid and continue to point to the same elements. The number of comparisons is approximately N log N, where N is the list's size.

Existing iterators are partially invalidated and a refresh() must be done.

Parameters:

pred	Comparison predicate.

template<class T, class R = RNG>

void IndexedSkipList< T, R >::stable_sort ( ) [inline]

Sorts *this according to operator<. O(n*logn)

The sort is stable, that is, the relative order of equivalent elements is preserved. All iterators remain valid and continue to point to the same elements. The number of comparisons is approximately N log N, where N is the list's size.

Existing iterators are partially invalidated and a refresh() must be done.

template<class T, class R = RNG>

template<class Pr3 >

void IndexedSkipList< T, R >::stable_sort ( Pr3 pred ) [inline]

Sorts *this according to predicate. O(n*logn)

Pred must be a comparison function that induces a strict weak ordering (as defined in the LessThan Comparable requirements on objects of type T. This function sorts the list *this according to pred. The sort is stable, that is, the relative order of equivalent elements is preserved. All iterators remain valid and continue to point to the same elements. The number of comparisons is approximately N log N, where N is the list's size.

Parameters:

pred	Comparison predicate.

template<class T, class R = RNG>

void IndexedSkipList< T, R >::erase_value ( const value_type & val ) [inline]

Erases all elements that compare equal to val. O(n)

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() comparisons for equality.

Parameters:

val	Value to remove.

template<class T, class R = RNG>

void IndexedSkipList< T, R >::splice	(	const iterator &	where,
		container_type &	right
	)		`[inline]`

All of the elements of right are inserted before where and removed from right. O(logn)

where must be a valid iterator in *this, and right must be a list that is distinct from *this. (That is, it is required that &x != this.). All iterators remain valid, including iterators that point to elements of x. [3] This function is logn time to find where. After that, all elements in right are inserted and removed in constant time according to O(1C).

Parameters:

where	elements in right will be inserted before where.
right	list to be inserted before where.

template<class T, class R = RNG>

void IndexedSkipList< T, R >::splice	(	const iterator &	where,
		container_type &	right,
		iterator	first
	)		`[inline]`

Moves the element pointed to by first from right to *this, inserting it before where. O(logn)

where must be a valid iterator in *this, and first must be a dereferenceable iterator in right. All iterators remain valid, including iterators that point to elements of right. [3] If where == first or wherep == ++first, this function is a null operation. This function is logn time.

Parameters:

where	elements in right will be inserted before where.
right	source list.
first	element from right to be removed and inserted before where.

template<class T, class R = RNG>

void IndexedSkipList< T, R >::splice	(	const iterator &	where,
		container_type &	right,
		iterator	first,
		iterator	last
	)		`[inline]`

Splice moves the elements in [first, last) from right to *this, inserting them before where. O(logn)

where must be a valid iterator in *this, and [first, last) must be a valid range in right. where may not be an iterator in the range [first, last). All iterators remain valid, including iterators that point to elements of right. [3] This function is constant logn time to find splice locations. After that, all elements are inserted and removed in constant time according to O(1C).

Parameters:

where	elements in right will be inserted before where.
right	source list.
first	start iterator in range [first,last) from right to be removed and inserted before where.
last	end iterator in range [first,last) from right to be removed and inserted before where.

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

CSIndexedSkipList.h

IndexedSkipList< T, R > Class Template Reference

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

template<class T, class R = RNG> class IndexedSkipList< T, R >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

template<class T, class R = RNG>
class IndexedSkipList< T, R >