Dynamic array. More...

#include <DynArray.h>

Public Types
typedef const T *	ConstIterator
	Random-access non-mutable DynArray iterator.
typedef T *	Iterator
	Random-access mutable DynArray iterator.
Public Member Functions
	DynArray ()
	Constructor.
	DynArray (Size initSize, const T &initVal=T())
	Constructor.
	DynArray (const MyType &a)
	Copy constructor.
	~DynArray ()
	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	Capacity () const
	Get the maximum number of elements the array can accomodate without memory reallocation.
Size	Elements () const
	Get the current number of elements in the container.
Iterator	End ()
	Iterator one after the last element.
ConstIterator	End () const
	Iterator one after the last element.
Iterator	Erase (Iterator it)
	Remove arbitrary element from the array.
Iterator	Erase (Iterator itBegin, Iterator itEnd)
	Remove a range of elements from the array.
MyType &	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 whether the array is empty.
MyType &	operator= (const MyType &a)
	Assignment operator.
T &	operator[] (Size i)
	Subscript operator.
const T &	operator[] (Size i) const
	Subscript operator.
MyType &	PopBack ()
	Remove the last element in the array.
MyType &	PopFront ()
	Remove the first element in the array.
MyType &	PushBack (const T &val)
	Add new element to the end of the array.
MyType &	PushFront (const T &val)
	Add new element to the beginning of the array.
MyType &	Reserve (Size cap)
	Enlarge the capacity of the array such that it is at least `cap`.
MyType &	Resize (Size newSize, const T &initVal=T())
	Resize the array.
MyType &	Shrink ()
	Free allocated storage that is not used by valid array elements.
MyType &	Swap (MyType &da)
	Swap the content of two arrays.
Protected Types
typedef DynArray< T >	MyType
Protected Member Functions
void	Grow (Size cap)
	Enlarge the capacity of the array.
Size	OptimalCapacityIncrease (Size reqSize)
	Returns how much the capacity should be increased in order to be able to fit the requested number of elements and to reduce later memory reallocations.
Static Protected Member Functions
static Size	MinCapacity ()
	Minimum capacity of the array.

Detailed Description

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

Dynamic array.

This class represents a one-dimensional array of data that can be dynamically resized. The data is stored in a continuous memory region and the content of the array is preserved during the resize operation. The class is optimized for frequent resizing, i.e., the number of memory reallocations should be minimized. On the other hand, the container may consume more memory than necessary in order to accommodate extra storage for future growth.

Alternatives:

In cases where the size of the array is known in advance and does not change very often it is advised to use Collection::Array instead.
The methods PushFront() and PopFront() are very slow. If you call them regularly consider using Collection::Deque instead.

Iterator category: Random-access.

Template Parameters:

T	Data type.

See also:: Collection::Array, Collection::Deque.

Member Typedef Documentation

template<class T >

typedef const T* Saf::Collection::DynArray< T >::ConstIterator

Random-access non-mutable DynArray iterator.

template<class T >

typedef T* Saf::Collection::DynArray< T >::Iterator

Random-access mutable DynArray iterator.

template<class T >

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

Constructor & Destructor Documentation

template<class T >

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

Constructor.

template<class T >

Saf::Collection::DynArray< T >::DynArray	(	Size	initSize,
		const T &	initVal = `T()`
	)		`[inline, explicit]`

Constructor.

Parameters:

[in]	initSize	Initial number of elements in the array.
[in]	initVal	Initial value of the elements.

template<class T >

Saf::Collection::DynArray< T >::DynArray ( const MyType & a ) [inline]

Copy constructor.

template<class T >

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

Destructor.

Member Function Documentation

template<class T >

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

Iterator to the last element.

template<class T >

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

Iterator to the last element.

template<class T >

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

Iterator to the first element.

template<class T >

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

Iterator to the first element.

template<class T >

Size Saf::Collection::DynArray< T >::Capacity ( ) const [inline]

Get the maximum number of elements the array can accomodate without memory reallocation.

template<class T >

Size Saf::Collection::DynArray< T >::Elements ( ) const [inline]

Get the current number of elements in the container.

Properties:

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

template<class T >

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

Iterator one after the last element.

template<class T >

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

Iterator one after the last element.

template<class T >

Iterator Saf::Collection::DynArray< T >::Erase ( Iterator it ) [inline]

Remove arbitrary element from the array.

Succeeding elements are shifted.

Properties:

Worst-case time complexity: $\mathcal{O}(\mathrm{Elements()})$ .
Iterator invalidation: Invalidates all iterators pointing at the removed element or its successors.

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

Warning:: This method is slow. Consider using Collection::List of Collection::ForwardList if you need to remove elements from arbitrary positions in the container.

