GblArrayDeque Struct Reference

#include <gimbal_array_deque.h>

Collaboration diagram for GblArrayDeque:

Data Fields
struct {
GblRingBuffer   ringBuffer
}	private_

Detailed Description

Circular array-based double-ended queue container.

GblArrayDeque is a very flexible container type which combines the fast random access and cache coherency of a contiguous array with the semantics of a double-ended queue. This means that not only are random accesses extremely efficient, but also adding and removing entries from either end as well.

This container is well-suited for data sets which can grow or shrink from either end, but which are typically accessed as an array.

Operation	Time Complexity
iteration	O(N)
insertion (back or front)	O(1)
insertion (middle)	O(N)
removal (back or front)	O(1)
removal (middle) (WIP)	O(N)
access (front or back)	O(1)
random access (middle)	O(1)

For reference, the following are the results of the profiler unit tests for some common operations shared between GblArrayList (comparable to std::vector) and GblArrayDeque (1024 pointer-sized entries):

Test	GblArrayList	GblArrayDeque
at	0.004 ms	0.008 ms
pushBack	0.030 ms	0.030 ms
pushFront	0.116 ms	0.027 ms

Note

This container can be seen as a slightly more specific, more optimized version of C++'s std::deque. A std::deque also allows for efficient insertion and removal to and from the middle of the array; however, this flexibility comes at the price of increased indirection overhead for random access and increased memory utilization. While GblArrayDeque does support random insertions and deletions, these are more costly than doing so from the front or back, as they require the shuffling around of surrounding elements in memory. We have decided that this trade-off is worth it, since we still support the operation, but fast lookups and lower memory utilization are much higher priorities.

Internally this structure is implemented as an extension of the GblRingBuffer container, which is able to push from the front, pop from the back, and dynamically resize itself as it reaches its capacity.

When the GBL_ARRAY_DEQUE_FORCE_POW2 macro is defined as 1 (default) behavior), the capacity of the deque will always be rounded to the next power-of-two. This means any direct requests to GblArrayDeque_reserve() or GblArrayDeque_shrinkToFit() will not resize the container to the exact value specified. As a consequence of this, lookup times can be optimized by another 15-30% by reducing a modulo operation to a decrement + bitmask.

See also

GblRingBuffer, GblArrayList

Definition at line 93 of file gimbal_array_deque.h.

Field Documentation

ringBuffer

GblRingBuffer GblArrayDeque::ringBuffer

Definition at line 95 of file gimbal_array_deque.h.

---

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

• gimbal_array_deque.h