A (partial) implementation of std::deque allocating its blocks on a MEM_ROOT. More...

#include <mem_root_deque.h>

Classes
struct	Block

class	Iterator

Public Types
using	size_type = size_t
	Used to conform to STL algorithm demands. More...

using	difference_type = ptrdiff_t

using	value_type = Element_type

using	pointer = Element_type *

using	reference = Element_type &

using	const_pointer = const Element_type *

using	const_reference = const Element_type &

using	iterator = Iterator< Element_type >

using	const_iterator = Iterator< const Element_type >

using	reverse_iterator = std::reverse_iterator< iterator >

using	reverse_const_iterator = std::reverse_iterator< const_iterator >

Public Member Functions
	mem_root_deque (MEM_ROOT *mem_root)
	Constructor. Leaves the array in an empty, valid state. More...

	mem_root_deque (const mem_root_deque &other)

mem_root_deque &	operator= (const mem_root_deque &other)

	mem_root_deque (mem_root_deque &&other)

mem_root_deque &	operator= (mem_root_deque &&other)

	~mem_root_deque ()

Element_type &	operator[] (size_t idx) const

bool	push_back (const Element_type &element)
	Adds the given element to the end of the deque. More...

bool	push_back (Element_type &&element)
	Adds the given element to the end of the deque. More...

bool	push_front (const Element_type &element)
	Adds the given element to the beginning of the deque. More...

bool	push_front (Element_type &&element)
	Adds the given element to the end of the deque. More...

void	pop_back ()
	Removes the last element from the deque. More...

void	pop_front ()
	Removes the first element from the deque. More...

Element_type &	front ()
	Returns the first element in the deque. More...

const Element_type &	front () const

Element_type &	back ()
	Returns the last element in the deque. More...

const Element_type &	back () const

void	clear ()
	Removes all elements from the deque. More...

size_t	block_slots () const

size_t	first_block_idx () const

uint8_t	back_growth_exp () const

uint8_t	front_growth_exp () const

size_t	capacity () const

iterator	begin ()

iterator	end ()

reverse_iterator	rbegin ()

reverse_iterator	rend ()

const_iterator	cbegin ()

const_iterator	cend ()

const_iterator	begin () const

const_iterator	end () const

reverse_const_iterator	crbegin () const

reverse_const_iterator	crend () const

reverse_const_iterator	rbegin () const

reverse_const_iterator	rend () const

size_t	size () const

bool	empty () const

iterator	erase (const_iterator first, const_iterator last)
	Erase all the elements in the specified range. More...

iterator	erase (const_iterator position)
	Removes a single element from the array. More...

iterator	insert (const_iterator pos, const Element_type &value)
	Insert an element at a given position. More...

iterator	insert (const_iterator pos, Element_type &&value)
	Insert an element at a given position. More...

template<class ForwardIt >
iterator	insert (const_iterator pos, ForwardIt first, ForwardIt last)

Private Member Functions
void	invalidate_iterators ()

bool	add_initial_block ()
	Adds the first block of elements. More...

bool	add_block_back ()

bool	add_block_front ()

size_t	num_blocks () const

Element_type &	get (size_t physical_idx) const
	Gets a reference to the memory used to store an element with the given physical index, starting from zero. More...

size_t	generation () const

Private Attributes
Block *	m_blocks = nullptr
	Pointer to the first block. More...

size_t	m_begin_idx = 0
	Physical index to the first valid element. More...

size_t	m_end_idx = 0
	Physical index one past the last valid element. More...

size_t	m_capacity = 0
	Number of blocks, multiplied by block_elements. More...

size_t	m_block_slots = 0
	Number of Block slots allocated in m_blocks array. More...

size_t	m_first_block_idx = 0
	Index in m_blocks where the first initialized block is stored. More...

uint8_t	m_back_growth_exp = 0
	Growth exponent for back expansion. More...

uint8_t	m_front_growth_exp = 0
	Growth exponent for front expansion. More...

MEM_ROOT *	m_root
	Pointer to the MEM_ROOT that we store our blocks and elements on. More...

size_t	m_generation = 0
	Incremented each time we make an operation that would invalidate iterators. More...

Static Private Attributes
static constexpr size_t	block_elements = FindElementsPerBlock<Element_type>()
	Number of elements in each block. More...

Detailed Description

template<class Element_type>
class mem_root_deque< Element_type >

A (partial) implementation of std::deque allocating its blocks on a MEM_ROOT.

