Contents User Forum Source Index APIs by Task APIs by Level Data G3D::Array< T > Class Template Reference Dynamic 1D array. More... #include <Array.h> List of all members. Public Types typedef const T *  ConstIterator typedef T *  Iterator Public Member Functions void  append (const Array< T > &array) void  append (const T &v1, const T &v2, const T &v3, const T &v4) void  append (const T &v1, const T &v2, const T &v3) void  append (const T &v1, const T &v2) void  append (const T &value)   Array (const Array &other)   Array (int size)   Array () ConstIterator  begin () const Iterator  begin () int  capacity () const void  clear () bool  contains (const T &e) const void  deleteAll () Iterator  end () ConstIterator  end () const void  fastClear () void  fastRemove (int index) void  fastResize (int n) ConstIterator  find (const T &value) const Iterator  find (const T &value) int  findIndex (const T &value) const const T &  first () const T &  first () int  firstIndex () const const T &  front () const T &  front () const T *  getCArray () const T *  getCArray () void  insert (int n, const T &value) T &  last () const T &  last () const int  lastIndex () const int  length () const void  medianPartition (Array< T > &ltMedian, Array< T > &eqMedian, Array< T > &gtMedian) const template<typename Comparator> void  medianPartition (Array< T > &ltMedian, Array< T > &eqMedian, Array< T > &gtMedian, Array< T > &tempArray, const Comparator &comparator) const T &  middle () const T &  middle () const int  middleIndex () const T &  next () Array &  operator= (const std::vector< T > &other) Array &  operator= (const Array &other) const T &  operator[] (unsigned int n) const const T &  operator[] (int n) const T &  operator[] (unsigned int n) T &  operator[] (int n) void  partition (const T &partitionElement, Array< T > &ltArray, Array< T > &eqArray, Array< T > &gtArray) const template<typename Comparator> void  partition (const T &partitionElement, Array< T > &ltArray, Array< T > &eqArray, Array< T > &gtArray, const Comparator &comparator) const T  pop (bool shrinkUnderlyingArrayIfNecessary=true) void  pop_back () void  popDiscard (bool shrinkUnderlyingArrayIfNecessary=false) void  push (const Array< T > &array) void  push (const T &value) void  push_back (const T &v) const T &  randomElement () const T &  randomElement () void  randomize () void  remove (int index, int count=1) void  remove (Iterator element, int count=1) void  resize (int n, bool shrinkIfNecessary) void  resize (int n) void  reverse () int  size () const void  sort (int direction=SORT_INCREASING) void  sort (bool(__cdecl *lessThan)(const T &elem1, const T &elem2)) template<typename StrictWeakOrdering> void  sortSubArray (int beginIndex, int endIndex, StrictWeakOrdering &lessThan) void  sortSubArray (int beginIndex, int endIndex, bool(__cdecl *lessThan)(const T &elem1, const T &elem2)) void  sortSubArray (int beginIndex, int endIndex, int direction=SORT_INCREASING) void  swap (Array< T > &str)   ~Array () Classes class   DefaultComparator   Uses < and == to evaluate operator(); this is the default comparator for Array::partition. More... Detailed Description template<class T> class G3D::Array< T > Dynamic 1D array. Objects must have a default constructor (constructor that takes no arguments) in order to be used with this template. You will get the error "no appropriate default constructor found" if they do not. Do not use with objects that overload placement operator new, since the speed of Array is partly due to pooled allocation. If SSE is defined Arrays allocate the first element aligned to 16 bytes. Array is highly optimized compared to std::vector. Array operations are less expensive than on std::vector and for large amounts of data, Array consumes only 1.5x the total size of the data, while std::vector consumes 2.0x. The default array takes up zero heap space. The first resize (or append) operation grows it to a reasonable internal size so it is efficient to append to small arrays. Memory is allocated using System::alignedMalloc, which produces pointers aligned to 16-byte boundaries for use with SSE instructions and uses pooled storage for fast allocation. When Array needs to copy data internally on a resize operation it correctly invokes copy constructors of the elements (the MSVC6 implementation of std::vector uses realloc, which can create memory leaks for classes containing references and pointers). Array provides a guaranteed safe way to access the underlying data as a flat C array -- Array::getCArray. Although (T*)std::vector::begin() can be used for this purpose, it is not guaranteed to succeed on all platforms. To serialize an array, see G3D::serialize. Do not subclass an Array. Member Typedef Documentation template<class T> typedef const T* G3D::Array< T >::ConstIterator template<class T> typedef T* G3D::Array< T >::Iterator C++ STL style iterator variable. Call begin() to get the first iterator, pre-increment (++i) the iterator to get to the next value. Use dereference (*i) to access the element. Constructor & Destructor Documentation template<class T> G3D::Array< T >::Array (  )  [inline] Creates a zero length array (no heap allocation occurs until resize). template<class T> G3D::Array< T >::Array ( int  size  )  [inline] Creates an array of size. template<class T> G3D::Array< T >::Array ( const Array< T > &  other  )  [inline] Copy constructor. template<class T> G3D::Array< T >::~Array (  )  [inline] Destructor does not delete() the objects if T is a pointer type (e.g. T = int*) instead, it deletes the pointers themselves and leaves the objects. Call deleteAll if you want to dealocate the objects referenced. Do not call deleteAll if T is not a pointer type (e.g. do call Array<Foo*>::deleteAll, do not call Array<Foo>::deleteAll). Member Function Documentation template<class T> void G3D::Array< T >::append ( const Array< T > &  array  )  [inline] Append the elements of array. Cannot be called with this array as an argument. template<class T> void G3D::Array< T >::append ( const T &  v1, const T &  v2, const T &  v3, const T &  v4   ) [inline] template<class T> void G3D::Array< T >::append ( const T &  v1, const T &  v2, const T &  v3   ) [inline] template<class T> void G3D::Array< T >::append ( const T &  v1, const T &  v2   ) [inline] template<class T> void G3D::Array< T >::append ( const T &  value  )  [inline] Add an element to the end of the array. Will not shrink the underlying array under any circumstances. It is safe to append an element that is already in the array. template<class T> ConstIterator G3D::Array< T >::begin (  )  const [inline] template<class T> Iterator G3D::Array< T >::begin (  )  [inline] C++ STL style iterator method. Returns the first iterator element. Do not change the size of the array while iterating. template<class T> int G3D::Array< T >::capacity (  )  const [inline] "The member function returns the storage currently allocated to hold the controlled sequence, a value at least as large as size()" For compatibility with std::vector. template<class T> void G3D::Array< T >::clear (  )  [inline] Removes all elements. Use resize(0, false) or fastClear if you want to remove all elements without deallocating the underlying array so that future append() calls will be faster. template<class T> bool G3D::Array< T >::contains ( const T &  e  )  const [inline] Returns true if the given element is in the array. template<class T> void G3D::Array< T >::deleteAll (  )  [inline] Calls delete on all objects[0. ..size-1] and sets the size to zero. template<class T> Iterator G3D::Array< T >::end (  )  [inline] template<class T> ConstIterator G3D::Array< T >::end (  )  const [inline] C++ STL style iterator method. Returns one after the last iterator element. template<class T> void G3D::Array< T >::fastClear (  )  [inline] resize(0, false) template<class T> void G3D::Array< T >::fastRemove ( int  index  )  [inline] Swaps element index with the last element in the array then shrinks the array by one. template<class T> void G3D::Array< T >::fastResize ( int  n  )  [inline] Resizes without shrinking the underlying array. template<class T> ConstIterator G3D::Array< T >::find ( const T &  value  )  const [inline] template<class T> Iterator G3D::Array< T >::find ( const T &  value  )  [inline] Finds an element and returns the iterator to it. If the element isn't found then returns end(). template<class T> int G3D::Array< T >::findIndex ( const T &  value  )  const [inline] Returns the index of (the first occurance of) an index or -1 if not found. template<class T> const T& G3D::Array< T >::first (  )  const [inline] template<class T> T& G3D::Array< T >::first (  )  [inline] Returns element firstIndex(), performing a check in debug mode to ensure that there is at least one. template<class T> int G3D::Array< T >::firstIndex (  )  const [inline] template<class T> const T& G3D::Array< T >::front (  )  const [inline] "The member function returns a reference to the first element of the controlled sequence, which must be non-empty. " For compatibility with std::vector. template<class T> T& G3D::Array< T >::front (  )  [inline] "The member function returns a reference to the first element of the controlled sequence, which must be non-empty. " For compatibility with std::vector. template<class T> const T* G3D::Array< T >::getCArray (  )  const [inline] The array returned is only valid until the next append() or resize call, or the Array is deallocated. template<class T> T* G3D::Array< T >::getCArray (  )  [inline] The array returned is only valid until the next append() or resize call, or the Array is deallocated. template<class T> void G3D::Array< T >::insert ( int  n, const T &  value   ) [inline] Inserts at the specified index and shifts all other elements up by one. template<class T> T& G3D::Array< T >::last (  )  [inline] Returns element lastIndex(). template<class T> const T& G3D::Array< T >::last (  )  const [inline] Returns the last element, performing a check in debug mode that there is at least one element. template<class T> int G3D::Array< T >::lastIndex (  )  const [inline] Returns size() - 1. template<class T> int G3D::Array< T >::length (  )  const [inline] Number of elements in the array. (Same as size; this is just here for convenience). template<class T> void G3D::Array< T >::medianPartition ( Array< T > &  ltMedian, Array< T > &  eqMedian, Array< T > &  gtMedian   ) const [inline] Computes a median partition using the default comparator and a dynamically allocated temporary working array. If the median is not in the array, it is chosen to be the largest value smaller than the true median. template<class T> template<typename Comparator> void G3D::Array< T >::medianPartition ( Array< T > &  ltMedian, Array< T > &  eqMedian, Array< T > &  gtMedian, Array< T > &  tempArray, const Comparator &  comparator   ) const [inline] Paritions the array into those below the median, those above the median, and those elements equal to the median in expected O(n) time using quickselect. If the array has an even number of different elements, the median for partition purposes is the largest value less than the median. Parameters: tempArray  used for working scratch space comparator  see parition() for a discussion. template<class T> T& G3D::Array< T >::middle (  )  [inline] Returns element middleIndex(). template<class T> const T& G3D::Array< T >::middle (  )  const [inline] Returns element middleIndex(). template<class T> int G3D::Array< T >::middleIndex (  )  const [inline] Returns iFloor(size() / 2), throws an assertion in debug mode if the array is empty. template<class T> T& G3D::Array< T >::next (  )  [inline] Pushes a new element onto the end and returns its address. This is the same as A.resize(A.size() + 1, false); A.last() template<class T> Array& G3D::Array< T >::operator= ( const std::vector< T > &  other  )  [inline] template<class T> Array& G3D::Array< T >::operator= ( const Array< T > &  other  )  [inline] Assignment operator. template<class T> const T& G3D::Array< T >::operator[] ( unsigned int  n  )  const [inline] template<class T> const T& G3D::Array< T >::operator[] ( int  n  )  const [inline] Performs bounds checks in debug mode. template<class T> T& G3D::Array< T >::operator[] ( unsigned int  n  )  [inline] template<class T> T& G3D::Array< T >::operator[] ( int  n  )  [inline] Performs bounds checks in debug mode. template<class T> void G3D::Array< T >::partition ( const T &  partitionElement, Array< T > &  ltArray, Array< T > &  eqArray, Array< T > &  gtArray   ) const [inline] Uses < and == on elements to perform a partition. See partition(). template<class T> template<typename Comparator> void G3D::Array< T >::partition ( const T &  partitionElement, Array< T > &  ltArray, Array< T > &  eqArray, Array< T > &  gtArray, const Comparator &  comparator   ) const [inline] The output arrays are resized with fastClear() so that if they are already of the same size as this array no memory is allocated during partitioning. Parameters: comparator  A function, or class instance with an overloaded operator() that compares two elements of type T and returns 0 if they are equal, -1 if the second is smaller, and 1 if the first is smaller (i.e., following the conventions of std::string::compare). For example: int compare(int A, int B) { if (A < B) { return 1; } else if (A == B) { return 0; } else { return -1; } } template<class T> T G3D::Array< T >::pop ( bool  shrinkUnderlyingArrayIfNecessary = true  )  [inline] Removes the last element and returns it. By default, shrinks the underlying array. template<class T> void G3D::Array< T >::pop_back (  )  [inline] "The member function removes the last element of the controlled sequence, which must be non-empty." For compatibility with std::vector. template<class T> void G3D::Array< T >::popDiscard ( bool  shrinkUnderlyingArrayIfNecessary = false  )  [inline] Pops the last element and discards it without returning anything. Faster than pop. By default, does not shrink the underlying array. template<class T> void G3D::Array< T >::push ( const Array< T > &  array  )  [inline] template<class T> void G3D::Array< T >::push ( const T &  value  )  [inline] Pushes an element onto the end (appends). template<class T> void G3D::Array< T >::push_back ( const T &  v  )  [inline] Alias to provide std::vector compatibility. template<class T> const T& G3D::Array< T >::randomElement (  )  const [inline] template<class T> T& G3D::Array< T >::randomElement (  )  [inline] template<class T> void G3D::Array< T >::randomize (  )  [inline] Redistributes the elements so that the new order is statistically independent of the original order. O(n) time. template<class T> void G3D::Array< T >::remove ( int  index, int  count = 1   ) [inline] template<class T> void G3D::Array< T >::remove ( Iterator  element, int  count = 1   ) [inline] Removes count elements from the array referenced either by index or Iterator. template<class T> void G3D::Array< T >::resize ( int  n, bool  shrinkIfNecessary   ) [inline] Parameters: shrinkIfNecessary  if false, memory will never be reallocated when the array shrinks. This makes resizing much faster but can waste memory. template<class T> void G3D::Array< T >::resize ( int  n  )  [inline] Resizes, calling the default constructor for newly created objects and shrinking the underlying array as needed (and calling destructors as needed). template<class T> void G3D::Array< T >::reverse (  )  [inline] Reverse the elements of the array in place. template<class T> int G3D::Array< T >::size (  )  const [inline] Number of elements in the array. template<class T> void G3D::Array< T >::sort ( int  direction = SORT_INCREASING  )  [inline] Sorts the array in increasing order using the > or < operator. To invoke this method on Array<T>, T must override those operator. You can overide these operators as follows: bool T::operator>(const T& other) const { return ...; } bool T::operator<(const T& other) const { return ...; } template<class T> void G3D::Array< T >::sort ( bool(__cdecl *lessThan)(const T &elem1, const T &elem2)   )  [inline] Sort using a specific less-than function, e.g. : bool __cdecl myLT(const MyClass& elem1, const MyClass& elem2) { return elem1.x < elem2.x; } Note that for pointer arrays, the const must come after the class name, e.g., Array<MyClass*> uses: bool __cdecl myLT(MyClass*const& elem1, MyClass*const& elem2) { return elem1->x < elem2->x; } template<class T> template<typename StrictWeakOrdering> void G3D::Array< T >::sortSubArray ( int  beginIndex, int  endIndex, StrictWeakOrdering &  lessThan   ) [inline] The StrictWeakOrdering can be either a class that overloads the function call operator() or a function pointer of the form bool (__cdecl *lessThan)(const T& elem1, const T& elem2). template<class T> void G3D::Array< T >::sortSubArray ( int  beginIndex, int  endIndex, bool(__cdecl *lessThan)(const T &elem1, const T &elem2)    ) [inline] template<class T> void G3D::Array< T >::sortSubArray ( int  beginIndex, int  endIndex, int  direction = SORT_INCREASING   ) [inline] Sorts elements beginIndex through and including endIndex. template<class T> void G3D::Array< T >::swap ( Array< T > &  str  )  [inline] "The member function swaps the controlled sequences between *this and str." Note that this is slower than the optimal std implementation. For compatibility with std::vector. The documentation for this class was generated from the following file: Array.h Hosted by