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 | |
| 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) |
| reserve num elements at end of array | |
| SizeT | Size () const |
| get number of elements in array | |
| SizeT | Capacity () const |
| get overall allocated size of array in number of elements | |
| void | Set (IndexT index, const TYPE &elm) |
| set element at index, grow array if necessary | |
| TYPE & | At (IndexT index) |
| return reference to nth element in array | |
| 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 | |
| Iterator | Erase (Iterator iter) |
| erase element pointed to by iterator | |
| void | Insert (IndexT index, const TYPE &elm) |
| insert element before element at index | |
| void | InsertSorted (const TYPE &elm) |
| insert element into sorted array | |
| 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 | Reallocate (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 [inline] |
[] 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 [inline] |
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 [inline] |
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 | ) | [inline] |
reserve num elements at end of array
Make room for N new elements at the end of the array, and return a pointer to the start of the reserved area. This can be (carefully!) used as a fast shortcut to fill the array directly with data.
| TYPE & Util::Array< TYPE >::At | ( | IndexT | index | ) | [inline] |
return reference to nth element in array
Access an element. This method may grow the array if the index is outside the array range.
| void Util::Array< TYPE >::InsertSorted | ( | const TYPE & | elm | ) | [inline] |
insert element into sorted array
This inserts the element into a sorted array. In the current implementation this is a slow operation O(n). This should be optimized to O(log n).
| void Util::Array< TYPE >::Clear | ( | ) | [inline] |
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 | ( | ) | [inline] |
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 [inline] |
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 [inline] |
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 | |||
| ) | [inline] |
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 | ) | [inline] |
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 | ( | ) | [inline] |
sort the array
Sorts the array. This just calls the STL sort algorithm.
| IndexT Util::Array< TYPE >::BinarySearchIndex | ( | const TYPE & | elm | ) | const [inline] |
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