template<class T >

Iterator Saf::Collection::DynArray< T >::Erase	(	Iterator	itBegin,
		Iterator	itEnd
	)		`[inline]`

Remove a range of elements from the array.

The elements in the range [itBegin, itEnd) are removed and succeeding elements are shifted.

Properties:

Worst-case time complexity: $\mathcal{O}(\mathrm{Elements()})$ .
Iterator invalidation: Invalidates all iterators pointing at elements in the removed range and iterators to elements following the removed range.

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

Warning:: This method is slow. Consider using Collection::List of Collection::ForwardList if you need to remove elements from arbitrary positions in the container.

template<class T >

MyType& Saf::Collection::DynArray< T >::Free ( ) [inline]

Free memory occupied by the container.

Properties:

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

template<class T >

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

Iterator to the first element.

template<class T >

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

Iterator to the first element.

template<class T >

void Saf::Collection::DynArray< T >::Grow ( Size cap ) [inline, protected]

Enlarge the capacity of the array.

Parameters:

[in] cap The requested capacity. Must be greater than zero and at least equal to the current number of elements.

template<class T >

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

Check whether the array is empty.

Properties:

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

template<class T >

static Size Saf::Collection::DynArray< T >::MinCapacity ( ) [inline, static, protected]

Minimum capacity of the array.

Setting this higher reduces memory reallocations but may waste some memory for small arrays.

template<class T >

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

Assignment operator.

template<class T >

T& Saf::Collection::DynArray< T >::operator[] ( Size i ) [inline]

Subscript operator.

template<class T >

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

Subscript operator.

template<class T >

Size Saf::Collection::DynArray< T >::OptimalCapacityIncrease ( Size reqSize ) [inline, protected]

Returns how much the capacity should be increased in order to be able to fit the requested number of elements and to reduce later memory reallocations.

Parameters:

[in] reqSize The requested new size.

template<class T >

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

Remove the last element in the array.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .
Iterator invalidation: Does invalidate only iterators pointing at the removed element and the End() iterator.

template<class T >

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

Remove the first element in the array.

Properties:

Worst-case time complexity: $\mathcal{O}(\mathrm{Elements()})$ .
Iterator invalidation: Invalidates all iterators and references.

Warning:: This method is slow. Consider using Collection::Deque if you need to remove elements from the front of the container.

template<class T >

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

Add new element to the end of the array.

Properties:

Worst-case time complexity: Amortized $\mathcal{O}(1)$ .
Iterator invalidation: Invalidates all iterators and references if Elements() == Capacity().

template<class T >

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

Add new element to the beginning of the array.

Properties:

Worst-case time complexity: $\mathcal{O}(\mathrm{Elements()})$ .
Iterator invalidation: Invalidates all iterators and references.

Warning:: This method is slow. Consider using Collection::Deque if you need to add elements to the front of the container.

template<class T >

MyType& Saf::Collection::DynArray< T >::Reserve ( Size cap ) [inline]

Enlarge the capacity of the array such that it is at least cap.

This method informs the object about future growth of the array and is useful to avoid iterator invalidations or excessive memory reallocations.

Properties:

Worst-case time complexity: $\mathcal{O}(\mathrm{Elements()})$ .
Iterator invalidation: Invalidates all iterators and references if cap > Capacity().

template<class T >

MyType& Saf::Collection::DynArray< T >::Resize	(	Size	newSize,
		const T &	initVal = `T()`
	)		`[inline]`

Resize the array.

The content of the first min(Elements(), newSize) elements is preserved.

Properties:

Worst-case time complexity: $\mathcal{O}(\mathrm{max(Elements(), newSize)})$ .
Iterator invalidation: Invalidates all iterators and references if newSize > Capacity().

Parameters:

[in]	newSize	New size of the array.
[in]	initVal	Initial value of the newly added elements.

Remarks:: The memory is reallocated only if newSize is greater than the current capacity. More memory than requested may be allocated to accommodate for future growth. Use Shrink() to free unused memory.

See also:: OptimalCapacityIncrease(), Shrink(), Reserve().

template<class T >

MyType& Saf::Collection::DynArray< T >::Shrink ( ) [inline]

Free allocated storage that is not used by valid array elements.

Properties:

Worst-case time complexity: $\mathcal{O}(\mathrm{Elements()})$ .
Iterator invalidation: Invalidates all iterators and references.

template<class T >

MyType& Saf::Collection::DynArray< T >::Swap ( MyType & da ) [inline]

Swap the content of two arrays.

Properties:

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

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

Saf/Collection/DynArray.h

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Static Protected Member Functions

Detailed Description

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

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

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