Data structure largely mimicking std::deque, but using single preallocated ring buffer. More...

#include <vecdeque.h>

Public Member Functions
	VecDeque () noexcept=default

void	resize (size_t size)
	Resize the deque to be exactly size size (adding default-constructed elements if needed). More...

void	clear () noexcept
	Resize the deque to be size 0. More...

	~VecDeque ()
	Destroy a deque. More...

VecDeque &	operator= (const VecDeque &other)
	Copy-assign a deque. More...

void	swap (VecDeque &other) noexcept
	Swap two deques. More...

VecDeque &	operator= (VecDeque &&other) noexcept
	Move-assign a deque. More...

	VecDeque (const VecDeque &other)
	Copy-construct a deque. More...

	VecDeque (VecDeque &&other) noexcept
	Move-construct a deque. More...

bool friend	operator== (const VecDeque &a, const VecDeque &b)
	Equality comparison between two deques (only compares size+contents, not capacity). More...

std::strong_ordering friend	operator<=> (const VecDeque &a, const VecDeque &b)
	Comparison between two deques, implementing lexicographic ordering on the contents. More...

void	reserve (size_t capacity)
	Increase the capacity to capacity. More...

void	shrink_to_fit ()
	Make the capacity equal to the size. More...

template<typename... Args>
void	emplace_back (Args &&... args)
	Construct a new element at the end of the deque. More...

void	push_back (T &&elem)
	Move-construct a new element at the end of the deque. More...

void	push_back (const T &elem)
	Copy-construct a new element at the end of the deque. More...

template<typename... Args>
void	emplace_front (Args &&... args)
	Construct a new element at the beginning of the deque. More...

void	push_front (const T &elem)
	Copy-construct a new element at the beginning of the deque. More...

void	push_front (T &&elem)
	Move-construct a new element at the beginning of the deque. More...

void	pop_front ()
	Remove the first element of the deque. More...

void	pop_back ()
	Remove the last element of the deque. More...

T &	front () noexcept
	Get a mutable reference to the first element of the deque. More...

const T &	front () const noexcept
	Get a const reference to the first element of the deque. More...

T &	back () noexcept
	Get a mutable reference to the last element of the deque. More...

const T &	back () const noexcept
	Get a const reference to the last element of the deque. More...

T &	operator[] (size_t idx) noexcept
	Get a mutable reference to the element in the deque at the given index. More...

const T &	operator[] (size_t idx) const noexcept
	Get a const reference to the element in the deque at the given index. More...

bool	empty () const noexcept
	Test whether the contents of this deque is empty. More...

size_t	size () const noexcept
	Get the number of elements in this deque. More...

size_t	capacity () const noexcept
	Get the capacity of this deque (maximum size it can have without reallocating). More...

Private Member Functions
size_t	FirstPart () const noexcept
	Returns the number of populated objects between m_offset and the end of the buffer. More...

void	Reallocate (size_t capacity)

size_t	BufferIndex (size_t pos) const noexcept
	What index in the buffer does logical entry number pos have? More...

void	ResizeDown (size_t size) noexcept
	Specialization of resize() that can only shrink. More...

Private Attributes
T *	m_buffer {nullptr}
	Pointer to allocated memory. More...

size_t	m_offset {0}
	m_buffer + m_offset points to first object in queue. More...

size_t	m_size {0}
	Number of objects in the container. More...

size_t	m_capacity {0}
	The size of m_buffer, expressed as a multiple of the size of T. More...

Friends
void	swap (VecDeque &a, VecDeque &b) noexcept
	Non-member version of swap. More...

Detailed Description

template<typename T>
class VecDeque< T >

Data structure largely mimicking std::deque, but using single preallocated ring buffer.

More efficient and better memory locality than std::deque.
Most operations ({push_,pop_,emplace_,}{front,back}(), operator[], ...) are O(1), unless reallocation is needed (in which case they are O(n)).
Supports reserve(), capacity(), shrink_to_fit() like vectors.
No iterator support.
Data is not stored in a single contiguous block, so no data().

Definition at line 24 of file vecdeque.h.

Constructor & Destructor Documentation

◆ VecDeque() [1/3]

template<typename T >

VecDeque< T >::VecDeque ( )

defaultnoexcept

◆ ~VecDeque()

template<typename T >

VecDeque< T >::~VecDeque ( )

inline

Destroy a deque.

Definition at line 129 of file vecdeque.h.

Here is the call graph for this function:

◆ VecDeque() [2/3]

template<typename T >

VecDeque< T >::VecDeque ( const VecDeque< T > & other )

inline

Copy-construct a deque.

Definition at line 180 of file vecdeque.h.

◆ VecDeque() [3/3]

template<typename T >

VecDeque< T >::VecDeque ( VecDeque< T > && other )

