irr::core::array< T, TAlloc > Class Template Reference

Self reallocating template array (like stl vector) with additional features. More...

#include <irrArray.h>

Public Types
typedef TAlloc	allocator_type
typedef T	value_type
typedef u32	size_type

Public Member Functions
	array ()
	Default constructor for empty array. More...
	array (u32 start_count)
	Constructs an array and allocates an initial chunk of memory. More...
	array (const array< T, TAlloc > &other)
	Copy constructor. More...
	~array ()
	Destructor. More...
void	reallocate (u32 new_size, bool canShrink=true)
	Reallocates the array, make it bigger or smaller. More...
void	setAllocStrategy (eAllocStrategy newStrategy=ALLOC_STRATEGY_DOUBLE)
	set a new allocation strategy More...
void	push_back (const T &element)
	Adds an element at back of array. More...
void	push_front (const T &element)
	Adds an element at the front of the array. More...
void	insert (const T &element, u32 index=0)
	Insert item into array at specified position. More...
void	clear ()
	Clears the array and deletes all allocated memory. More...
void	set_pointer (T *newPointer, u32 size, bool _is_sorted=false, bool _free_when_destroyed=true)
	Sets pointer to new array, using this as new workspace. More...
void	set_free_when_destroyed (bool f)
	Sets if the array should delete the memory it uses upon destruction. More...
void	set_used (u32 usedNow)
	Sets the size of the array and allocates new elements if necessary. More...
const array< T, TAlloc > &	operator= (const array< T, TAlloc > &other)
	Assignment operator. More...
bool	operator== (const array< T, TAlloc > &other) const
	Equality operator. More...
bool	operator != (const array< T, TAlloc > &other) const
	Inequality operator. More...
T &	operator [] (u32 index)
	Direct access operator. More...
const T &	operator [] (u32 index) const
	Direct const access operator. More...
T &	getLast ()
	Gets last element. More...
const T &	getLast () const
	Gets last element. More...
T *	pointer ()
	Gets a pointer to the array. More...
const T *	const_pointer () const
	Gets a const pointer to the array. More...
u32	size () const
	Get number of occupied elements of the array. More...
u32	allocated_size () const
	Get amount of memory allocated. More...
bool	empty () const
	Check if array is empty. More...
void	sort ()
	Sorts the array using heapsort. More...
s32	binary_search (const T &element)
	Performs a binary search for an element, returns -1 if not found. More...
s32	binary_search (const T &element) const
	Performs a binary search for an element if possible, returns -1 if not found. More...
s32	binary_search (const T &element, s32 left, s32 right) const
	Performs a binary search for an element, returns -1 if not found. More...
s32	binary_search_multi (const T &element, s32 &last)
s32	linear_search (const T &element) const
	Finds an element in linear time, which is very slow. More...
s32	linear_reverse_search (const T &element) const
	Finds an element in linear time, which is very slow. More...
void	erase (u32 index)
	Erases an element from the array. More...
void	erase (u32 index, s32 count)
	Erases some elements from the array. More...
void	set_sorted (bool _is_sorted)
	Sets if the array is sorted. More...
void	swap (array< T, TAlloc > &other)
	Swap the content of this array container with the content of another array. More...

Detailed Description

template<class T, typename TAlloc = irrAllocator<T>>
class irr::core::array< T, TAlloc >

Self reallocating template array (like stl vector) with additional features.

Some features are: Heap sorting, binary search methods, easier debugging.

Definition at line 22 of file irrArray.h.

Member Typedef Documentation

allocator_type

template<class T, typename TAlloc = irrAllocator<T>>

typedef TAlloc irr::core::array< T, TAlloc >::allocator_type

Definition at line 607 of file irrArray.h.

size_type

template<class T, typename TAlloc = irrAllocator<T>>

typedef u32 irr::core::array< T, TAlloc >::size_type

Definition at line 609 of file irrArray.h.

value_type

template<class T, typename TAlloc = irrAllocator<T>>

typedef T irr::core::array< T, TAlloc >::value_type

Definition at line 608 of file irrArray.h.

Constructor & Destructor Documentation

array() [1/3]

template<class T, typename TAlloc = irrAllocator<T>>

