#include <arraystack.h>

Detailed Description

template<class TYPE, int STACK_SIZE>
class Util::ArrayStack< TYPE, STACK_SIZE >

Nebula's small vector optimized array.

Identical to Array in every way except that it keeps a stack allocated small buffer (much like String) and can allow for arrays to be tightly packed in memory.

Presented at CppCon 2016: https://www.youtube.com/watch?v=vElZc6zSIXM

Copyright: (C) 2018-2020 Individual contributors, see AUTHORS file

Public Types
typedef TYPE *	Iterator
	define iterator

Public Member Functions
	ArrayStack ()
	constructor with default parameters

	ArrayStack (SizeT initialCapacity, SizeT initialGrow)
	constuctor with initial size and grow size

	ArrayStack (SizeT initialSize, SizeT initialGrow, const TYPE &initialValue)
	constructor with initial size, grow size and initial values

	ArrayStack (const ArrayStack< TYPE, STACK_SIZE > &rhs)
	copy constructor

	ArrayStack (ArrayStack< TYPE, STACK_SIZE > &&rhs) noexcept
	move constructor

	ArrayStack (std::initializer_list< TYPE > list)
	constructor from initializer list

	~ArrayStack ()
	destructor

void	operator= (const ArrayStack< TYPE, STACK_SIZE > &rhs)
	assignment operator

void	operator= (ArrayStack< TYPE, STACK_SIZE > &&rhs) noexcept
	move operator

TYPE &	operator[] (IndexT index) const
	[] operator

bool	operator== (const ArrayStack< TYPE, STACK_SIZE > &rhs) const
	equality operator

bool	operator!= (const ArrayStack< TYPE, STACK_SIZE > &rhs) const
	inequality operator

template<typename T>
T	As () const
	convert to "anything"

template<typename ... ELEM_TYPE>
void	Append (const TYPE &first, const ELEM_TYPE &... elements)
	Append multiple elements to the end of the array.

void	Append (const TYPE &elm)
	append element to end of array

void	Append (TYPE &&elm)
	append an element which is being forwarded

void	AppendArray (const ArrayStack< TYPE, STACK_SIZE > &rhs)
	append the contents of an array to this array

void	AppendArray (const TYPE *arr, const SizeT count)
	append from C array

void	Reserve (SizeT num)
	increase capacity to fit N more elements into the array

const SizeT	Size () const
	get number of elements in array

const SizeT	ByteSize () const
	return the byte size of the array.

const SizeT	Capacity () const
	get overall allocated size of array in number of elements

TYPE &	Front () const
	return reference to first element

TYPE &	Back () const
	return reference to last element

bool	IsEmpty () const
	return true if array empty

void	EraseIndex (IndexT index)
	erase element at index, keep sorting intact

Iterator	Erase (Iterator iter)
	erase element pointed to by iterator, keep sorting intact

void	EraseIndexSwap (IndexT index)
	erase element at index, fill gap by swapping in last element, destroys sorting!

Iterator	EraseSwap (Iterator iter)
	erase element at iterator, fill gap by swapping in last element, destroys sorting!

void	EraseBack ()
	erase last element

void	EraseFront ()
	erase first element

void	Insert (IndexT index, const TYPE &elm)
	insert element before element at index

IndexT	InsertSorted (const TYPE &elm)
	insert element into sorted array, return index where element was included

IndexT	InsertAtEndOfIdenticalRange (IndexT startIndex, const TYPE &elm)
	insert element at the first non-identical position, return index of inclusion position

bool	IsSorted () const
	test if the array is sorted, this is a slow operation!

void	Clear ()
	clear array (calls destructors)

void	Reset ()
	reset array (does NOT call destructors)

void	Free ()
	free memory and reset size

Iterator	Begin () const
	return iterator to beginning of array

Iterator	End () const
	return iterator to end of array

Iterator	Find (const TYPE &elm) const
	find identical element in array, return iterator

IndexT	FindIndex (const TYPE &elm) const
	find identical element in array, return index, InvalidIndex if not found

template<typename KEYTYPE>
IndexT	FindIndex (typename std::enable_if< true, const KEYTYPE & >::type elm) const
	find identical element using a specific key type

void	Fill (IndexT first, SizeT num, const TYPE &elm)
	fill array range with element

void	Realloc (SizeT capacity, SizeT grow)
	clear contents and preallocate with new attributes

ArrayStack< TYPE, STACK_SIZE >	Difference (const ArrayStack< TYPE, STACK_SIZE > &rhs)
	returns new array with elements which are not in rhs (slow!)

