Singly-linked list container. More...

#include <ForwardList.h>

Classes
class	ConstIterator
	Forward non-mutable ForwardList iterator. More...
class	Iterator
	Forward mutable ForwardList iterator. More...
class	Node
	List node. More...
Public Member Functions
	ForwardList ()
	Constructor.
	ForwardList (const MyType &list)
	Copy constructor.
	~ForwardList ()
	Destructor.
Iterator	Back ()
	Iterator to the first element.
ConstIterator	Back () const
	Iterator to the first element.
Iterator	BeforeBegin ()
	Iterator just before the first element.
ConstIterator	BeforeBegin () const
	Iterator just before the first 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	EraseAfter (Iterator iter)
	Remove the element after a given 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.
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 &	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 &	SpliceAfter (Iterator el, MyType &list)
	Splice lists.
MyType &	SpliceAfter (Iterator el, MyType &list, Iterator first)
	Splice lists.
MyType &	SpliceAfter (Iterator el, MyType &list, Iterator first, Iterator last)
	Splice lists.
MyType &	Swap (MyType &fl)
	Swap the content of two forward lists.
template<class Pred >
Size	Unique (Pred pred)
	Erase all elements that satisfy the given predicate with their predecessor.
Protected Types
typedef ForwardList< T >	MyType

Detailed Description

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

Singly-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 singly-linked list. As opposed to List container, ForwardList occupies less memory but it is more limited in terms of capabilities.

This container allows following operations in constant time:

Insertion at front and back of the list: PushFront(), PushBack().
Insertion after arbitrary element: InsertAfter().
Removing front element: PopFront().
Removing element after arbitrary element: EraseAfter().
Splicing: SpliceAfter().

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: Forward.

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::List, Collection::Deque.

Member Typedef Documentation

template<class T>

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

Constructor & Destructor Documentation

template<class T>

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

Constructor.

template<class T>

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

Copy constructor.

template<class T>

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

Destructor.

Member Function Documentation

template<class T>

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

Iterator to the first element.

template<class T>

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

Iterator to the first element.

template<class T>

Iterator Saf::Collection::ForwardList< T >::BeforeBegin ( ) [inline]

Iterator just before the first element.

template<class T>

ConstIterator Saf::Collection::ForwardList< T >::BeforeBegin ( ) const [inline]

Iterator just before the first element.

template<class T>

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

Iterator to the first element.

template<class T>

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

Iterator to the first element.

template<class T>

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

Iterator one behind the last element.

template<class T>

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

Iterator one behind the last element.

template<class T>

Iterator Saf::Collection::ForwardList< T >::EraseAfter ( Iterator iter ) [inline]

Remove the element after a given element from the list.

Properties:

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

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

template<class T>

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

Free memory occupied by the list.

template<class T>

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

Iterator to the first element.

template<class T>

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

Iterator to the first element.

template<class T>

Iterator Saf::Collection::ForwardList< 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.

Returns:: Iterator to the inserted element.

template<class T>

bool Saf::Collection::ForwardList< 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::ForwardList< 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::ForwardList< T >::operator= ( const MyType & l ) [inline]

Assignment operator.

template<class T>

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

Remove the first element.

Properties:

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

template<class T>

MyType& Saf::Collection::ForwardList< 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::ForwardList< 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::ForwardList< 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::ForwardList< 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::ForwardList< 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::ForwardList< T >::SpliceAfter	(	Iterator	el,
		MyType &	list
	)		`[inline]`

Splice lists.

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

Properties:

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

template<class T>

MyType& Saf::Collection::ForwardList< T >::SpliceAfter	(	Iterator	el,
		MyType &	list,
		Iterator	first
	)		`[inline]`

Splice lists.

Splice the element after first into this list after element el.

Properties:

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

template<class T>

MyType& Saf::Collection::ForwardList< T >::SpliceAfter	(	Iterator	el,
		MyType &	list,
		Iterator	first,
		Iterator	last
	)		`[inline]`

Splice lists.

Splice the range (first, last] into this list after element el.

Properties:

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

template<class T>

MyType& Saf::Collection::ForwardList< T >::Swap ( MyType & fl ) [inline]

Swap the content of two forward lists.

Properties:

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

template<class T>

template<class Pred >

Size Saf::Collection::ForwardList< 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/ForwardList.h

Classes

Public Member Functions

Protected Types

Detailed Description

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

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

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