Doubly-linked list container. More...

#include <List.h>

Classes
class	ConstIterator
	Bidirectional non-mutable List iterator. More...
class	Iterator
	Bidirectional mutable List iterator. More...
class	Node
	List node. More...
Public Member Functions
	List ()
	Constructor.
	List (const MyType &list)
	Copy constructor.
	~List ()
	Destructor.
Iterator	Back ()
	Iterator to the last element.
ConstIterator	Back () const
	Iterator to the last element.
Iterator	Begin ()
	Iterator to the first element.
ConstIterator	Begin () const
	Iterator to the first element.
Iterator	End ()
	Iterator one behind the last element.
ConstIterator	End () const
	Iterator one behind the last element.
Iterator	Erase (Iterator iter)
	Remove element from the list.
void	Free ()
	Free memory occupied by the list.
Iterator	Front ()
	Iterator to the first element.
ConstIterator	Front () const
	Iterator to the first element.
Iterator	InsertAfter (Iterator iter, const T &val)
	Insert element after a given element.
Iterator	InsertBefore (Iterator iter, const T &val)
	Insert element before a given element.
bool	IsEmpty () const
	Check whether the list is empty.
template<class Comp >
MyType &	Merge (MyType &list, Comp comp)
	Merge in elements from a given list.
MyType &	operator= (const MyType &l)
	Assignment operator.
MyType &	PopBack ()
	Remove the last element.
MyType &	PopFront ()
	Remove the first element.
MyType &	PushBack (const T &val)
	Insert element on the tail of the list.
MyType &	PushFront (const T &val)
	Insert element on the beginning of the list.
template<class Pred >
Size	RemoveIf (Pred pred)
	Erase all elements satisfying a given predicate.
MyType &	Reverse ()
	In-place list reverse.
template<class Comp >
MyType &	Sort (Comp comp)
	Sort list.
MyType &	SpliceBefore (Iterator el, MyType &list)
	Splice lists.
MyType &	SpliceBefore (Iterator el, Iterator first)
	Splice lists.
MyType &	SpliceBefore (Iterator el, Iterator first, Iterator last)
	Splice lists.
MyType &	Swap (MyType &l)
	Swap the content of two lists.
template<class Pred >
Size	Unique (Pred pred)
	Erase all elements that satisfy the given predicate with their predecessor.
Protected Types
typedef List< T >	MyType

Detailed Description

template<class T>
class Saf::Collection::List< T >

Doubly-linked list container.

This class implements a data container where each element is stored in its own storage location and the individual locations are interconnected into a doubly-linked list.

The container allows following operations in constant time:

Insertion at front and back of the list: PushFront(), PushBack().
Insertion before or after any element: InsertBefore(), InsertAfter().
Removing front and back elements: PopFront(), PopBack().
Removing arbitrary element: Erase().
Splicing at arbitrary position: SpliceBefore().

The following operations can be performed in linear time:

Removing duplicate elements: Unique().
Removing elements satisfying a certain criterion: RemoveIf().
Reversing element order: Reverse().
Merging: Merge().

Finally, it is possible to efficiently sort the elements in the list using the Sort() method.

Iterator category: Bidirectional.

Template Parameters:

T	Data type.

Warning:: In order to allow constant-time list splicing, the container does not maintain the number of elements in the list. The length can be determined in linear time using the function Saf::Algo::Range::Distance(list.Begin(), list.End()) or tracked manually by the user of the class.

See also:: Collection::ForwardList, Collection::Deque.

Member Typedef Documentation

template<class T>

typedef List<T> Saf::Collection::List< T >::MyType [protected]

Constructor & Destructor Documentation

template<class T>

Saf::Collection::List< T >::List ( ) [inline]

Constructor.

template<class T>

Saf::Collection::List< T >::List ( const MyType & list ) [inline]

Copy constructor.

template<class T>

Saf::Collection::List< T >::~List ( ) [inline]

Destructor.

Member Function Documentation

template<class T>

Iterator Saf::Collection::List< T >::Back ( ) [inline]

Iterator to the last element.

template<class T>

ConstIterator Saf::Collection::List< T >::Back ( ) const [inline]

Iterator to the last element.

template<class T>

Iterator Saf::Collection::List< T >::Begin ( ) [inline]

Iterator to the first element.

template<class T>

ConstIterator Saf::Collection::List< T >::Begin ( ) const [inline]

Iterator to the first element.

template<class T>

Iterator Saf::Collection::List< T >::End ( ) [inline]

Iterator one behind the last element.

template<class T>

ConstIterator Saf::Collection::List< T >::End ( ) const [inline]

Iterator one behind the last element.

template<class T>

Iterator Saf::Collection::List< T >::Erase ( Iterator iter ) [inline]

Remove element from the list.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .
Iterator invalidation: Invalidates only iterators to the deleted element.

Returns:: Iterator to the successor of the erased element.

template<class T>

void Saf::Collection::List< T >::Free ( ) [inline]

Free memory occupied by the list.

template<class T>

Iterator Saf::Collection::List< T >::Front ( ) [inline]

Iterator to the first element.

template<class T>

ConstIterator Saf::Collection::List< T >::Front ( ) const [inline]

Iterator to the first element.

template<class T>

Iterator Saf::Collection::List< T >::InsertAfter	(	Iterator	iter,
		const T &	val
	)		`[inline]`

Insert element after a given element.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .
Iterator invalidation: Does not invalidate any iterators or references.

template<class T>

Iterator Saf::Collection::List< T >::InsertBefore	(	Iterator	iter,
		const T &	val
	)		`[inline]`

Insert element before a given element.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .
Iterator invalidation: Does not invalidate any iterators or references.

template<class T>

bool Saf::Collection::List< T >::IsEmpty ( ) const [inline]

Check whether the list is empty.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .

template<class T>

template<class Comp >

MyType& Saf::Collection::List< T >::Merge	(	MyType &	list,
		Comp	comp
	)		`[inline]`

Merge in elements from a given list.

Both lists are assumed to be sorted according to the predicate Comp.

Properties:

Worst-case time complexity: $\mathcal{O}(\mathrm{Algo::Range::Distance(Begin(), End())})$ .
Iterator invalidation: Does not invalidate any iterators.

Parameters:

[in]	list	List to be merged in.
[in]	comp	Comparison predicate.

template<class T>

MyType& Saf::Collection::List< T >::operator= ( const MyType & l ) [inline]

Assignment operator.

template<class T>

MyType& Saf::Collection::List< T >::PopBack ( ) [inline]

Remove the last element.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .
Iterator invalidation: Does not invalidate any iterators or references.

template<class T>

MyType& Saf::Collection::List< T >::PopFront ( ) [inline]

Remove the first element.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .
Iterator invalidation: Does not invalidate any iterators or references.

template<class T>

MyType& Saf::Collection::List< T >::PushBack ( const T & val ) [inline]

Insert element on the tail of the list.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .
Iterator invalidation: Does not invalidate any iterators or references.

template<class T>

MyType& Saf::Collection::List< T >::PushFront ( const T & val ) [inline]

Insert element on the beginning of the list.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .
Iterator invalidation: Does not invalidate any iterators or references.

template<class T>

template<class Pred >

Size Saf::Collection::List< T >::RemoveIf ( Pred pred ) [inline]

Erase all elements satisfying a given predicate.

Properties:

Worst-case time complexity: $\mathcal{O}(\mathrm{Algo::Range::Distance(Begin(), End())})$ .
Iterator invalidation: Invalidates only iterators to the erased elements.

Returns:: Number of removed elements.

template<class T>

MyType& Saf::Collection::List< T >::Reverse ( ) [inline]

In-place list reverse.

Properties:

Worst-case time complexity: $\mathcal{O}(\mathrm{Algo::Range::Distance(Begin(), End())})$ .
Iterator invalidation: Does not invalidate any iterators.

template<class T>

template<class Comp >

MyType& Saf::Collection::List< T >::Sort ( Comp comp ) [inline]

Sort list.

A merge sort variant is used to sort the list.

Properties:

Worst-case time complexity: $\mathcal{O}(n \log n)$ where $n = \mathrm{Algo::Range::Distance(Begin(), End())}$ .
Iterator invalidation: Does not invalidate any iterators.
Stable sort: Yes.

Parameters:

[in] comp Comparison predicate.

template<class T>

MyType& Saf::Collection::List< T >::SpliceBefore	(	Iterator	el,
		MyType &	list
	)		`[inline]`

Splice lists.

All elements from list are spliced into this list before element el.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .
Iterator invalidation: Does not invalidate any iterators.

template<class T>

MyType& Saf::Collection::List< T >::SpliceBefore	(	Iterator	el,
		Iterator	first
	)		`[inline]`

Splice lists.

Move element first from its original list to this list before element el.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .
Iterator invalidation: Does not invalidate any iterators.

template<class T>

MyType& Saf::Collection::List< T >::SpliceBefore	(	Iterator	el,
		Iterator	first,
		Iterator	last
	)		`[inline]`

Splice lists.

Move the range [first, last) from its original list to this list before element el.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .
Iterator invalidation: Does not invalidate any iterators.

template<class T>

MyType& Saf::Collection::List< T >::Swap ( MyType & l ) [inline]

Swap the content of two lists.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .

template<class T>

template<class Pred >

Size Saf::Collection::List< T >::Unique ( Pred pred ) [inline]

Erase all elements that satisfy the given predicate with their predecessor.

Properties:

Worst-case time complexity: $\mathcal{O}(\mathrm{Algo::Range::Distance(Begin(), End())})$ .
Iterator invalidation: Invalidates only iterators to the erased elements.

Returns:: Number of removed elements.

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

Saf/Collection/List.h

Classes

Public Member Functions

Protected Types

Detailed Description

template<class T> class Saf::Collection::List< T >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

template<class T>
class Saf::Collection::List< T >