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.
MyType &	operator= (const MyType &d)
	Assignment operator.
T &	operator[] (Size i)
	Subscript operator.
const T &	operator[] (Size i) const
	Subscript operator.
MyType &	PopBack ()
	Remove element from the back of the container.
MyType &	PopFront ()
	Remove element from the beginning of the container.
MyType &	PushBack (const T &val)
	Add new element at the back of the container.
MyType &	PushFront (const T &val)
	Add new element at the beginning of the container.
void	Shrink ()
	Shrink the container by deallocating unused memory.
MyType &	Swap (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:

T	Data 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]	elems	Initial size of the container.
[in]	val	Initial 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: .

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

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

---

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:

• Saf/Collection/Deque.h