void	Sort ()
	sort the array

void	SortWithFunc (bool(*func)(const TYPE &lhs, const TYPE &rhs))
	sort with custom function

IndexT	BinarySearchIndex (const TYPE &elm) const
	do a binary search, requires a sorted array

template<typename KEYTYPE>
IndexT	BinarySearchIndex (typename std::enable_if< true, const KEYTYPE & >::type elm) const
	do binary search with explicit typed element

const bool	IsStackUsed () const
	returns true if the stack is used

Iterator	begin () const
	for range-based iteration

Iterator	end () const

Private Member Functions
void	Destroy (TYPE *elm)
	destroy an element (call destructor without freeing memory)

void	Copy (const ArrayStack< TYPE, STACK_SIZE > &src)
	copy content

void	Delete ()
	delete content

void	Grow ()
	grow array

void	GrowTo (SizeT newCapacity)
	grow array to target size

void	Move (IndexT fromIndex, IndexT toIndex)
	move elements, grows array if needed

Private Attributes
SizeT	grow

SizeT	capacity

SizeT	count

TYPE	smallVector [STACK_SIZE]

TYPE *	elements

Static Private Attributes
static const SizeT	MinGrowSize = 16

static const SizeT	MaxGrowSize = 65536

Member Typedef Documentation

◆ Iterator

template<class TYPE, int STACK_SIZE>

typedef TYPE* Util::ArrayStack< TYPE, STACK_SIZE >::Iterator

define iterator

Constructor & Destructor Documentation

◆ ArrayStack() [1/6]

template<class TYPE, int STACK_SIZE>

Util::ArrayStack< TYPE, STACK_SIZE >::ArrayStack ( )

constructor with default parameters

◆ ArrayStack() [2/6]

template<class TYPE, int STACK_SIZE>

Util::ArrayStack< TYPE, STACK_SIZE >::ArrayStack	(	SizeT	initialCapacity,
		SizeT	initialGrow )

constuctor with initial size and grow size

◆ ArrayStack() [3/6]

template<class TYPE, int STACK_SIZE>

Util::ArrayStack< TYPE, STACK_SIZE >::ArrayStack	(	SizeT	initialSize,
		SizeT	initialGrow,
		const TYPE &	initialValue )

constructor with initial size, grow size and initial values

◆ ArrayStack() [4/6]

template<class TYPE, int STACK_SIZE>

Util::ArrayStack< TYPE, STACK_SIZE >::ArrayStack ( const ArrayStack< TYPE, STACK_SIZE > & rhs )

copy constructor

◆ ArrayStack() [5/6]

template<class TYPE, int STACK_SIZE>

Util::ArrayStack< TYPE, STACK_SIZE >::ArrayStack ( ArrayStack< TYPE, STACK_SIZE > && rhs )

inlinenoexcept

move constructor

◆ ArrayStack() [6/6]

template<class TYPE, int STACK_SIZE>

Util::ArrayStack< TYPE, STACK_SIZE >::ArrayStack ( std::initializer_list< TYPE > list )

constructor from initializer list

◆ ~ArrayStack()

template<class TYPE, int STACK_SIZE>

Util::ArrayStack< TYPE, STACK_SIZE >::~ArrayStack ( )

destructor

Member Function Documentation

◆ Append() [1/3]

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::Append ( const TYPE & elm )

append element to end of array

◆ Append() [2/3]

template<class TYPE, int STACK_SIZE>

template<typename ... ELEM_TYPE>

void Util::ArrayStack< TYPE, STACK_SIZE >::Append	(	const TYPE &	first,
		const ELEM_TYPE &...	elements )

inline

Append multiple elements to the end of the array.

◆ Append() [3/3]

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::Append ( TYPE && elm )

inline

append an element which is being forwarded

◆ AppendArray() [1/2]

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::AppendArray ( const ArrayStack< TYPE, STACK_SIZE > & rhs )

append the contents of an array to this array

◆ AppendArray() [2/2]

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::AppendArray	(	const TYPE *	arr,
		const SizeT	count )

append from C array

◆ As()

template<class TYPE, int STACK_SIZE>

template<typename T>

T Util::ArrayStack< TYPE, STACK_SIZE >::As ( ) const

convert to "anything"

◆ Back()

template<class TYPE, int STACK_SIZE>

TYPE & Util::ArrayStack< TYPE, STACK_SIZE >::Back ( ) const

return reference to last element

◆ Begin()

template<class TYPE, int STACK_SIZE>