This class works pretty much like an std::deque with a Mem_root_allocator, and used to be a forwarder to it. However, libstdc++ has a very complicated implementation of std::deque, leading to code blowup (e.g., operator[] is 23 instructions on x86-64, including two branches), and we cannot easily use libc++ on all platforms. This version is instead:

Optimized for small, straight-through machine code (few and simple instructions, few branches).
Optimized for few elements; in particular, zero elements is an important special case, much more so than 10,000.

It gives mostly the same guarantees as std::deque; elements can be inserted efficiently on both front and back [1]. {push,pop}_{front,back} guarantees reference stability except for to removed elements (obviously), and invalidates iterators. (Iterators are forcefully invalidated using asserts.) erase() does the same. Note that unlike std::deque, insert() at begin() will invalidate references. Some functionality, like several constructors, resize(), shrink_to_fit(), swap(), etc. is missing.

The implementation is the same as classic std::deque: Elements are held in blocks of about 1 kB each. Once an element is in a block, it never moves (giving the aforementioned pointer stability). The blocks are held in an array, which can be reallocated when more blocks are needed. The implementation keeps track of the used items in terms of “physical indexes”; element 0 starts at the first byte of the first block, element 1 starts immediately after 0, and so on. So you can have something like (assuming very small blocks of only 4 elements each for the sake of drawing):

   block 0   block 1   block 2
   ↓         ↓         ↓
  [x x 2 3] [4 5 6 7] [8 9 x x]
       ↑                   ↑
       begin_idx = 2       end_idx = 10

end_idx counts as is customary one-past-the-end, so in this case, the elements [2,9) would be valid, and e.g. (*this)[4] would give physical index 6, which points to the third element (index 2) in the middle block (block 1). Inserting a new element at the front is as easy as putting it in physical index 1 and adjusting begin_idx to the left. This means a lookup by index requires some shifting, masking and a double indirect load.