irr::core::array< T, TAlloc >::array ( )

inline

Default constructor for empty array.

Definition at line 28 of file irrArray.h.

                : data(0), allocated(0), used(0),
                        strategy(ALLOC_STRATEGY_DOUBLE), free_when_destroyed(true), is_sorted(true)
        {
        }

array() [2/3]

template<class T, typename TAlloc = irrAllocator<T>>

irr::core::array< T, TAlloc >::array ( u32  start_count )

inlineexplicit

Constructs an array and allocates an initial chunk of memory.

Parameters

start_count

Amount of elements to pre-allocate.

Definition at line 36 of file irrArray.h.

                                        : data(0), allocated(0), used(0),
                        strategy(ALLOC_STRATEGY_DOUBLE),
                        free_when_destroyed(true), is_sorted(true)
        {
                reallocate(start_count);
        }

array() [3/3]

template<class T, typename TAlloc = irrAllocator<T>>

irr::core::array< T, TAlloc >::array ( const array< T, TAlloc > &  other )

inline

Copy constructor.

Definition at line 45 of file irrArray.h.

                                             : data(0)
        {
                *this = other;
        }

~array()

template<class T, typename TAlloc = irrAllocator<T>>

irr::core::array< T, TAlloc >::~array ( )

inline

Destructor.

Frees allocated memory, if set_free_when_destroyed was not set to false by the user before.

Definition at line 54 of file irrArray.h.

        {
                clear();
        }

Member Function Documentation

allocated_size()

template<class T, typename TAlloc = irrAllocator<T>>

u32 irr::core::array< T, TAlloc >::allocated_size ( ) const

inline

Get amount of memory allocated.

Returns

Amount of memory allocated. The amount of bytes allocated would be allocated_size() * sizeof(ElementTypeUsed);

Definition at line 373 of file irrArray.h.

        {
                return allocated;
        }

binary_search() [1/3]

template<class T, typename TAlloc = irrAllocator<T>>

s32 irr::core::array< T, TAlloc >::binary_search ( const T &  element )

inline

Performs a binary search for an element, returns -1 if not found.

The array will be sorted before the binary search if it is not already sorted. Caution is advised! Be careful not to call this on unsorted const arrays, or the slower method will be used.

Parameters

element

Element to search for.

Returns

Position of the searched element if it was found, otherwise -1 is returned.

Definition at line 405 of file irrArray.h.

        {
                sort();
                return binary_search(element, 0, used-1);
        }

binary_search() [2/3]

template<class T, typename TAlloc = irrAllocator<T>>

s32 irr::core::array< T, TAlloc >::binary_search ( const T &  element ) const

inline

Performs a binary search for an element if possible, returns -1 if not found.

This method is for const arrays and so cannot call sort(), if the array is not sorted then linear_search will be used instead. Potentially very slow!

Parameters

element

Element to search for.

Returns

Position of the searched element if it was found, otherwise -1 is returned.

Definition at line 418 of file irrArray.h.

        {
                if (is_sorted)
                        return binary_search(element, 0, used-1);
                else
                        return linear_search(element);
        }

binary_search() [3/3]

template<class T, typename TAlloc = irrAllocator<T>>

s32 irr::core::array< T, TAlloc >::binary_search ( const T &  element, s32  left, s32  right  ) const

inline

Performs a binary search for an element, returns -1 if not found.

Parameters

element	Element to search for.
left	First left index
right	Last right index.

Returns

Position of the searched element if it was found, otherwise -1 is returned.

Definition at line 433 of file irrArray.h.

        {
                if (!used)
                        return -1;

                s32 m;

                do
                {
                        m = (left+right)>>1;

                        if (element < data[m])
                                right = m - 1;
                        else
                                left = m + 1;

                } while((element < data[m] || data[m] < element) && left<=right);
                // this last line equals to:
                // " while((element != array[m]) && left<=right);"
                // but we only want to use the '<' operator.
                // the same in next line, it is "(element == array[m])"


                if (!(element < data[m]) && !(data[m] < element))
                        return m;

                return -1;
        }

binary_search_multi()

template<class T, typename TAlloc = irrAllocator<T>>