ArrayStack< TYPE, STACK_SIZE >::Iterator Util::ArrayStack< TYPE, STACK_SIZE >::Begin ( ) const

return iterator to beginning of array

◆ begin()

template<class TYPE, int STACK_SIZE>

ArrayStack< TYPE, STACK_SIZE >::Iterator Util::ArrayStack< TYPE, STACK_SIZE >::begin ( ) const

for range-based iteration

◆ BinarySearchIndex() [1/2]

template<class TYPE, int STACK_SIZE>

IndexT Util::ArrayStack< TYPE, STACK_SIZE >::BinarySearchIndex ( const TYPE & elm ) const

do a binary search, requires a sorted array

Does a binary search on the array, returns the index of the identical element, or InvalidIndex if not found.

◆ BinarySearchIndex() [2/2]

template<class TYPE, int STACK_SIZE>

template<typename KEYTYPE>

IndexT Util::ArrayStack< TYPE, STACK_SIZE >::BinarySearchIndex ( typename std::enable_if< true, const KEYTYPE & >::type elm ) const

inline

do binary search with explicit typed element

Template type is used to force a specific type comparison.

This might mitigate some expensive implicit constructions to TYPE.

This templated method requires a explicit template type, which is enforced by using typename to put the template type in a non-deducable context. The enable_if does nothing except allow us to use typename.

◆ ByteSize()

template<class TYPE, int STACK_SIZE>

const SizeT Util::ArrayStack< TYPE, STACK_SIZE >::ByteSize ( ) const

return the byte size of the array.

◆ Capacity()

template<class TYPE, int STACK_SIZE>

const SizeT Util::ArrayStack< TYPE, STACK_SIZE >::Capacity ( ) const

get overall allocated size of array in number of elements

◆ Clear()

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::Clear ( )

clear array (calls destructors)

The current implementation of this method does not shrink the preallocated space.

It simply sets the array size to 0.

◆ Copy()

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::Copy ( const ArrayStack< TYPE, STACK_SIZE > & src )

private

copy content

◆ Delete()

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::Delete ( )

private

delete content

◆ Destroy()

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::Destroy ( TYPE * elm )

private

destroy an element (call destructor without freeing memory)

◆ Difference()

template<class TYPE, int STACK_SIZE>

ArrayStack< TYPE, STACK_SIZE > Util::ArrayStack< TYPE, STACK_SIZE >::Difference ( const ArrayStack< TYPE, STACK_SIZE > & rhs )

returns new array with elements which are not in rhs (slow!)

Returns a new array with all element which are in rhs, but not in this.

Carefull, this method may be very slow with large arrays!

Todo: this method is broken, check test case to see why!

◆ End()

template<class TYPE, int STACK_SIZE>

ArrayStack< TYPE, STACK_SIZE >::Iterator Util::ArrayStack< TYPE, STACK_SIZE >::End ( ) const

return iterator to end of array

◆ end()

template<class TYPE, int STACK_SIZE>

ArrayStack< TYPE, STACK_SIZE >::Iterator Util::ArrayStack< TYPE, STACK_SIZE >::end ( ) const

◆ Erase()

template<class TYPE, int STACK_SIZE>

ArrayStack< TYPE, STACK_SIZE >::Iterator Util::ArrayStack< TYPE, STACK_SIZE >::Erase ( Iterator iter )

erase element pointed to by iterator, keep sorting intact

◆ EraseBack()

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::EraseBack ( )

erase last element

◆ EraseFront()

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::EraseFront ( )

erase first element

◆ EraseIndex()

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::EraseIndex ( IndexT index )

erase element at index, keep sorting intact

◆ EraseIndexSwap()

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::EraseIndexSwap ( IndexT index )

erase element at index, fill gap by swapping in last element, destroys sorting!

NOTE: this method is fast but destroys the sorting order!

◆ EraseSwap()

template<class TYPE, int STACK_SIZE>

ArrayStack< TYPE, STACK_SIZE >::Iterator Util::ArrayStack< TYPE, STACK_SIZE >::EraseSwap ( Iterator iter )

erase element at iterator, fill gap by swapping in last element, destroys sorting!

NOTE: this method is fast but destroys the sorting order!

◆ Fill()

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::Fill	(	IndexT	first,
		SizeT	num,
		const TYPE &	elm )

fill array range with element

Fills an array range with the given element value.

Will grow the array if necessary

Parameters

first	index of first element to start fill
num	num elements to fill
elm	fill value

◆ Find()

template<class TYPE, int STACK_SIZE>

