A lightweight double ended queue backed by a flat array. More...

#include <geomc/Deque.h>

Public Member Functions
	Deque ()
	Construct a new empty circular buffer, with capacity for `N` items.

	Deque (const Deque< T, N > &other)
	Construct a new circular buffer containing copies of all the items in `other`.

	Deque (Deque< T, N > &&other)
	Move the contents of `other` to a new Deque.

	Deque (index_t capacity)
	Construct a new empty circular buffer, with space for at least `capacity` items.

template<typename InputIterator>
	Deque (InputIterator begin, index_t count)
	Construct a new circular buffer by copying `count` items in the sequence starting at `begin`.

T &	back ()
	Return a reference to the item at the end of the buffer.

const T &	back () const
	Return a const reference to the item at the end of the buffer.

index_t	capacity () const
	Return the total number of items that can be accommodated without an additional memory allocation.

void	clear ()
	Empty the buffer of all items.

T &	front ()
	Return a reference to the item at the beginning of the buffer.

const T &	front () const
	Return a const reference to the item at the beginning of the buffer.

bool	operator!= (const Deque< T, N > &other)
	Inequality operator.

Deque &	operator= (const Deque &other)
	Assignment operator.

Deque &	operator= (Deque &&other)
	Move the contents of `other` to this buffer.

bool	operator== (const Deque< T, N > &other)
	Equality operator.

T &	operator[] (index_t i)
	Get the `i`th element in the buffer.

const T &	operator[] (index_t i) const
	Get the `i`th (const) element in the buffer.

std::optional< T >	pop_back ()
	Remove the element at the end of the buffer, if there is one.

std::optional< T >	pop_front ()
	Remove the first element in the buffer, if there is one.

template<typename U>
T &	push_back (U &&t)
	Add an element to the end of the buffer.

template<typename U>
T &	push_front (U &&t)
	Add an element to the beginning of the buffer.

void	reserve (index_t new_cap)
	Increase the capacity of the circular buffer to a value that's greater or equal to `new_cap`. If `new_cap` is greater than the current capacity, then new storage is allocated; otherwise the method does nothing.

index_t	size () const
	Return the number of items in the buffer.

Protected Member Functions
T *	get ()

const T *	get () const

T *	item (index_t i)

const T *	item (index_t i) const

Detailed Description

template<typename T, index_t N>
class geom::Deque< T, N >

A lightweight double ended queue backed by a flat array.

A deque can accommodate adding elements to either the front or the back of the list in constant time. Random access is also constant time.

Furthermore, indexing off the end of the deque wraps around to the beginning again, as in a circular buffer. This works in both directions.

Template Parameters

T	Element type.
N	Static capacity of the buffer. Adding more than this number of elements to the buffer will incur a heap memory allocation. To always use heap allocation, pass zero to this parameter, in which case memory will be allocated when the first element is added.