s32 irr::core::array< T, TAlloc >::binary_search_multi ( const T &  element, s32 &  last  )

inline

Performs a binary search for an element, returns -1 if not found. it is used for searching a multiset The array will be sorted before the binary search if it is not already sorted.

Parameters

element	Element to search for.
&last	return lastIndex of equal elements

Returns

Position of the first searched element if it was found, otherwise -1 is returned.

Definition at line 471 of file irrArray.h.

        {
                sort();
                s32 index = binary_search(element, 0, used-1);
                if ( index < 0 )
                        return index;

                // The search can be somewhere in the middle of the set
                // look linear previous and past the index
                last = index;

                while ( index > 0 && !(element < data[index - 1]) && !(data[index - 1] < element) )
                {
                        index -= 1;
                }
                // look linear up
                while ( last < (s32) used - 1 && !(element < data[last + 1]) && !(data[last + 1] < element) )
                {
                        last += 1;
                }

                return index;
        }

clear()

template<class T, typename TAlloc = irrAllocator<T>>

void irr::core::array< T, TAlloc >::clear ( void  )

inline

Clears the array and deletes all allocated memory.

Definition at line 199 of file irrArray.h.

        {
                if (free_when_destroyed)
                {
                        for (u32 i=0; i<used; ++i)
                                allocator.destruct(&data[i]);

                        allocator.deallocate(data); // delete [] data;
                }
                data = 0;
                used = 0;
                allocated = 0;
                is_sorted = true;
        }

const_pointer()

template<class T, typename TAlloc = irrAllocator<T>>

const T* irr::core::array< T, TAlloc >::const_pointer ( ) const

inline

Gets a const pointer to the array.

Returns

Pointer to the array.

Definition at line 356 of file irrArray.h.

        {
                return data;
        }

empty()

template<class T, typename TAlloc = irrAllocator<T>>

bool irr::core::array< T, TAlloc >::empty ( ) const

inline

Check if array is empty.

Returns

True if the array is empty false if not.

Definition at line 381 of file irrArray.h.

        {
                return used == 0;
        }

erase() [1/2]

template<class T, typename TAlloc = irrAllocator<T>>

void irr::core::array< T, TAlloc >::erase ( u32  index )

inline

Erases an element from the array.

May be slow, because all elements following after the erased element have to be copied.

Parameters

index

Index of element to be erased.

Definition at line 532 of file irrArray.h.

        {
                _IRR_DEBUG_BREAK_IF(index>=used) // access violation

                for (u32 i=index+1; i<used; ++i)
                {
                        allocator.destruct(&data[i-1]);
                        allocator.construct(&data[i-1], data[i]); // data[i-1] = data[i];
                }

                allocator.destruct(&data[used-1]);

                --used;
        }

erase() [2/2]

template<class T, typename TAlloc = irrAllocator<T>>

void irr::core::array< T, TAlloc >::erase ( u32  index, s32  count  )

inline

Erases some elements from the array.

May be slow, because all elements following after the erased element have to be copied.

Parameters

index	Index of the first element to be erased.
count	Amount of elements to be erased.

Definition at line 553 of file irrArray.h.

        {
                if (index>=used || count<1)
                        return;
                if (index+count>used)
                        count = used-index;

                u32 i;
                for (i=index; i<index+count; ++i)
                        allocator.destruct(&data[i]);

                for (i=index+count; i<used; ++i)
                {
                        if (i-count >= index+count) // not already destructed before loop
                                allocator.destruct(&data[i-count]);

                        allocator.construct(&data[i-count], data[i]); // data[i-count] = data[i];

                        if (i >= used-count) // those which are not overwritten
                                allocator.destruct(&data[i]);
                }

                used-= count;
        }

getLast() [1/2]

template<class T, typename TAlloc = irrAllocator<T>>

T& irr::core::array< T, TAlloc >::getLast ( )

inline

Gets last element.

Definition at line 329 of file irrArray.h.

        {
                _IRR_DEBUG_BREAK_IF(!used) // access violation

                return data[used-1];
        }

getLast() [2/2]

template<class T, typename TAlloc = irrAllocator<T>>