ArrayStack< TYPE, STACK_SIZE >::Iterator Util::ArrayStack< TYPE, STACK_SIZE >::Find ( const TYPE & elm ) const

find identical element in array, return iterator

Find element in array, return iterator, or 0 if element not found.

Parameters

elm	element to find

Returns: element iterator, or 0 if not found

◆ FindIndex() [1/2]

template<class TYPE, int STACK_SIZE>

IndexT Util::ArrayStack< TYPE, STACK_SIZE >::FindIndex ( const TYPE & elm ) const

find identical element in array, return index, InvalidIndex if not found

Find element in array, return element index, or InvalidIndex if element not found.

Parameters

elm	element to find

Returns: index to element, or InvalidIndex if not found

◆ FindIndex() [2/2]

template<class TYPE, int STACK_SIZE>

template<typename KEYTYPE>

IndexT Util::ArrayStack< TYPE, STACK_SIZE >::FindIndex ( typename std::enable_if< true, const KEYTYPE & >::type elm ) const

inline

find identical element using a specific key type

Find element in array, return element index, or InvalidIndex if element not found.

Template type is used to force a specific type comparison. This might mitigate some expensive implicit constructions to TYPE.

This templated method requires a explicit template type, which is enforced by using typename to put the template type in a non-deducable context. The enable_if does nothing except allow us to use typename.

Parameters

elm	element to find

Returns: index to element, or InvalidIndex if not found

◆ Free()

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::Free ( )

free memory and reset size

Free up memory and reset the grow.

◆ Front()

template<class TYPE, int STACK_SIZE>

TYPE & Util::ArrayStack< TYPE, STACK_SIZE >::Front ( ) const

return reference to first element

◆ Grow()

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::Grow ( )

private

grow array

◆ GrowTo()

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::GrowTo ( SizeT newCapacity )

private

grow array to target size

◆ Insert()

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::Insert	(	IndexT	index,
		const TYPE &	elm )

insert element before element at index

◆ InsertAtEndOfIdenticalRange()

template<class TYPE, int STACK_SIZE>

IndexT Util::ArrayStack< TYPE, STACK_SIZE >::InsertAtEndOfIdenticalRange	(	IndexT	startIndex,
		const TYPE &	elm )

insert element at the first non-identical position, return index of inclusion position

This inserts an element at the end of a range of identical elements starting at a given index.

Performance is O(n). Returns the index at which the element was added.

◆ InsertSorted()

template<class TYPE, int STACK_SIZE>

IndexT Util::ArrayStack< TYPE, STACK_SIZE >::InsertSorted ( const TYPE & elm )

insert element into sorted array, return index where element was included

This inserts the element into a sorted array.

Returns the index at which the element was inserted.

◆ IsEmpty()

template<class TYPE, int STACK_SIZE>

bool Util::ArrayStack< TYPE, STACK_SIZE >::IsEmpty ( ) const

return true if array empty

◆ IsSorted()

template<class TYPE, int STACK_SIZE>

bool Util::ArrayStack< TYPE, STACK_SIZE >::IsSorted ( ) const

test if the array is sorted, this is a slow operation!

This tests, whether the array is sorted.

This is a slow operation O(n).

◆ IsStackUsed()

template<class TYPE, int STACK_SIZE>

const bool Util::ArrayStack< TYPE, STACK_SIZE >::IsStackUsed ( ) const

returns true if the stack is used

◆ Move()

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::Move	(	IndexT	fromIndex,
		IndexT	toIndex )

private

move elements, grows array if needed

30-Jan-03 floh serious bugfixes!

07-Dec-04 jo bugfix: neededSize >= this->capacity => neededSize > capacity

◆ operator!=()

template<class TYPE, int STACK_SIZE>

bool Util::ArrayStack< TYPE, STACK_SIZE >::operator!= ( const ArrayStack< TYPE, STACK_SIZE > & rhs ) const

inequality operator

The inequality operator returns true if at least one element in the array is different, or the array sizes are different.

◆ operator=() [1/2]

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::operator= ( ArrayStack< TYPE, STACK_SIZE > && rhs )

inlinenoexcept

move operator

◆ operator=() [2/2]

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::operator= ( const ArrayStack< TYPE, STACK_SIZE > & rhs )

assignment operator

◆ operator==()

template<class TYPE, int STACK_SIZE>

bool Util::ArrayStack< TYPE, STACK_SIZE >::operator== ( const ArrayStack< TYPE, STACK_SIZE > & rhs ) const

equality operator

The equality operator returns true if all elements are identical.

The TYPE class must support the equality operator.

◆ operator[]()