Iterators keep track of which deque they belong to, and what physical index they point to. (So lookup by iterator also requires a double indirect load, but the alternative would be caching the block pointer and having an extra branch when advancing the iterator.) Inserting a new block at the beginning would move around all the physical indexes (which is why iterators get invalidated; we could probably get around this by having an “offset to first block”, but it's likely not worth it.)

[1] The blocks array uses exponential growth (doubling), so insertions are amortized O(1). The blocks array is reallocated rarely (O(log n) times for n insertions).

To support exponential growth, we track additional state beyond the blocks array pointer:

m_block_slots - Total slots in the blocks array (may exceed num_blocks). m_first_block_idx - Index where used blocks start (enables front spare). m_back_growth_exp - Growth exponent for back (next growth adds 2^exp slots). m_front_growth_exp - Growth exponent for front (next growth adds 2^exp slots).

The growth exponents track history, not current state. After growing back 3 times, we've created 1+2+4=7 spare slots. But some may be consumed, so we can't derive the exponent from current spare - we must track it explicitly.

Example: Growth triggered by push_back (back-only expansion)

Initial state (3 used blocks, no spare): m_blocks: [B0][B1][B2] m_first_block_idx: 0 m_block_slots: 3 m_back_growth_exp: 0

After 1st back growth (adds 2^0 = 1 spare slot at back): m_blocks: [B0][B1][B2][ ] ↑ spare m_block_slots: 4 m_back_growth_exp: 1

After 2nd back growth (adds 2^1 = 2 spare slots at back): m_blocks: [B0][B1][B2][B3][ ][ ] ↑ spare m_block_slots: 6 m_back_growth_exp: 2

Example: Growth triggered by push_front (front-only expansion)

Initial state (3 used blocks, no spare at front): m_blocks: [B0][B1][B2] m_first_block_idx: 0 m_front_growth_exp: 0

After 1st front growth (adds 2^0 = 1 spare slot at front): m_blocks: [ ][B0][B1][B2] ↑ spare m_first_block_idx: 1 (new block goes here, then decrements to 0) m_block_slots: 4 m_front_growth_exp: 1

After 2nd front growth (adds 2^1 = 2 spare slots at front): m_blocks: [ ][ ][ ][B0][B1][B2] ↑ spare m_first_block_idx: 3 (new block goes at index 2) m_block_slots: 6 m_front_growth_exp: 2

Each direction grows independently. A deque with many push_back calls will have large m_back_growth_exp but m_front_growth_exp stays 0 until push_front triggers growth.

Member Typedef Documentation

◆ const_iterator

template<class Element_type >

using mem_root_deque< Element_type >::const_iterator = Iterator<const Element_type>

◆ const_pointer

template<class Element_type >

using mem_root_deque< Element_type >::const_pointer = const Element_type *

◆ const_reference

template<class Element_type >

using mem_root_deque< Element_type >::const_reference = const Element_type &

◆ difference_type

template<class Element_type >

using mem_root_deque< Element_type >::difference_type = ptrdiff_t

◆ iterator

template<class Element_type >

using mem_root_deque< Element_type >::iterator = Iterator<Element_type>

◆ pointer

template<class Element_type >

using mem_root_deque< Element_type >::pointer = Element_type *

◆ reference

template<class Element_type >

using mem_root_deque< Element_type >::reference = Element_type &

◆ reverse_const_iterator

template<class Element_type >

using mem_root_deque< Element_type >::reverse_const_iterator = std::reverse_iterator<const_iterator>

◆ reverse_iterator

template<class Element_type >

using mem_root_deque< Element_type >::reverse_iterator = std::reverse_iterator<iterator>

◆ size_type

template<class Element_type >

using mem_root_deque< Element_type >::size_type = size_t

Used to conform to STL algorithm demands.

◆ value_type

template<class Element_type >

using mem_root_deque< Element_type >::value_type = Element_type

Constructor & Destructor Documentation

◆ mem_root_deque() [1/3]

template<class Element_type >

mem_root_deque< Element_type >::mem_root_deque ( MEM_ROOT * mem_root )

inlineexplicit

Constructor. Leaves the array in an empty, valid state.

◆ mem_root_deque() [2/3]

template<class Element_type >

mem_root_deque< Element_type >::mem_root_deque ( const mem_root_deque< Element_type > & other )

inline

◆ mem_root_deque() [3/3]

template<class Element_type >

mem_root_deque< Element_type >::mem_root_deque ( mem_root_deque< Element_type > && other )

inline

◆ ~mem_root_deque()

template<class Element_type >

mem_root_deque< Element_type >::~mem_root_deque ( )

inline

Member Function Documentation

◆ add_block_back()

template<class Element_type >

bool mem_root_deque< Element_type >::add_block_back

private

◆ add_block_front()

template<class Element_type >

bool mem_root_deque< Element_type >::add_block_front

private

◆ add_initial_block()

template<class Element_type >

bool mem_root_deque< Element_type >::add_initial_block ( )

inlineprivate

Adds the first block of elements.

◆ back() [1/2]

template<class Element_type >

Element_type & mem_root_deque< Element_type >::back ( )

inline

Returns the last element in the deque.

◆ back() [2/2]

template<class Element_type >

const Element_type & mem_root_deque< Element_type >::back ( ) const

inline

◆ back_growth_exp()

template<class Element_type >

uint8_t mem_root_deque< Element_type >::back_growth_exp ( ) const

inline

◆ begin() [1/2]

template<class Element_type >

iterator mem_root_deque< Element_type >::begin ( )

inline

◆ begin() [2/2]

template<class Element_type >

const_iterator mem_root_deque< Element_type >::begin ( ) const

inline

◆ block_slots()

template<class Element_type >

size_t mem_root_deque< Element_type >::block_slots ( ) const

inline

◆ capacity()

template<class Element_type >

size_t mem_root_deque< Element_type >::capacity ( ) const

inline

◆ cbegin()

template<class Element_type >

const_iterator mem_root_deque< Element_type >::cbegin ( )

inline

◆ cend()

template<class Element_type >

const_iterator mem_root_deque< Element_type >::cend ( )

inline

◆ clear()

template<class Element_type >

void mem_root_deque< Element_type >::clear ( )

inline

Removes all elements from the deque.

Destructors are called, but since the elements themselves are allocated on the MEM_ROOT, their memory cannot be freed.

◆ crbegin()

template<class Element_type >

reverse_const_iterator mem_root_deque< Element_type >::crbegin ( ) const

inline

◆ crend()

template<class Element_type >

reverse_const_iterator mem_root_deque< Element_type >::crend ( ) const

inline

◆ empty()

template<class Element_type >

bool mem_root_deque< Element_type >::empty ( ) const

inline

◆ end() [1/2]

template<class Element_type >

iterator mem_root_deque< Element_type >::end ( )

inline

◆ end() [2/2]

template<class Element_type >

const_iterator mem_root_deque< Element_type >::end ( ) const

inline

◆ erase() [1/2]

template<class Element_type >

iterator mem_root_deque< Element_type >::erase	(	const_iterator	first,
		const_iterator	last
	)

inline

Erase all the elements in the specified range.

Parameters

first	iterator that points to the first element to remove
last	iterator that points to the element after the last one to remove

Returns: an iterator to the first element after the removed range

◆ erase() [2/2]

template<class Element_type >

iterator mem_root_deque< Element_type >::erase ( const_iterator position )

inline

Removes a single element from the array.

Parameters

position iterator that points to the element to remove

Returns: an iterator to the first element after the removed range

◆ first_block_idx()

template<class Element_type >

size_t mem_root_deque< Element_type >::first_block_idx ( ) const

inline

◆ front() [1/2]

template<class Element_type >

Element_type & mem_root_deque< Element_type >::front ( )

inline

Returns the first element in the deque.

◆ front() [2/2]

template<class Element_type >

const Element_type & mem_root_deque< Element_type >::front ( ) const

inline

◆ front_growth_exp()

template<class Element_type >

uint8_t mem_root_deque< Element_type >::front_growth_exp ( ) const

inline

◆ generation()

template<class Element_type >

size_t mem_root_deque< Element_type >::generation ( ) const

inlineprivate

◆ get()

template<class Element_type >

Element_type & mem_root_deque< Element_type >::get ( size_t physical_idx ) const

inlineprivate

Gets a reference to the memory used to store an element with the given physical index, starting from zero.

Note that block_elements is always a power of two, so the division and modulus operations are cheap.

◆ insert() [1/3]

template<class Element_type >

iterator mem_root_deque< Element_type >::insert	(	const_iterator	pos,
		const Element_type &	value
	)

inline

Insert an element at a given position.

The element is a copy of the given one.

Parameters

pos	the new element is inserted before the element at this position
value	the value of the new element

Returns: an iterator that points to the inserted element

◆ insert() [2/3]

template<class Element_type >

iterator mem_root_deque< Element_type >::insert	(	const_iterator	pos,
		Element_type &&	value
	)

inline

Insert an element at a given position.

The element is moved into place.

Parameters

pos	the new element is inserted before the element at this position
value	the value of the new element

Returns: an iterator that points to the inserted element

◆ insert() [3/3]

template<class Element_type >

template<class ForwardIt >

iterator mem_root_deque< Element_type >::insert	(	const_iterator	pos,
		ForwardIt	first,
		ForwardIt	last
	)

inline

◆ invalidate_iterators()

template<class Element_type >

void mem_root_deque< Element_type >::invalidate_iterators ( )

inlineprivate

◆ num_blocks()

template<class Element_type >

size_t mem_root_deque< Element_type >::num_blocks ( ) const

inlineprivate

◆ operator=() [1/2]

template<class Element_type >

mem_root_deque & mem_root_deque< Element_type >::operator= ( const mem_root_deque< Element_type > & other )

inline

◆ operator=() [2/2]

template<class Element_type >

mem_root_deque & mem_root_deque< Element_type >::operator= ( mem_root_deque< Element_type > && other )

inline

◆ operator[]()

template<class Element_type >

Element_type & mem_root_deque< Element_type >::operator[] ( size_t idx ) const

inline

◆ pop_back()

template<class Element_type >

void mem_root_deque< Element_type >::pop_back ( )

inline

Removes the last element from the deque.

◆ pop_front()

template<class Element_type >

void mem_root_deque< Element_type >::pop_front ( )

inline

Removes the first element from the deque.

◆ push_back() [1/2]

template<class Element_type >

bool mem_root_deque< Element_type >::push_back ( const Element_type & element )

inline

Adds the given element to the end of the deque.

The element is a copy of the given one.

Returns: true on OOM (no change is done if so)

◆ push_back() [2/2]

template<class Element_type >

bool mem_root_deque< Element_type >::push_back ( Element_type && element )

inline

Adds the given element to the end of the deque.

The element is moved into place.

Returns: true on OOM (no change is done if so)

◆ push_front() [1/2]

template<class Element_type >

bool mem_root_deque< Element_type >::push_front ( const Element_type & element )

inline

Adds the given element to the beginning of the deque.

The element is a copy of the given one.

Returns: true on OOM (no change is done if so)

◆ push_front() [2/2]

template<class Element_type >

bool mem_root_deque< Element_type >::push_front ( Element_type && element )

inline

Adds the given element to the end of the deque.

The element is moved into place.

◆ rbegin() [1/2]

template<class Element_type >

reverse_iterator mem_root_deque< Element_type >::rbegin ( )

inline

◆ rbegin() [2/2]

template<class Element_type >

reverse_const_iterator mem_root_deque< Element_type >::rbegin ( ) const

inline

◆ rend() [1/2]

template<class Element_type >

reverse_iterator mem_root_deque< Element_type >::rend ( )

inline

◆ rend() [2/2]

template<class Element_type >

reverse_const_iterator mem_root_deque< Element_type >::rend ( ) const

inline

◆ size()

template<class Element_type >

size_t mem_root_deque< Element_type >::size ( ) const

inline

Member Data Documentation

◆ block_elements

template<class Element_type >

constexpr size_t mem_root_deque< Element_type >::block_elements = FindElementsPerBlock<Element_type>()

staticconstexprprivate

Number of elements in each block.

◆ m_back_growth_exp

template<class Element_type >

uint8_t mem_root_deque< Element_type >::m_back_growth_exp = 0

private

Growth exponent for back expansion.

When push_back needs to grow, we add 2^m_back_growth_exp spare slots at the back, then increment. This gives independent exponential growth: 1, 2, 4, 8, 16...

◆ m_begin_idx

template<class Element_type >

size_t mem_root_deque< Element_type >::m_begin_idx = 0

private

Physical index to the first valid element.

◆ m_block_slots

template<class Element_type >

size_t mem_root_deque< Element_type >::m_block_slots = 0

private

Number of Block slots allocated in m_blocks array.

This may be larger than num_blocks() to allow for exponential growth without reallocating on every new block.

◆ m_blocks

template<class Element_type >

Block* mem_root_deque< Element_type >::m_blocks = nullptr

private

Pointer to the first block.

Can be nullptr if there are no elements (this makes the constructor cheaper). Stored on the MEM_ROOT, and needs no destruction, so just a raw pointer.

◆ m_capacity

template<class Element_type >

size_t mem_root_deque< Element_type >::m_capacity = 0

private

Number of blocks, multiplied by block_elements.

(Storing this instead of the number of blocks itself makes testing in push_back cheaper.)

◆ m_end_idx

template<class Element_type >

size_t mem_root_deque< Element_type >::m_end_idx = 0

private

Physical index one past the last valid element.

If begin == end, the array is empty (and then it doesn't matter what the values are).

◆ m_first_block_idx

template<class Element_type >

size_t mem_root_deque< Element_type >::m_first_block_idx = 0

private

Index in m_blocks where the first initialized block is stored.

Blocks are stored contiguously from m_first_block_idx to m_first_block_idx + num_blocks() - 1. Spare slots before this index can be used for push_front without reallocating.

◆ m_front_growth_exp

template<class Element_type >

uint8_t mem_root_deque< Element_type >::m_front_growth_exp = 0

private

Growth exponent for front expansion.

When push_front needs to grow, we add 2^m_front_growth_exp spare slots at the front, then increment.

◆ m_generation

template<class Element_type >

size_t mem_root_deque< Element_type >::m_generation = 0

private

Incremented each time we make an operation that would invalidate iterators.

Asserts use this value in debug mode to be able to verify that they have not been invalidated. (In optimized mode, using an invalidated iterator incurs undefined behavior.)

◆ m_root

template<class Element_type >

MEM_ROOT* mem_root_deque< Element_type >::m_root

private

Pointer to the MEM_ROOT that we store our blocks and elements on.

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

include/mem_root_deque.h

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ difference_type

◆ iterator

◆ pointer

◆ reference

◆ reverse_const_iterator

◆ reverse_iterator

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ mem_root_deque() [1/3]

◆ mem_root_deque() [2/3]

◆ mem_root_deque() [3/3]

◆ ~mem_root_deque()

Member Function Documentation

◆ add_block_back()

◆ add_block_front()

◆ add_initial_block()

◆ back() [1/2]

◆ back() [2/2]

◆ back_growth_exp()

◆ begin() [1/2]

◆ begin() [2/2]

◆ block_slots()

◆ capacity()

◆ cbegin()

◆ cend()

◆ clear()

◆ crbegin()

◆ crend()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase() [1/2]

◆ erase() [2/2]

◆ first_block_idx()

◆ front() [1/2]

◆ front() [2/2]

◆ front_growth_exp()

◆ generation()

◆ get()

◆ insert() [1/3]

◆ insert() [2/3]

◆ insert() [3/3]

◆ invalidate_iterators()

◆ num_blocks()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator[]()

◆ pop_back()

◆ pop_front()

◆ push_back() [1/2]

◆ push_back() [2/2]

◆ push_front() [1/2]

◆ push_front() [2/2]

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ rend() [1/2]

◆ rend() [2/2]

◆ size()

Member Data Documentation

◆ block_elements

◆ m_back_growth_exp

◆ m_begin_idx

◆ m_block_slots

◆ m_blocks

◆ m_capacity

◆ m_end_idx

◆ m_first_block_idx

◆ m_front_growth_exp