const T& irr::core::array< T, TAlloc >::getLast ( ) const

inline

Gets last element.

Definition at line 338 of file irrArray.h.

        {
                _IRR_DEBUG_BREAK_IF(!used) // access violation

                return data[used-1];
        }

insert()

template<class T, typename TAlloc = irrAllocator<T>>

void irr::core::array< T, TAlloc >::insert ( const T &  element, u32  index = 0  )

inline

Insert item into array at specified position.

Parameters

element	Element to be inserted
index	Where position to insert the new element.

Definition at line 132 of file irrArray.h.

        {
                _IRR_DEBUG_BREAK_IF(index>used) // access violation

                if (used + 1 > allocated)
                {
                        // this doesn't work if the element is in the same
                        // array. So we'll copy the element first to be sure
                        // we'll get no data corruption
                        const T e(element);

                        // increase data block
                        u32 newAlloc;
                        switch ( strategy )
                        {
                                case ALLOC_STRATEGY_DOUBLE:
                                        newAlloc = used + 5 + (allocated < 500 ? used : used >> 2);
                                        break;
                                default:
                                case ALLOC_STRATEGY_SAFE:
                                        newAlloc = used + 1;
                                        break;
                        }
                        reallocate( newAlloc);

                        // move array content and construct new element
                        // first move end one up
                        for (u32 i=used; i>index; --i)
                        {
                                if (i<used)
                                        allocator.destruct(&data[i]);
                                allocator.construct(&data[i], data[i-1]); // data[i] = data[i-1];
                        }
                        // then add new element
                        if (used > index)
                                allocator.destruct(&data[index]);
                        allocator.construct(&data[index], e); // data[index] = e;
                }
                else
                {
                        // element inserted not at end
                        if ( used > index )
                        {
                                // create one new element at the end
                                allocator.construct(&data[used], data[used-1]);

                                // move the rest of the array content
                                for (u32 i=used-1; i>index; --i)
                                {
                                        data[i] = data[i-1];
                                }
                                // insert the new element
                                data[index] = element;
                        }
                        else
                        {
                                // insert the new element to the end
                                allocator.construct(&data[index], element);
                        }
                }
                // set to false as we don't know if we have the comparison operators
                is_sorted = false;
                ++used;
        }

linear_reverse_search()

template<class T, typename TAlloc = irrAllocator<T>>

s32 irr::core::array< T, TAlloc >::linear_reverse_search ( const T &  element ) const

inline

Finds an element in linear time, which is very slow.

Use binary_search for faster finding. Only works if ==operator is implemented.

Parameters

element

Element to search for.

Returns

Position of the searched element if it was found, otherwise -1 is returned.

Definition at line 518 of file irrArray.h.

        {
                for (s32 i=used-1; i>=0; --i)
                        if (data[i] == element)
                                return i;

                return -1;
        }

linear_search()

template<class T, typename TAlloc = irrAllocator<T>>

s32 irr::core::array< T, TAlloc >::linear_search ( const T &  element ) const

inline

Finds an element in linear time, which is very slow.

Use binary_search for faster finding. Only works if ==operator is implemented.

Parameters

element

Element to search for.

Returns

Position of the searched element if it was found, otherwise -1 is returned.

Definition at line 502 of file irrArray.h.

        {
                for (u32 i=0; i<used; ++i)
                        if (element == data[i])
                                return (s32)i;

                return -1;
        }

operator !=()

template<class T, typename TAlloc = irrAllocator<T>>

bool irr::core::array< T, TAlloc >::operator != ( const array< T, TAlloc > &  other ) const

inline

Inequality operator.

Definition at line 304 of file irrArray.h.

        {
                return !(*this==other);
        }

operator []() [1/2]

template<class T, typename TAlloc = irrAllocator<T>>

T& irr::core::array< T, TAlloc >::operator [] ( u32  index )

inline

Direct access operator.

Definition at line 311 of file irrArray.h.

        {
                _IRR_DEBUG_BREAK_IF(index>=used) // access violation

                return data[index];
        }

operator []() [2/2]

template<class T, typename TAlloc = irrAllocator<T>>

const T& irr::core::array< T, TAlloc >::operator [] ( u32  index ) const