template<class TYPE, int STACK_SIZE>

TYPE & Util::ArrayStack< TYPE, STACK_SIZE >::operator[] ( IndexT index ) const

[] operator

Access an element.

This method will NOT grow the array, and instead do a range check, which may throw an assertion.

◆ Realloc()

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::Realloc	(	SizeT	capacity,
		SizeT	grow )

clear contents and preallocate with new attributes

◆ Reserve()

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::Reserve ( SizeT num )

increase capacity to fit N more elements into the array

This increases the capacity to make room for N elements.

If the number of elements is known before appending the elements, this method can be used to prevent reallocation. If there is already enough room for N more elements, nothing will happen.

NOTE: the functionality of this method has been changed as of 26-Apr-08, it will now only change the capacity of the array, not its size.

◆ Reset()

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::Reset ( )

reset array (does NOT call destructors)

This is identical with Clear(), but does NOT call destructors (it just resets the size member.

USE WITH CARE!

◆ Size()

template<class TYPE, int STACK_SIZE>

const SizeT Util::ArrayStack< TYPE, STACK_SIZE >::Size ( ) const

get number of elements in array

◆ Sort()

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::Sort ( )

sort the array

Sorts the array.

This just calls the STL sort algorithm.

◆ SortWithFunc()

template<class TYPE, int STACK_SIZE>

void Util::ArrayStack< TYPE, STACK_SIZE >::SortWithFunc ( bool(* func )(const TYPE &lhs, const TYPE &rhs) )

sort with custom function

Member Data Documentation

◆ capacity

template<class TYPE, int STACK_SIZE>

SizeT Util::ArrayStack< TYPE, STACK_SIZE >::capacity

private

◆ count

template<class TYPE, int STACK_SIZE>

SizeT Util::ArrayStack< TYPE, STACK_SIZE >::count

private

◆ elements

template<class TYPE, int STACK_SIZE>

TYPE* Util::ArrayStack< TYPE, STACK_SIZE >::elements

private

◆ grow

template<class TYPE, int STACK_SIZE>

SizeT Util::ArrayStack< TYPE, STACK_SIZE >::grow

private

◆ MaxGrowSize

template<class TYPE, int STACK_SIZE>

const SizeT Util::ArrayStack< TYPE, STACK_SIZE >::MaxGrowSize = 65536

staticprivate

◆ MinGrowSize

template<class TYPE, int STACK_SIZE>

const SizeT Util::ArrayStack< TYPE, STACK_SIZE >::MinGrowSize = 16

staticprivate

◆ smallVector

template<class TYPE, int STACK_SIZE>

TYPE Util::ArrayStack< TYPE, STACK_SIZE >::smallVector[STACK_SIZE]

private

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

/github/workspace/code/foundation/util/arraystack.h

Detailed Description

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Member Typedef Documentation

◆ Iterator

Constructor & Destructor Documentation

◆ ArrayStack() [1/6]

◆ ArrayStack() [2/6]

◆ ArrayStack() [3/6]

◆ ArrayStack() [4/6]

◆ ArrayStack() [5/6]

◆ ArrayStack() [6/6]

◆ ~ArrayStack()

Member Function Documentation

◆ Append() [1/3]

◆ Append() [2/3]

◆ Append() [3/3]

◆ AppendArray() [1/2]

◆ AppendArray() [2/2]

◆ As()

◆ Back()

◆ Begin()

◆ begin()

◆ BinarySearchIndex() [1/2]

◆ BinarySearchIndex() [2/2]

◆ ByteSize()

◆ Capacity()

◆ Clear()

◆ Copy()

◆ Delete()

◆ Destroy()

◆ Difference()

◆ End()

◆ end()

◆ Erase()

◆ EraseBack()

◆ EraseFront()

◆ EraseIndex()

◆ EraseIndexSwap()

◆ EraseSwap()

◆ Fill()

◆ Find()

◆ FindIndex() [1/2]

◆ FindIndex() [2/2]

◆ Free()

◆ Front()

◆ Grow()

◆ GrowTo()

◆ Insert()

◆ InsertAtEndOfIdenticalRange()

◆ InsertSorted()

◆ IsEmpty()

◆ IsSorted()

◆ IsStackUsed()

◆ Move()

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator[]()

◆ Realloc()

◆ Reserve()

◆ Reset()

◆ Size()

◆ Sort()

◆ SortWithFunc()

Member Data Documentation

◆ capacity

◆ count

◆ elements

◆ grow

◆ MaxGrowSize

◆ MinGrowSize

◆ smallVector