inlinenoexcept

Move-construct a deque.

Definition at line 182 of file vecdeque.h.

Here is the call graph for this function:

Member Function Documentation

◆ back() [1/2]

template<typename T >

const T & VecDeque< T >::back ( ) const

inlinenoexcept

Get a const reference to the last element of the deque.

Requires !empty().

Definition at line 289 of file vecdeque.h.

Here is the call graph for this function:

◆ back() [2/2]

template<typename T >

T & VecDeque< T >::back ( )

inlinenoexcept

Get a mutable reference to the last element of the deque.

Requires !empty().

Definition at line 282 of file vecdeque.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ BufferIndex()

template<typename T >

size_t VecDeque< T >::BufferIndex ( size_t pos ) const

inlineprivatenoexcept

What index in the buffer does logical entry number pos have?

Definition at line 75 of file vecdeque.h.

Here is the caller graph for this function:

◆ capacity()

template<typename T >

size_t VecDeque< T >::capacity ( ) const

inlinenoexcept

Get the capacity of this deque (maximum size it can have without reallocating).

Definition at line 314 of file vecdeque.h.

Here is the caller graph for this function:

◆ clear()

template<typename T >

void VecDeque< T >::clear ( )

inlinenoexcept

Resize the deque to be size 0.

The capacity will remain unchanged.

Definition at line 126 of file vecdeque.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ emplace_back()

template<typename T >

template<typename... Args>

void VecDeque< T >::emplace_back ( Args &&... args )

inline

Construct a new element at the end of the deque.

Definition at line 219 of file vecdeque.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ emplace_front()

template<typename T >

template<typename... Args>

void VecDeque< T >::emplace_front ( Args &&... args )

inline

Construct a new element at the beginning of the deque.

Definition at line 234 of file vecdeque.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ empty()

template<typename T >

bool VecDeque< T >::empty ( ) const

inlinenoexcept

Test whether the contents of this deque is empty.

Definition at line 310 of file vecdeque.h.

Here is the caller graph for this function:

◆ FirstPart()

template<typename T >

size_t VecDeque< T >::FirstPart ( ) const

inlineprivatenoexcept

Returns the number of populated objects between m_offset and the end of the buffer.

Definition at line 37 of file vecdeque.h.

Here is the caller graph for this function:

◆ front() [1/2]

template<typename T >

const T & VecDeque< T >::front ( ) const

inlinenoexcept

Get a const reference to the first element of the deque.

Requires !empty().

Definition at line 275 of file vecdeque.h.

◆ front() [2/2]

template<typename T >

T & VecDeque< T >::front ( )

inlinenoexcept

Get a mutable reference to the first element of the deque.

Requires !empty().

Definition at line 268 of file vecdeque.h.

Here is the caller graph for this function:

◆ operator<=>()

template<typename T >

std::strong_ordering friend VecDeque< T >::operator<=>	(	const VecDeque< T > &	a,
		const VecDeque< T > &	b
	)

inline

Comparison between two deques, implementing lexicographic ordering on the contents.

Definition at line 195 of file vecdeque.h.

◆ operator=() [1/2]

template<typename T >

VecDeque & VecDeque< T >::operator= ( const VecDeque< T > & other )

inline

Copy-assign a deque.

Definition at line 136 of file vecdeque.h.

Here is the call graph for this function:

◆ operator=() [2/2]

template<typename T >

VecDeque & VecDeque< T >::operator= ( VecDeque< T > && other )

inlinenoexcept

Move-assign a deque.

Definition at line 173 of file vecdeque.h.

Here is the call graph for this function:

◆ operator==()

template<typename T >

bool friend VecDeque< T >::operator==	(	const VecDeque< T > &	a,
		const VecDeque< T > &	b
	)

inline

Equality comparison between two deques (only compares size+contents, not capacity).

Definition at line 185 of file vecdeque.h.

◆ operator[]() [1/2]

template<typename T >

const T & VecDeque< T >::operator[] ( size_t idx ) const

inlinenoexcept

Get a const reference to the element in the deque at the given index.

Requires idx < size().

Definition at line 303 of file vecdeque.h.

Here is the call graph for this function:

◆ operator[]() [2/2]

template<typename T >

T & VecDeque< T >::operator[] ( size_t idx )

inlinenoexcept

Get a mutable reference to the element in the deque at the given index.

Requires idx < size().

Definition at line 296 of file vecdeque.h.

Here is the call graph for this function:

◆ pop_back()

template<typename T >

void VecDeque< T >::pop_back ( )

inline

Remove the last element of the deque.

Requires !empty().

Definition at line 260 of file vecdeque.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ pop_front()

template<typename T >

void VecDeque< T >::pop_front ( )

inline

Remove the first element of the deque.

Requires !empty().

Definition at line 250 of file vecdeque.h.

Here is the caller graph for this function:

◆ push_back() [1/2]

template<typename T >

void VecDeque< T >::push_back ( const T & elem )

inline

Copy-construct a new element at the end of the deque.

Definition at line 230 of file vecdeque.h.

Here is the call graph for this function:

◆ push_back() [2/2]

template<typename T >

void VecDeque< T >::push_back ( T && elem )

inline

Move-construct a new element at the end of the deque.

Definition at line 227 of file vecdeque.h.

Here is the call graph for this function:

◆ push_front() [1/2]

template<typename T >

void VecDeque< T >::push_front ( const T & elem )

inline

Copy-construct a new element at the beginning of the deque.

Definition at line 244 of file vecdeque.h.

Here is the call graph for this function:

◆ push_front() [2/2]

template<typename T >

void VecDeque< T >::push_front ( T && elem )

inline

Move-construct a new element at the beginning of the deque.

Definition at line 247 of file vecdeque.h.

Here is the call graph for this function:

◆ Reallocate()

template<typename T >

void VecDeque< T >::Reallocate ( size_t capacity )

inlineprivate

Definition at line 39 of file vecdeque.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ reserve()

template<typename T >

void VecDeque< T >::reserve ( size_t capacity )

inline

Increase the capacity to capacity.

Capacity will not shrink.

Definition at line 206 of file vecdeque.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ resize()

template<typename T >

void VecDeque< T >::resize ( size_t size )

inline

Resize the deque to be exactly size size (adding default-constructed elements if needed).

Definition at line 110 of file vecdeque.h.

Here is the call graph for this function:

◆ ResizeDown()

template<typename T >

void VecDeque< T >::ResizeDown ( size_t size )

inlineprivatenoexcept

Specialization of resize() that can only shrink.

Separate so that clear() can call it without requiring a default T constructor.

Definition at line 89 of file vecdeque.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ shrink_to_fit()

template<typename T >

void VecDeque< T >::shrink_to_fit ( )

inline

Make the capacity equal to the size.

The contents does not change.

Definition at line 212 of file vecdeque.h.

Here is the call graph for this function:

◆ size()

template<typename T >

size_t VecDeque< T >::size ( ) const

inlinenoexcept

Get the number of elements in this deque.

Definition at line 312 of file vecdeque.h.

Here is the caller graph for this function:

◆ swap()

template<typename T >

void VecDeque< T >::swap ( VecDeque< T > & other )

inlinenoexcept

Swap two deques.

Definition at line 161 of file vecdeque.h.

Here is the caller graph for this function:

Friends And Related Function Documentation

◆ swap

template<typename T >

void swap	(	VecDeque< T > &	a,
		VecDeque< T > &	b
	)

friend

Non-member version of swap.

Definition at line 170 of file vecdeque.h.

Member Data Documentation

◆ m_buffer

template<typename T >

T* VecDeque< T >::m_buffer {nullptr}

private

Pointer to allocated memory.

Can contain constructed and uninitialized T objects.

Definition at line 27 of file vecdeque.h.

◆ m_capacity

template<typename T >

size_t VecDeque< T >::m_capacity {0}

private

The size of m_buffer, expressed as a multiple of the size of T.

Definition at line 34 of file vecdeque.h.

◆ m_offset

template<typename T >

size_t VecDeque< T >::m_offset {0}

private

m_buffer + m_offset points to first object in queue.

m_offset = 0 if m_capacity is 0; otherwise 0 <= m_offset < m_capacity.

Definition at line 30 of file vecdeque.h.

◆ m_size

template<typename T >

size_t VecDeque< T >::m_size {0}

private

Number of objects in the container.

0 <= m_size <= m_capacity.

Definition at line 32 of file vecdeque.h.

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

src/util/vecdeque.h

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ VecDeque() [1/3]

◆ ~VecDeque()

◆ VecDeque() [2/3]

◆ VecDeque() [3/3]

Member Function Documentation

◆ back() [1/2]

◆ back() [2/2]

◆ BufferIndex()

◆ capacity()

◆ clear()

◆ emplace_back()

◆ emplace_front()

◆ empty()

◆ FirstPart()

◆ front() [1/2]

◆ front() [2/2]

◆ operator<=>()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ pop_back()

◆ pop_front()

◆ push_back() [1/2]

◆ push_back() [2/2]

◆ push_front() [1/2]

◆ push_front() [2/2]

◆ Reallocate()

◆ reserve()

◆ resize()

◆ ResizeDown()

◆ shrink_to_fit()

◆ size()

◆ swap()

Friends And Related Function Documentation

◆ swap

Member Data Documentation

◆ m_buffer

◆ m_capacity

◆ m_offset

◆ m_size