Nebula
|
#include <arraystack.h>
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 > | |
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 |
TYPE* Util::ArrayStack< TYPE, STACK_SIZE >::Iterator |
define iterator
Util::ArrayStack< TYPE, STACK_SIZE >::ArrayStack | ( | ) |
constructor with default parameters
Util::ArrayStack< TYPE, STACK_SIZE >::ArrayStack | ( | SizeT | initialCapacity, |
SizeT | initialGrow ) |
constuctor with initial size and grow size
Util::ArrayStack< TYPE, STACK_SIZE >::ArrayStack | ( | SizeT | initialSize, |
SizeT | initialGrow, | ||
const TYPE & | initialValue ) |
constructor with initial size, grow size and initial values
Util::ArrayStack< TYPE, STACK_SIZE >::ArrayStack | ( | const ArrayStack< TYPE, STACK_SIZE > & | rhs | ) |
copy constructor
|
inlinenoexcept |
move constructor
Util::ArrayStack< TYPE, STACK_SIZE >::ArrayStack | ( | std::initializer_list< TYPE > | list | ) |
constructor from initializer list
Util::ArrayStack< TYPE, STACK_SIZE >::~ArrayStack | ( | ) |
destructor
void Util::ArrayStack< TYPE, STACK_SIZE >::Append | ( | const TYPE & | elm | ) |
append element to end of array
|
inline |
Append multiple elements to the end of the array.
|
inline |
append an element which is being forwarded
void Util::ArrayStack< TYPE, STACK_SIZE >::AppendArray | ( | const ArrayStack< TYPE, STACK_SIZE > & | rhs | ) |
append the contents of an array to this array
void Util::ArrayStack< TYPE, STACK_SIZE >::AppendArray | ( | const TYPE * | arr, |
const SizeT | count ) |
append from C array
T Util::ArrayStack< TYPE, STACK_SIZE >::As | ( | ) | const |
convert to "anything"
TYPE & Util::ArrayStack< TYPE, STACK_SIZE >::Back | ( | ) | const |
return reference to last element
ArrayStack< TYPE, STACK_SIZE >::Iterator Util::ArrayStack< TYPE, STACK_SIZE >::Begin | ( | ) | const |
return iterator to beginning of array
ArrayStack< TYPE, STACK_SIZE >::Iterator Util::ArrayStack< TYPE, STACK_SIZE >::begin | ( | ) | const |
for range-based iteration
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.
|
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.
const SizeT Util::ArrayStack< TYPE, STACK_SIZE >::ByteSize | ( | ) | const |
return the byte size of the array.
const SizeT Util::ArrayStack< TYPE, STACK_SIZE >::Capacity | ( | ) | const |
get overall allocated size of array in number of elements
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.
|
private |
copy content
|
private |
delete content
|
private |
destroy an element (call destructor without freeing memory)
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!
ArrayStack< TYPE, STACK_SIZE >::Iterator Util::ArrayStack< TYPE, STACK_SIZE >::End | ( | ) | const |
return iterator to end of array
ArrayStack< TYPE, STACK_SIZE >::Iterator Util::ArrayStack< TYPE, STACK_SIZE >::end | ( | ) | const |
ArrayStack< TYPE, STACK_SIZE >::Iterator Util::ArrayStack< TYPE, STACK_SIZE >::Erase | ( | Iterator | iter | ) |
erase element pointed to by iterator, keep sorting intact
void Util::ArrayStack< TYPE, STACK_SIZE >::EraseBack | ( | ) |
erase last element
void Util::ArrayStack< TYPE, STACK_SIZE >::EraseFront | ( | ) |
erase first element
void Util::ArrayStack< TYPE, STACK_SIZE >::EraseIndex | ( | IndexT | index | ) |
erase element at index, keep sorting intact
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!
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!
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
first | index of first element to start fill |
num | num elements to fill |
elm | fill value |
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.
elm | element to find |
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.
elm | element to find |
|
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.
elm | element to find |
void Util::ArrayStack< TYPE, STACK_SIZE >::Free | ( | ) |
free memory and reset size
Free up memory and reset the grow.
TYPE & Util::ArrayStack< TYPE, STACK_SIZE >::Front | ( | ) | const |
return reference to first element
|
private |
grow array
|
private |
grow array to target size
void Util::ArrayStack< TYPE, STACK_SIZE >::Insert | ( | IndexT | index, |
const TYPE & | elm ) |
insert element before element at index
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.
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.
bool Util::ArrayStack< TYPE, STACK_SIZE >::IsEmpty | ( | ) | const |
return true if array empty
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).
const bool Util::ArrayStack< TYPE, STACK_SIZE >::IsStackUsed | ( | ) | const |
returns true if the stack is used
|
private |
move elements, grows array if needed
30-Jan-03 floh serious bugfixes! 07-Dec-04 jo bugfix: neededSize >= this->capacity => neededSize > capacity
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.
|
inlinenoexcept |
move operator
void Util::ArrayStack< TYPE, STACK_SIZE >::operator= | ( | const ArrayStack< TYPE, STACK_SIZE > & | rhs | ) |
assignment operator
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.
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.
void Util::ArrayStack< TYPE, STACK_SIZE >::Realloc | ( | SizeT | capacity, |
SizeT | grow ) |
clear contents and preallocate with new attributes
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.
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!
const SizeT Util::ArrayStack< TYPE, STACK_SIZE >::Size | ( | ) | const |
get number of elements in array
void Util::ArrayStack< TYPE, STACK_SIZE >::Sort | ( | ) |
sort the array
Sorts the array.
This just calls the STL sort algorithm.
void Util::ArrayStack< TYPE, STACK_SIZE >::SortWithFunc | ( | bool(* | func )(const TYPE &lhs, const TYPE &rhs) | ) |
sort with custom function
|
private |
|
private |
|
private |
|
private |
|
staticprivate |
|
staticprivate |
|
private |