Simple Application Framework  1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Classes | Public Member Functions | Protected Types
Saf::Collection::List< T > Class Template Reference

Doubly-linked list container. More...

#include <List.h>

List of all members.

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 >
MyTypeMerge (MyType &list, Comp comp)
 Merge in elements from a given list.
MyTypeoperator= (const MyType &l)
 Assignment operator.
MyTypePopBack ()
 Remove the last element.
MyTypePopFront ()
 Remove the first element.
MyTypePushBack (const T &val)
 Insert element on the tail of the list.
MyTypePushFront (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.
MyTypeReverse ()
 In-place list reverse.
template<class Comp >
MyTypeSort (Comp comp)
 Sort list.
MyTypeSpliceBefore (Iterator el, MyType &list)
 Splice lists.
MyTypeSpliceBefore (Iterator el, Iterator first)
 Splice lists.
MyTypeSpliceBefore (Iterator el, Iterator first, Iterator last)
 Splice lists.
MyTypeSwap (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:

The following operations can be performed in linear time:

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

Iterator category: Bidirectional.

Template Parameters:
TData 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]listList to be merged in.
[in]compComparison 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]compComparison 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: