Nebula
Loading...
Searching...
No Matches
Util::ArrayStack< TYPE, STACK_SIZE > Class Template Reference

#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

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 >
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>
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
firstindex of first element to start fill
numnum elements to fill
elmfill 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
elmelement 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
elmelement 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
elmelement 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: