A class implementing the std::deque interface using a circular buffer to avoid allocations when the size does not exceed a previous allocated capacity. More...

#include <CircularDeque.hpp>

Additional Inherited Members
Public Types inherited from stl_boilerplate::RandomAccessSequence< StaticDeque< T, Capacity >, T, true >
using	value_type
using	reference
using	const_reference
using	pointer
using	const_pointer
using	reverse_iterator
using	const_reverse_iterator
using	difference_type
using	size_type
Public Member Functions inherited from stl_boilerplate::RandomAccessSequence< StaticDeque< T, Capacity >, T, true >
iterator	begin () &
const_iterator	cbegin () const &
iterator	end () &
const_iterator	cend () const &
reverse_iterator	rbegin () &
const_reverse_iterator	crbegin () const &
reverse_iterator	rend () &
const_reverse_iterator	crend () const &
size_type	max_size () const
bool	empty () const
reference	front ()
reference	back ()
reference	at (const size_type n)
Protected Member Functions inherited from stl_boilerplate::RandomAccessSequence< StaticDeque< T, Capacity >, T, true >
RandomAccessSequence &	operator= (const RandomAccessSequence &)=default

Detailed Description

template<typename T>
class CircularDeque< T >

A class implementing the std::deque interface using a circular buffer to avoid allocations when the size does not exceed a previous allocated capacity.

The class is optimized for a small number of elements with many balanced insertions and removals. As such, the capacity is not increased beyond the size required when inserting elements in order to save memory in the steady-state.

Differences from std::deque:

Insertions (including during construction) are O(n) if the previous capacity is exceeded and invalidate all references and iterators. Some cases where multiple insertions happen in the same method are optimized to perform only one reallocation.
Erasing elements from the front of the queue invalidates all iterators (but not references).

This last point is not a fundamental limitation, but could be corrected with a more complicated iterator implementation if the standard behavior is found to be useful.

Note: This class does not behave like a standard circular buffer, in that insertion operations never overwrite existing elements. The circularness is only a reference to the implementation using circular internal storage to avoid allocations.

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

src/DataStructures/CircularDeque.hpp

Additional Inherited Members

Detailed Description