 |
ezEngine
Release 25.03
|
|
ezEngine
Release 25.03
|
A double ended queue container. More...
#include <Deque.h>
Public Types | |
| using | const_iterator = const_iterator_base< ezDequeBase< T, Construct >, T, false > |
| using | const_reverse_iterator = const_iterator_base< ezDequeBase< T, Construct >, T, true > |
| using | iterator = iterator_base< ezDequeBase< T, Construct >, T, false > |
| using | reverse_iterator = iterator_base< ezDequeBase< T, Construct >, T, true > |
Public Member Functions | |
| void | Clear () |
| Destructs all elements and sets the count to zero. Does not deallocate any data. | |
| void | Reserve (ezUInt32 uiCount) |
| Rearranges the internal data structures such that the amount of reserved elements can be appended with as few allocations, as possible. More... | |
| void | Compact () |
| This function deallocates as much memory as possible to shrink the deque to the bare minimum size that it needs to work. More... | |
| void | Swap (ezDequeBase< T, Construct > &other) |
| swaps the contents of this deque with another one | |
| void | SetCount (ezUInt32 uiCount) |
| Sets the number of active elements in the deque. All new elements are default constructed. If the deque is shrunk, elements at the end of the deque are destructed. | |
| template<typename = void> | |
| void | SetCountUninitialized (ezUInt32 uiCount) |
| \Same as SetCount(), but new elements do not get default constructed. | |
| void | EnsureCount (ezUInt32 uiCount) |
| Ensures the container has at least uiCount elements. Ie. calls SetCount() if the container has fewer elements, does nothing otherwise. | |
| T & | operator[] (ezUInt32 uiIndex) |
| Accesses the n-th element in the deque. | |
| const T & | operator[] (ezUInt32 uiIndex) const |
| Accesses the n-th element in the deque. | |
| T & | ExpandAndGetRef () |
| Grows the deque by one element and returns a reference to the newly created element. | |
| void | PushBack () |
| Adds one default constructed element to the back of the deque. | |
| void | PushBack (const T &element) |
| Adds one element to the back of the deque. | |
| void | PushBack (T &&value) |
| Adds one element at the end of the deque. | |
| void | PopBack (ezUInt32 uiElements=1) |
| Removes the last element from the deque. | |
| void | PushFront (const T &element) |
| Adds one element to the front of the deque. | |
| void | PushFront (T &&element) |
| Adds one element to the front of the deque. | |
| void | PushFront () |
| Adds one default constructed element to the front of the deque. | |
| void | PopFront (ezUInt32 uiElements=1) |
| Removes the first element from the deque. | |
| bool | IsEmpty () const |
| Checks whether no elements are active in the deque. | |
| ezUInt32 | GetCount () const |
| Returns the number of active elements in the deque. | |
| const T & | PeekFront () const |
| Returns the first element. | |
| T & | PeekFront () |
| Returns the first element. | |
| const T & | PeekBack () const |
| Returns the last element. | |
| T & | PeekBack () |
| Returns the last element. | |
| bool | Contains (const T &value) const |
| Checks whether there is any element in the deque with the given value. | |
| ezUInt32 | IndexOf (const T &value, ezUInt32 uiStartIndex=0) const |
| Returns the first index at which an element with the given value could be found or ezInvalidIndex if nothing was found. | |
| ezUInt32 | LastIndexOf (const T &value, ezUInt32 uiStartIndex=ezInvalidIndex) const |
| Returns the last index at which an element with the given value could be found or ezInvalidIndex if nothing was found. | |
| void | RemoveAtAndSwap (ezUInt32 uiIndex) |
| Removes the element at the given index and fills the gap with the last element in the deque. | |
| void | RemoveAtAndCopy (ezUInt32 uiIndex) |
| Removes the element at index and fills the gap by shifting all following elements. | |
| bool | RemoveAndCopy (const T &value) |
| Removes the first occurrence of value and fills the gap by shifting all following elements. | |
| bool | RemoveAndSwap (const T &value) |
| Removes the first occurrence of value and fills the gap with the last element in the deque. | |
| void | InsertAt (ezUInt32 uiIndex, const T &value) |
| Inserts value at index by shifting all following elements. Valid insert positions are [0; GetCount]. | |
| template<typename Comparer > | |
| void | Sort (const Comparer &comparer) |
| Sort with explicit comparer. | |
| void | Sort () |
| Sort with default comparer. | |
| ezAllocator * | GetAllocator () const |
| Returns the allocator that is used by this instance. | |
| ezUInt32 | GetContiguousRange (ezUInt32 uiStartIndex) const |
| Returns the number of elements after uiStartIndex that are stored in contiguous memory. More... | |
| bool | operator== (const ezDequeBase< T, Construct > &rhs) const |
| Comparison operator. | |
| EZ_ADD_DEFAULT_OPERATOR_NOTEQUAL (const ezDequeBase< T, Construct > &) | |
| ezUInt64 | GetHeapMemoryUsage () const |
| Returns the amount of bytes that are currently allocated on the heap. | |
Protected Member Functions | |
| ezDequeBase (ezAllocator *pAllocator) | |
| No memory is allocated during construction. | |
| ezDequeBase (const ezDequeBase< T, Construct > &rhs, ezAllocator *pAllocator) | |
| Constructs this deque by copying from rhs. | |
| ezDequeBase (ezDequeBase< T, Construct > &&rhs, ezAllocator *pAllocator) | |
| Constructs this deque by moving from rhs. | |
| ~ezDequeBase () | |
| Destructor. | |
| void | operator= (const ezDequeBase< T, Construct > &rhs) |
| Assignment operator. | |
| void | operator= (ezDequeBase< T, Construct > &&rhs) |
| Move operator. | |
A double ended queue container.
The deque allocates elements in fixed size chunks (usually around 4KB per chunk), but with at least 32 elements per chunk. It will allocate additional chunks when necessary, but never reallocate already existing data. Therefore it is well suited when it is not known up front how many elements are needed, as it can start with a small amount of data and grow on demand. Also an element in a deque is never moved around in memory, thus it is safe to store pointers to elements inside the deque. The deque uses one redirection to look up elements, for which it uses one index array. Thus a look up into a deque is slightly slower than a pure array lookup, but still very fast, compared to all other containers. Deques can easily grow and shrink at both ends and are thus well suited for use as a FIFO or LIFO queue or even a ring-buffer. It is optimized to even handle the ring-buffer use case without any memory allocations, as long as the buffer does not need to grow.
| void ezDequeBase< T, Construct >::Compact |
This function deallocates as much memory as possible to shrink the deque to the bare minimum size that it needs to work.
This function is never called internally. It is only for the user to trigger a size reduction when he feels like it. The index array data is not reduced as much as possible, a bit spare memory is kept to allow for scaling the deque up again, without immediate reallocation of all data structures. If the deque is completely empty, ALL data is completely deallocated.
|
inline |
Returns the number of elements after uiStartIndex that are stored in contiguous memory.
That means one can do a memcpy or memcmp from position uiStartIndex up until uiStartIndex + range.
| void ezDequeBase< T, Construct >::Reserve | ( | ezUInt32 | uiCount | ) |
Rearranges the internal data structures such that the amount of reserved elements can be appended with as few allocations, as possible.
This does not reserve the actual amount of chunks, that would be needed, but only grows the index array (for redirections) as much as needed. Thus you can use it to reserve enough bookkeeping storage, without actually allocating all that data. In contrast to the ezDynamicArray and ezHybridArray containers, ezDeque does not require you to reserve space up front, to be fast. However, if useful information is available, 'Reserve' can be used to prevent a few unnecessary reallocations of its internal data structures.
1.8.17