inline

Direct const access operator.

Definition at line 320 of file irrArray.h.

        {
                _IRR_DEBUG_BREAK_IF(index>=used) // access violation

                return data[index];
        }

operator=()

template<class T, typename TAlloc = irrAllocator<T>>

const array<T, TAlloc>& irr::core::array< T, TAlloc >::operator= ( const array< T, TAlloc > &  other )

inline

Assignment operator.

Definition at line 263 of file irrArray.h.

        {
                if (this == &other)
                        return *this;
                strategy = other.strategy;

                if (data)
                        clear();

                //if (allocated < other.allocated)
                if (other.allocated == 0)
                        data = 0;
                else
                        data = allocator.allocate(other.allocated); // new T[other.allocated];

                used = other.used;
                free_when_destroyed = true;
                is_sorted = other.is_sorted;
                allocated = other.allocated;

                for (u32 i=0; i<other.used; ++i)
                        allocator.construct(&data[i], other.data[i]); // data[i] = other.data[i];

                return *this;
        }

operator==()

template<class T, typename TAlloc = irrAllocator<T>>

bool irr::core::array< T, TAlloc >::operator== ( const array< T, TAlloc > &  other ) const

inline

Equality operator.

Definition at line 291 of file irrArray.h.

        {
                if (used != other.used)
                        return false;

                for (u32 i=0; i<other.used; ++i)
                        if (data[i] != other[i])
                                return false;
                return true;
        }

pointer()

template<class T, typename TAlloc = irrAllocator<T>>

T* irr::core::array< T, TAlloc >::pointer ( )

inline

Gets a pointer to the array.

Returns

Pointer to the array.

Definition at line 348 of file irrArray.h.

        {
                return data;
        }

push_back()

template<class T, typename TAlloc = irrAllocator<T>>

void irr::core::array< T, TAlloc >::push_back ( const T &  element )

inline

Adds an element at back of array.

If the array is too small to add this new element it is made bigger.

Parameters

element

Element to add at the back of the array.

Definition at line 111 of file irrArray.h.

        {
                insert(element, used);
        }

push_front()

template<class T, typename TAlloc = irrAllocator<T>>

void irr::core::array< T, TAlloc >::push_front ( const T &  element )

inline

Adds an element at the front of the array.

If the array is to small to add this new element, the array is made bigger. Please note that this is slow, because the whole array needs to be copied for this.

Parameters

element

Element to add at the back of the array.

Definition at line 122 of file irrArray.h.

        {
                insert(element);
        }

reallocate()

template<class T, typename TAlloc = irrAllocator<T>>

void irr::core::array< T, TAlloc >::reallocate ( u32  new_size, bool  canShrink = true  )

inline

Reallocates the array, make it bigger or smaller.

Parameters

new_size	New size of array.
canShrink	Specifies whether the array is reallocated even if enough space is available. Setting this flag to false can speed up array usage, but may use more memory than required by the data.

Definition at line 66 of file irrArray.h.

        {
                if (allocated==new_size)
                        return;
                if (!canShrink && (new_size < allocated))
                        return;

                T* old_data = data;

                data = allocator.allocate(new_size); //new T[new_size];
                allocated = new_size;

                // copy old data
                const s32 end = used < new_size ? used : new_size;

                for (s32 i=0; i<end; ++i)
                {
                        // data[i] = old_data[i];
                        allocator.construct(&data[i], old_data[i]);
                }

                // destruct old data
                for (u32 j=0; j<used; ++j)
                        allocator.destruct(&old_data[j]);

                if (allocated < used)
                        used = allocated;

                allocator.deallocate(old_data); //delete [] old_data;
        }

set_free_when_destroyed()

template<class T, typename TAlloc = irrAllocator<T>>

void irr::core::array< T, TAlloc >::set_free_when_destroyed ( bool  f )

inline

Sets if the array should delete the memory it uses upon destruction.

Also clear and set_pointer will only delete the (original) memory area if this flag is set to true, which is also the default. The methods reallocate, set_used, push_back, push_front, insert, and erase will still try to deallocate the original memory, which might cause troubles depending on the intended use of the memory area.

