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

Double-ended queue container. More...

#include <Deque.h>

List of all members.

Classes

class  ConstIterator
 Random-access non-mutable Deque iterator. More...
class  Iterator
 Random-access mutable Deque iterator. More...

Public Member Functions

 Deque (Size elems=0, const T &val=T())
 Default constructor.
 Deque (const MyType &d)
 Copy constructor.
 ~Deque ()
 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.
Size Elements () const
 Get the number of elements stored in the container.
Iterator End ()
 Iterator one behind the last element.
ConstIterator End () const
 Iterator one behind the last element.
void Free ()
 Free memory occupied by the container.
Iterator Front ()
 Iterator to the first element.
ConstIterator Front () const
 Iterator to the first element.
bool IsEmpty () const
 Check if the container is empty.
MyTypeoperator= (const MyType &d)
 Assignment operator.
T & operator[] (Size i)
 Subscript operator.
const T & operator[] (Size i) const
 Subscript operator.
MyTypePopBack ()
 Remove element from the back of the container.
MyTypePopFront ()
 Remove element from the beginning of the container.
MyTypePushBack (const T &val)
 Add new element at the back of the container.
MyTypePushFront (const T &val)
 Add new element at the beginning of the container.
void Shrink ()
 Shrink the container by deallocating unused memory.
MyTypeSwap (MyType &d)
 Swap the content of two Deque arrays.

Protected Types

typedef Deque< T > MyType

Protected Member Functions

void AllocateBlock (T *&block)
 Allocate memory for a given block.
Size BlockIndex (Size ofs) const
 Get block index for a given element offset.
Size BlockOffset (Size ofs) const
 Element offset in a block.
Size BlockSize () const
 Get maximum number of elements in each block.
void ComputeBlockSize ()
 Compute the block size.
T * ElementAt (Size ofs)
 Get pointer to element at given offset.
const T * ElementAt (Size ofs) const
 Get pointer to element at given offset.
void GrowMap ()
 Grow block map - double the number of blocks.
void InitIterators ()
 Init the begin and end iterators.
Size NormElemCount () const
 Normalized element count.

Static Protected Attributes

static const Size MinBlockSize = 4096
 Minimum size of the deque block of elements (in bytes).
static const Size MinMapSize = 8
 Minimum size of the block map.

Detailed Description

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

Double-ended queue container.

This container stores a sequence of elements and is designed for efficient adding and removing of elements at the beginning and at the end of the sequence. All these operations are performed in amortized constant time.

Compared to the Collection::DynArray container adding and removing of elements is faster. Both containers support random-access iterators but Deque is little slower in accessing the elements using the subscript operator because the data is not stored in a continuous array.

To enable inserts at both ends the elements are stored in blocks (whose size is always a power of 2) and pointers to the blocks are stored in a map. Allocated blocks are never freed unless you call the Shrink() or Free() methods. The size of the block map is also always a power of 2 to allow fast lookup of elements using bit masking. Moreover, the map behaves as a circular buffer to prevent some degenerate cases (e.g., sequence of PushBack() + PopFront() operations).

Iterator category: Random-access.

Template Parameters:
TData type.
See also:
Collection::DynArray, Collection::Array, Collection::List, Collection::ForwardList.

Member Typedef Documentation

template<class T >
typedef Deque<T> Saf::Collection::Deque< T >::MyType [protected]

Constructor & Destructor Documentation

template<class T >
Saf::Collection::Deque< T >::Deque ( Size  elems = 0,
const T &  val = T() 
) [inline, explicit]

Default constructor.

Parameters:
[in]elemsInitial size of the container.
[in]valInitial value of the elements.
template<class T >
Saf::Collection::Deque< T >::Deque ( const MyType d) [inline]

Copy constructor.

template<class T >
Saf::Collection::Deque< T >::~Deque ( ) [inline]

Destructor.


Member Function Documentation

template<class T >
void Saf::Collection::Deque< T >::AllocateBlock ( T *&  block) [inline, protected]

Allocate memory for a given block.

template<class T >
Iterator Saf::Collection::Deque< T >::Back ( ) [inline]

Iterator to the last element.

The behaviour on empty sequence is undefined.

template<class T >
ConstIterator Saf::Collection::Deque< T >::Back ( ) const [inline]

Iterator to the last element.

The behaviour on empty sequence is undefined.

template<class T >
Iterator Saf::Collection::Deque< T >::Begin ( ) [inline]

Iterator to the first element.

template<class T >
ConstIterator Saf::Collection::Deque< T >::Begin ( ) const [inline]

Iterator to the first element.

template<class T >
Size Saf::Collection::Deque< T >::BlockIndex ( Size  ofs) const [inline, protected]

Get block index for a given element offset.

