Util::Array< TYPE > Class Template Reference
#include <array.h>
Detailed Description
template<class TYPE>
class Util::Array< TYPE >
Nebula3's dynamic array class. This class is also used by most other collection classes.The default constructor will not pre-allocate elements, so no space is wasted as long as no elements are added. As soon as the first element is added to the array, an initial buffer of 16 elements is created. Whenever the element buffer would overflow, a new buffer of twice the size of the previous buffer is created and the existing elements are then copied over to the new buffer. The element buffer will never shrink, the only way to reclaim unused memory is to copy the Array to a new Array object. This is usually not a problem since most arrays will oscillate around some specific size, so once the array has reached this specific size, no costly memory free or allocs will be performed.
It is possible to sort the array using the Sort() method, this uses std::sort (one of the very few exceptions where the STL is used in Nebula3).
One should generally be careful with costly copy operators, the Array class (and the other container classes using Array) may do some heavy element shuffling in some situations (especially when sorting and erasing elements).
(C) 2006 RadonLabs GmbH
Public Types | |
| typedef TYPE * | Iterator |
| define iterator | |
Public Member Functions | |
| Array () | |
| constructor with default parameters | |
| Array (SizeT initialCapacity, SizeT initialGrow) | |
| constuctor with initial size and grow size | |
| Array (SizeT initialSize, SizeT initialGrow, const TYPE &initialValue) | |
| constructor with initial size, grow size and initial values | |
| Array (const Array< TYPE > &rhs) | |
| copy constructor | |
| ~Array () | |
| destructor | |
| void | operator= (const Array< TYPE > &rhs) |
| assignment operator | |
| TYPE & | operator[] (IndexT index) const |
| [] operator | |
| bool | operator== (const Array< TYPE > &rhs) const |
| equality operator | |
| bool | operator!= (const Array< TYPE > &rhs) const |
| inequality operator | |
| template<typename T> | |
| T | As () const |
| convert to "anything" | |
| void | Append (const TYPE &elm) |
| append element to end of array | |
| void | AppendArray (const Array< TYPE > &rhs) |
| append the contents of an array to this array | |
| void | Reserve (SizeT num) |
| increase capacity to fit N more elements into the array | |
| SizeT | Size () const |
| get number of elements in array | |
| 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 | 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) | |
| 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 | |
| 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 | |
| Array< TYPE > | Difference (const Array< TYPE > &rhs) |
| returns new array with elements which are not in rhs (slow!) | |
| void | Sort () |
| sort the array | |
| IndexT | BinarySearchIndex (const TYPE &elm) const |
| do a binary search, requires a sorted array | |
Member Function Documentation
| TYPE & Util::Array< TYPE >::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.
| bool Util::Array< TYPE >::operator== | ( | const Array< TYPE > & | rhs | ) | const |
equality operator
The equality operator returns true if all elements are identical. The TYPE class must support the equality operator.
| bool Util::Array< TYPE >::operator!= | ( | const Array< TYPE > & | 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.
| void Util::Array< TYPE >::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::Array< TYPE >::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!
| IndexT Util::Array< TYPE >::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.
| IndexT Util::Array< TYPE >::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.
| bool Util::Array< TYPE >::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).
| void Util::Array< TYPE >::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.
| void Util::Array< TYPE >::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!
| Array< TYPE >::Iterator Util::Array< TYPE >::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
| IndexT Util::Array< TYPE >::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
| void Util::Array< TYPE >::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
| Array< TYPE > Util::Array< TYPE >::Difference | ( | const Array< TYPE > & | 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!
| void Util::Array< TYPE >::Sort | ( | ) |
sort the array
Sorts the array. This just calls the STL sort algorithm.
| IndexT Util::Array< TYPE >::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