Parameters

f	If true, the array frees the allocated memory in its destructor, otherwise not. The default is true.

Definition at line 243 of file irrArray.h.

        {
                free_when_destroyed = f;
        }

set_pointer()

template<class T, typename TAlloc = irrAllocator<T>>

void irr::core::array< T, TAlloc >::set_pointer ( T *  newPointer, u32  size, bool  _is_sorted = false, bool  _free_when_destroyed = true  )

inline

Sets pointer to new array, using this as new workspace.

Make sure that set_free_when_destroyed is used properly.

Parameters

newPointer	Pointer to new array of elements.
size	Size of the new array.
_is_sorted	Flag which tells whether the new array is already sorted.
_free_when_destroyed	Sets whether the new memory area shall be freed by the array upon destruction, or if this will be up to the user application.

Definition at line 224 of file irrArray.h.

        {
                clear();
                data = newPointer;
                allocated = size;
                used = size;
                is_sorted = _is_sorted;
                free_when_destroyed=_free_when_destroyed;
        }

set_sorted()

template<class T, typename TAlloc = irrAllocator<T>>

void irr::core::array< T, TAlloc >::set_sorted ( bool  _is_sorted )

inline

Sets if the array is sorted.

Definition at line 580 of file irrArray.h.

        {
                is_sorted = _is_sorted;
        }

set_used()

template<class T, typename TAlloc = irrAllocator<T>>

void irr::core::array< T, TAlloc >::set_used ( u32  usedNow )

inline

Sets the size of the array and allocates new elements if necessary.

Please note: This is only secure when using it with simple types, because no default constructor will be called for the added elements.

Parameters

usedNow

Amount of elements now used.

Definition at line 253 of file irrArray.h.

        {
                if (allocated < usedNow)
                        reallocate(usedNow);

                used = usedNow;
        }

setAllocStrategy()

template<class T, typename TAlloc = irrAllocator<T>>

void irr::core::array< T, TAlloc >::setAllocStrategy ( eAllocStrategy  newStrategy = ALLOC_STRATEGY_DOUBLE )

inline

set a new allocation strategy

if the maximum size of the array is unknown, you can define how big the allocation should happen.

Parameters

newStrategy

New strategy to apply to this array.

Definition at line 102 of file irrArray.h.

        {
                strategy = newStrategy;
        }

size()

template<class T, typename TAlloc = irrAllocator<T>>

u32 irr::core::array< T, TAlloc >::size ( ) const

inline

Get number of occupied elements of the array.

Returns

Size of elements in the array which are actually occupied.

Definition at line 364 of file irrArray.h.

        {
                return used;
        }

sort()

template<class T, typename TAlloc = irrAllocator<T>>

void irr::core::array< T, TAlloc >::sort ( )

inline

Sorts the array using heapsort.

There is no additional memory waste and the algorithm performs O(n*log n) in worst case.

Definition at line 390 of file irrArray.h.

        {
                if (!is_sorted && used>1)
                        heapsort(data, used);
                is_sorted = true;
        }

swap()

template<class T, typename TAlloc = irrAllocator<T>>

void irr::core::array< T, TAlloc >::swap ( array< T, TAlloc > &  other )

inline

Swap the content of this array container with the content of another array.

Afterward this object will contain the content of the other object and the other object will contain the content of this object.

Parameters

other

Swap content with this object

Definition at line 590 of file irrArray.h.

        {
                core::swap(data, other.data);
                core::swap(allocated, other.allocated);
                core::swap(used, other.used);
                core::swap(allocator, other.allocator); // memory is still released by the same allocator used for allocation
                eAllocStrategy helper_strategy(strategy); // can't use core::swap with bitfields
                strategy = other.strategy;
                other.strategy = helper_strategy;
                bool helper_free_when_destroyed(free_when_destroyed);
                free_when_destroyed = other.free_when_destroyed;
                other.free_when_destroyed = helper_free_when_destroyed;
                bool helper_is_sorted(is_sorted);
                is_sorted = other.is_sorted;
                other.is_sorted = helper_is_sorted;
        }

---

The documentation for this class was generated from the following file:

• include/irrlicht/irrArray.h