template<class T >
Size Saf::Collection::Deque< T >::BlockOffset ( Size  ofs) const [inline, protected]

Element offset in a block.

template<class T >
Size Saf::Collection::Deque< T >::BlockSize ( ) const [inline, protected]

Get maximum number of elements in each block.

template<class T >
void Saf::Collection::Deque< T >::ComputeBlockSize ( ) [inline, protected]

Compute the block size.

template<class T >
T* Saf::Collection::Deque< T >::ElementAt ( Size  ofs) [inline, protected]

Get pointer to element at given offset.

template<class T >
const T* Saf::Collection::Deque< T >::ElementAt ( Size  ofs) const [inline, protected]

Get pointer to element at given offset.

template<class T >
Size Saf::Collection::Deque< T >::Elements ( ) const [inline]

Get the number of elements stored in the container.

Properties:

  • Worst-case time complexity: $ \mathcal{O}(1) $.
template<class T >
Iterator Saf::Collection::Deque< T >::End ( ) [inline]

Iterator one behind the last element.

template<class T >
ConstIterator Saf::Collection::Deque< T >::End ( ) const [inline]

Iterator one behind the last element.

template<class T >
void Saf::Collection::Deque< T >::Free ( ) [inline]

Free memory occupied by the container.

template<class T >
Iterator Saf::Collection::Deque< T >::Front ( ) [inline]

Iterator to the first element.

template<class T >
ConstIterator Saf::Collection::Deque< T >::Front ( ) const [inline]

Iterator to the first element.

template<class T >
void Saf::Collection::Deque< T >::GrowMap ( ) [inline, protected]

Grow block map - double the number of blocks.

template<class T >
void Saf::Collection::Deque< T >::InitIterators ( ) [inline, protected]

Init the begin and end iterators.

template<class T >
bool Saf::Collection::Deque< T >::IsEmpty ( ) const [inline]

Check if the container is empty.

Properties:

  • Worst-case time complexity: $ \mathcal{O}(1) $.
template<class T >
Size Saf::Collection::Deque< T >::NormElemCount ( ) const [inline, protected]

Normalized element count.

Returns the number of elements including the sentinel and unused element positions in the first block. Useful in several situations.

template<class T >
MyType& Saf::Collection::Deque< T >::operator= ( const MyType d) [inline]

Assignment operator.

template<class T >
T& Saf::Collection::Deque< T >::operator[] ( Size  i) [inline]

Subscript operator.

template<class T >
const T& Saf::Collection::Deque< T >::operator[] ( Size  i) const [inline]

Subscript operator.

template<class T >
MyType& Saf::Collection::Deque< T >::PopBack ( ) [inline]

Remove element from the back of the container.

Properties:

  • Worst-case time complexity: $ \mathcal{O}(1) $.
  • Iterator invalidation: Invalidates only iterators to the deleted element and the End() iterator.
Remarks:
No memory is freed, to free unused memory use the Shrink() method.
template<class T >
MyType& Saf::Collection::Deque< T >::PopFront ( ) [inline]

Remove element from the beginning of the container.

Properties:

  • Worst-case time complexity: $ \mathcal{O}(1) $.
  • Iterator invalidation: Invalidates only iterators to the deleted element.
Remarks:
No memory is freed, to free unused memory use the Shrink() method.
template<class T >
MyType& Saf::Collection::Deque< T >::PushBack ( const T &  val) [inline]

Add new element at the back of the container.

Properties:

  • Worst-case time complexity: Amortized $ \mathcal{O}(1) $.
  • Iterator invalidation: Invalidates all iterators but does not invalidate references and pointers to existing elements.
template<class T >
MyType& Saf::Collection::Deque< T >::PushFront ( const T &  val) [inline]

Add new element at the beginning of the container.

Properties:

  • Worst-case time complexity: Amortized $ \mathcal{O}(1) $.
  • Iterator invalidation: Invalidates all iterators but does not invalidate references and pointers to existing elements.
template<class T >
void Saf::Collection::Deque< T >::Shrink ( ) [inline]

Shrink the container by deallocating unused memory.

Properties:

  • Iterator invalidation: Invalidates all iterators but does not invalidate references and pointers to existing elements.
template<class T >
MyType& Saf::Collection::Deque< T >::Swap ( MyType d) [inline]

Swap the content of two Deque arrays.

Properties:

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

Member Data Documentation

template<class T >
const Size Saf::Collection::Deque< T >::MinBlockSize = 4096 [static, protected]

Minimum size of the deque block of elements (in bytes).

The maximum number of elements in a block is derived from this number such that it is a power of 2 and occupies memory greater than or equal to this number.

template<class T >
const Size Saf::Collection::Deque< T >::MinMapSize = 8 [static, protected]

Minimum size of the block map.

This must be a power of 2.


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