Class that mimics std::deque<bool>, but with std::vector<bool>'s bit packing. More...

#include <bitdeque.h>

Classes
class	Iterator
	Iterator to a bitdeque element, const or not. More...

Public Types
using	value_type = bool

using	size_type = std::size_t

using	difference_type = typename deque_type::difference_type

using	reference = typename word_type::reference

using	const_reference = bool

using	iterator = Iterator< false >

using	const_iterator = Iterator< true >

using	pointer = void

using	const_pointer = void

using	reverse_iterator = std::reverse_iterator< iterator >

using	const_reverse_iterator = std::reverse_iterator< const_iterator >

Public Member Functions
	bitdeque ()
	Construct an empty container.

void	assign (size_type count, bool val)
	Set the container equal to count times the value of val.

	bitdeque (size_type count, bool val)
	Construct a container containing count times the value of val.

	bitdeque (size_t count)
	Construct a container containing count false values.

	bitdeque (const bitdeque &)=default
	Copy constructor.

	bitdeque (bitdeque &&) noexcept=default
	Move constructor.

bitdeque &	operator= (const bitdeque &other)=default
	Copy assignment operator.

bitdeque &	operator= (bitdeque &&other) noexcept=default
	Move assignment operator.

iterator	begin () noexcept

iterator	end () noexcept

const_iterator	begin () const noexcept

const_iterator	cbegin () const noexcept

const_iterator	end () const noexcept

const_iterator	cend () const noexcept

reverse_iterator	rbegin () noexcept

reverse_iterator	rend () noexcept

const_reverse_iterator	rbegin () const noexcept

const_reverse_iterator	crbegin () const noexcept

const_reverse_iterator	rend () const noexcept

const_reverse_iterator	crend () const noexcept

size_type	size () const noexcept
	Count the number of bits in the container.

bool	empty () const noexcept
	Determine whether the container is empty.

size_type	max_size () const noexcept
	Return the maximum size of the container.

template<typename It >
void	assign (It first, It last)
	Set the container equal to the bits in [first,last).

void	assign (std::initializer_list< bool > ilist)
	Set the container equal to the bits in ilist.

bitdeque &	operator= (std::initializer_list< bool > ilist)
	Set the container equal to the bits in ilist.

template<typename It >
	bitdeque (It first, It last)
	Construct a container containing the bits in [first,last).

	bitdeque (std::initializer_list< bool > ilist)
	Construct a container containing the bits in ilist.

reference	at (size_type position)

const_reference	at (size_type position) const

reference	operator[] (size_type position)

const_reference	operator[] (size_type position) const

reference	front ()

const_reference	front () const

reference	back ()

const_reference	back () const

void	shrink_to_fit ()
	Release unused memory.

void	clear () noexcept
	Empty the container.

void	push_back (bool val)

reference	emplace_back (bool val)

void	push_front (bool val)

reference	emplace_front (bool val)

void	pop_back ()

void	pop_front ()

void	resize (size_type n)
	Resize the container.

void	swap (bitdeque &other) noexcept

iterator	erase (const_iterator first, const_iterator last)

iterator	erase (iterator first, iterator last)

iterator	erase (const_iterator pos)

iterator	erase (iterator pos)

iterator	insert (const_iterator pos, bool val)

iterator	emplace (const_iterator pos, bool val)

iterator	insert (const_iterator pos, size_type count, bool val)

template<typename It >
iterator	insert (const_iterator pos, It first, It last)

Private Types
using	word_type = std::bitset< BlobSize >

using	deque_type = std::deque< word_type >

Private Member Functions
void	erase_back (size_type n)
	Shrink the container by n bits, removing from the end.

void	extend_back (size_type n)
	Extend the container by n bits, adding at the end.

void	erase_front (size_type n)
	Shrink the container by n bits, removing from the beginning.

void	extend_front (size_type n)
	Extend the container by n bits, adding at the beginning.

void	insert_zeroes (size_type before, size_type count)
	Insert a sequence of falses anywhere in the container.

Private Attributes
deque_type	m_deque
	Deque of bitsets storing the actual bit data.

int	m_pad_begin
	Number of unused bits at the front of m_deque.front().

int	m_pad_end
	Number of unused bits at the back of m_deque.back().

Static Private Attributes
static constexpr int	BITS_PER_WORD = BlobSize

Friends
template<bool Const>
class	Iterator

void	swap (bitdeque &b1, bitdeque &b2) noexcept

Detailed Description

template<int BlobSize = 4096 * 8>
class bitdeque< BlobSize >

Class that mimics std::deque<bool>, but with std::vector<bool>'s bit packing.

BlobSize selects the (minimum) number of bits that are allocated at once. Larger values reduce the asymptotic memory usage overhead, at the cost of needing larger up-front allocations. The default is 4096 bytes.

Definition at line 22 of file bitdeque.h.

Member Typedef Documentation

◆ const_iterator

template<int BlobSize = 4096 * 8>

using bitdeque< BlobSize >::const_iterator = Iterator<true>

Definition at line 166 of file bitdeque.h.

◆ const_pointer

template<int BlobSize = 4096 * 8>

using bitdeque< BlobSize >::const_pointer = void

Definition at line 168 of file bitdeque.h.

◆ const_reference

template<int BlobSize = 4096 * 8>

using bitdeque< BlobSize >::const_reference = bool

Definition at line 164 of file bitdeque.h.

◆ const_reverse_iterator

template<int BlobSize = 4096 * 8>

using bitdeque< BlobSize >::const_reverse_iterator = std::reverse_iterator<const_iterator>

Definition at line 170 of file bitdeque.h.

◆ deque_type

template<int BlobSize = 4096 * 8>

using bitdeque< BlobSize >::deque_type = std::deque<word_type>

private

Definition at line 25 of file bitdeque.h.

◆ difference_type

template<int BlobSize = 4096 * 8>

using bitdeque< BlobSize >::difference_type = typename deque_type::difference_type

Definition at line 162 of file bitdeque.h.

◆ iterator

template<int BlobSize = 4096 * 8>

using bitdeque< BlobSize >::iterator = Iterator<false>

Definition at line 165 of file bitdeque.h.

◆ pointer

template<int BlobSize = 4096 * 8>

using bitdeque< BlobSize >::pointer = void

Definition at line 167 of file bitdeque.h.

◆ reference

template<int BlobSize = 4096 * 8>

using bitdeque< BlobSize >::reference = typename word_type::reference

Definition at line 163 of file bitdeque.h.

◆ reverse_iterator

template<int BlobSize = 4096 * 8>

using bitdeque< BlobSize >::reverse_iterator = std::reverse_iterator<iterator>

Definition at line 169 of file bitdeque.h.

◆ size_type

template<int BlobSize = 4096 * 8>

using bitdeque< BlobSize >::size_type = std::size_t

Definition at line 161 of file bitdeque.h.

◆ value_type

template<int BlobSize = 4096 * 8>

using bitdeque< BlobSize >::value_type = bool

Definition at line 160 of file bitdeque.h.

◆ word_type

template<int BlobSize = 4096 * 8>

using bitdeque< BlobSize >::word_type = std::bitset<BlobSize>

private

Definition at line 24 of file bitdeque.h.

Constructor & Destructor Documentation

◆ bitdeque() [1/7]

template<int BlobSize = 4096 * 8>

bitdeque< BlobSize >::bitdeque ( )

inlineexplicit

Construct an empty container.

Definition at line 257 of file bitdeque.h.

◆ bitdeque() [2/7]

template<int BlobSize = 4096 * 8>

bitdeque< BlobSize >::bitdeque	(	size_type	count,
		bool	val
	)

inline

Construct a container containing count times the value of val.

Definition at line 275 of file bitdeque.h.

Here is the call graph for this function:

◆ bitdeque() [3/7]

template<int BlobSize = 4096 * 8>

bitdeque< BlobSize >::bitdeque ( size_t count )

inlineexplicit

Construct a container containing count false values.

Definition at line 278 of file bitdeque.h.

Here is the call graph for this function:

◆ bitdeque() [4/7]

template<int BlobSize = 4096 * 8>

bitdeque< BlobSize >::bitdeque ( const bitdeque< BlobSize > & )

default

Copy constructor.

◆ bitdeque() [5/7]

template<int BlobSize = 4096 * 8>

bitdeque< BlobSize >::bitdeque ( bitdeque< BlobSize > && )

defaultnoexcept

Move constructor.

◆ bitdeque() [6/7]

template<int BlobSize = 4096 * 8>

template<typename It >

bitdeque< BlobSize >::bitdeque	(	It	first,
		It	last
	)

inline

Construct a container containing the bits in [first,last).

Definition at line 371 of file bitdeque.h.

Here is the call graph for this function:

◆ bitdeque() [7/7]

template<int BlobSize = 4096 * 8>

bitdeque< BlobSize >::bitdeque ( std::initializer_list< bool > ilist )

inline

Construct a container containing the bits in ilist.

Definition at line 374 of file bitdeque.h.

Here is the call graph for this function:

Member Function Documentation

◆ assign() [1/3]

template<int BlobSize = 4096 * 8>

template<typename It >

void bitdeque< BlobSize >::assign	(	It	first,
		It	last
	)

inline

Set the container equal to the bits in [first,last).

Definition at line 345 of file bitdeque.h.

Here is the call graph for this function:

◆ assign() [2/3]

template<int BlobSize = 4096 * 8>

void bitdeque< BlobSize >::assign	(	size_type	count,
		bool	val
	)

inline

Set the container equal to count times the value of val.

Definition at line 260 of file bitdeque.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ assign() [3/3]

template<int BlobSize = 4096 * 8>

void bitdeque< BlobSize >::assign ( std::initializer_list< bool > ilist )

inline

Set the container equal to the bits in ilist.

Definition at line 355 of file bitdeque.h.

Here is the call graph for this function:

◆ at() [1/2]

template<int BlobSize = 4096 * 8>

reference bitdeque< BlobSize >::at ( size_type position )

inline

Definition at line 377 of file bitdeque.h.

Here is the call graph for this function:

◆ at() [2/2]

template<int BlobSize = 4096 * 8>

const_reference bitdeque< BlobSize >::at ( size_type position ) const

inline

Definition at line 382 of file bitdeque.h.

Here is the call graph for this function:

◆ back() [1/2]

template<int BlobSize = 4096 * 8>

reference bitdeque< BlobSize >::back ( )

inline

Definition at line 395 of file bitdeque.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ back() [2/2]

template<int BlobSize = 4096 * 8>

const_reference bitdeque< BlobSize >::back ( ) const

inline

Definition at line 396 of file bitdeque.h.

Here is the call graph for this function:

◆ begin() [1/2]

template<int BlobSize = 4096 * 8>

const_iterator bitdeque< BlobSize >::begin ( ) const

inlinenoexcept

Definition at line 295 of file bitdeque.h.

◆ begin() [2/2]

template<int BlobSize = 4096 * 8>

iterator bitdeque< BlobSize >::begin ( )

inlinenoexcept

Definition at line 293 of file bitdeque.h.

Here is the caller graph for this function:

◆ cbegin()

template<int BlobSize = 4096 * 8>

const_iterator bitdeque< BlobSize >::cbegin ( ) const

inlinenoexcept

Definition at line 298 of file bitdeque.h.

Here is the caller graph for this function:

◆ cend()

template<int BlobSize = 4096 * 8>

const_iterator bitdeque< BlobSize >::cend ( ) const

inlinenoexcept

Definition at line 304 of file bitdeque.h.

Here is the caller graph for this function:

◆ clear()

template<int BlobSize = 4096 * 8>

void bitdeque< BlobSize >::clear ( )

inlinenoexcept

Empty the container.

Definition at line 402 of file bitdeque.h.

◆ crbegin()

template<int BlobSize = 4096 * 8>

const_reverse_iterator bitdeque< BlobSize >::crbegin ( ) const

inlinenoexcept

Definition at line 312 of file bitdeque.h.

Here is the call graph for this function:

◆ crend()

template<int BlobSize = 4096 * 8>

const_reverse_iterator bitdeque< BlobSize >::crend ( ) const

inlinenoexcept

Definition at line 318 of file bitdeque.h.

Here is the call graph for this function:

◆ emplace()

template<int BlobSize = 4096 * 8>

iterator bitdeque< BlobSize >::emplace	(	const_iterator	pos,
		bool	val
	)

inline

Definition at line 487 of file bitdeque.h.

Here is the call graph for this function:

◆ emplace_back()

template<int BlobSize = 4096 * 8>

reference bitdeque< BlobSize >::emplace_back ( bool val )

inline

Definition at line 412 of file bitdeque.h.

Here is the call graph for this function:

◆ emplace_front()

template<int BlobSize = 4096 * 8>

reference bitdeque< BlobSize >::emplace_front ( bool val )

inline

Definition at line 424 of file bitdeque.h.

Here is the call graph for this function:

◆ empty()

template<int BlobSize = 4096 * 8>

bool bitdeque< BlobSize >::empty ( ) const

inlinenoexcept

Determine whether the container is empty.

Definition at line 328 of file bitdeque.h.

◆ end() [1/2]

template<int BlobSize = 4096 * 8>

const_iterator bitdeque< BlobSize >::end ( ) const

inlinenoexcept

Definition at line 301 of file bitdeque.h.

◆ end() [2/2]

template<int BlobSize = 4096 * 8>

iterator bitdeque< BlobSize >::end ( )

inlinenoexcept

Definition at line 294 of file bitdeque.h.

Here is the caller graph for this function:

◆ erase() [1/4]

template<int BlobSize = 4096 * 8>

iterator bitdeque< BlobSize >::erase	(	const_iterator	first,
		const_iterator	last
	)

inline

Definition at line 455 of file bitdeque.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ erase() [2/4]

template<int BlobSize = 4096 * 8>

iterator bitdeque< BlobSize >::erase ( const_iterator pos )

inline

Definition at line 473 of file bitdeque.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ erase() [3/4]

template<int BlobSize = 4096 * 8>

iterator bitdeque< BlobSize >::erase	(	iterator	first,
		iterator	last
	)

inline

Definition at line 470 of file bitdeque.h.

Here is the call graph for this function:

◆ erase() [4/4]

template<int BlobSize = 4096 * 8>

iterator bitdeque< BlobSize >::erase ( iterator pos )

inline

Definition at line 474 of file bitdeque.h.

Here is the call graph for this function:

◆ erase_back()

template<int BlobSize = 4096 * 8>

void bitdeque< BlobSize >::erase_back ( size_type n )

inlineprivate

Shrink the container by n bits, removing from the end.

Definition at line 183 of file bitdeque.h.

Here is the caller graph for this function:

◆ erase_front()

template<int BlobSize = 4096 * 8>

void bitdeque< BlobSize >::erase_front ( size_type n )

inlineprivate

Shrink the container by n bits, removing from the beginning.

Definition at line 213 of file bitdeque.h.

Here is the caller graph for this function:

◆ extend_back()

template<int BlobSize = 4096 * 8>

void bitdeque< BlobSize >::extend_back ( size_type n )

inlineprivate

Extend the container by n bits, adding at the end.

Definition at line 202 of file bitdeque.h.

Here is the caller graph for this function:

◆ extend_front()

template<int BlobSize = 4096 * 8>

void bitdeque< BlobSize >::extend_front ( size_type n )

inlineprivate

Extend the container by n bits, adding at the beginning.

Definition at line 232 of file bitdeque.h.

Here is the caller graph for this function:

◆ front() [1/2]

template<int BlobSize = 4096 * 8>

reference bitdeque< BlobSize >::front ( )

inline

Definition at line 393 of file bitdeque.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ front() [2/2]

template<int BlobSize = 4096 * 8>

const_reference bitdeque< BlobSize >::front ( ) const

inline

Definition at line 394 of file bitdeque.h.

Here is the call graph for this function:

◆ insert() [1/3]

template<int BlobSize = 4096 * 8>

iterator bitdeque< BlobSize >::insert	(	const_iterator	pos,
		bool	val
	)

inline

Definition at line 479 of file bitdeque.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert() [2/3]

template<int BlobSize = 4096 * 8>

template<typename It >

iterator bitdeque< BlobSize >::insert	(	const_iterator	pos,
		It	first,
		It	last
	)

inline

Definition at line 501 of file bitdeque.h.

Here is the call graph for this function:

◆ insert() [3/3]

template<int BlobSize = 4096 * 8>

iterator bitdeque< BlobSize >::insert	(	const_iterator	pos,
		size_type	count,
		bool	val
	)

inline

Definition at line 489 of file bitdeque.h.

Here is the call graph for this function:

◆ insert_zeroes()

template<int BlobSize = 4096 * 8>

void bitdeque< BlobSize >::insert_zeroes	(	size_type	before,
		size_type	count
	)

inlineprivate

Insert a sequence of falses anywhere in the container.

Definition at line 243 of file bitdeque.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ max_size()

template<int BlobSize = 4096 * 8>

size_type bitdeque< BlobSize >::max_size ( ) const

inlinenoexcept

Return the maximum size of the container.

Definition at line 335 of file bitdeque.h.

◆ operator=() [1/3]

template<int BlobSize = 4096 * 8>

bitdeque & bitdeque< BlobSize >::operator= ( bitdeque< BlobSize > && other )

defaultnoexcept

Move assignment operator.

◆ operator=() [2/3]

template<int BlobSize = 4096 * 8>

bitdeque & bitdeque< BlobSize >::operator= ( const bitdeque< BlobSize > & other )

default

Copy assignment operator.

◆ operator=() [3/3]

template<int BlobSize = 4096 * 8>

bitdeque & bitdeque< BlobSize >::operator= ( std::initializer_list< bool > ilist )

inline

Set the container equal to the bits in ilist.

Definition at line 365 of file bitdeque.h.

Here is the call graph for this function:

◆ operator[]() [1/2]

template<int BlobSize = 4096 * 8>

reference bitdeque< BlobSize >::operator[] ( size_type position )

inline

Definition at line 389 of file bitdeque.h.

Here is the call graph for this function:

◆ operator[]() [2/2]

template<int BlobSize = 4096 * 8>

const_reference bitdeque< BlobSize >::operator[] ( size_type position ) const

inline

Definition at line 390 of file bitdeque.h.

Here is the call graph for this function:

◆ pop_back()

template<int BlobSize = 4096 * 8>

void bitdeque< BlobSize >::pop_back ( )

inline

Definition at line 432 of file bitdeque.h.

Here is the call graph for this function:

◆ pop_front()

template<int BlobSize = 4096 * 8>

void bitdeque< BlobSize >::pop_front ( )

inline

Definition at line 435 of file bitdeque.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ push_back()

template<int BlobSize = 4096 * 8>

void bitdeque< BlobSize >::push_back ( bool val )

inline

Definition at line 408 of file bitdeque.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ push_front()

template<int BlobSize = 4096 * 8>

void bitdeque< BlobSize >::push_front ( bool val )

inline

Definition at line 420 of file bitdeque.h.

Here is the call graph for this function:

◆ rbegin() [1/2]

template<int BlobSize = 4096 * 8>

const_reverse_iterator bitdeque< BlobSize >::rbegin ( ) const

inlinenoexcept

Definition at line 309 of file bitdeque.h.

Here is the call graph for this function:

◆ rbegin() [2/2]

template<int BlobSize = 4096 * 8>

reverse_iterator bitdeque< BlobSize >::rbegin ( )

inlinenoexcept

Definition at line 307 of file bitdeque.h.

Here is the call graph for this function:

◆ rend() [1/2]

template<int BlobSize = 4096 * 8>

const_reverse_iterator bitdeque< BlobSize >::rend ( ) const

inlinenoexcept

Definition at line 315 of file bitdeque.h.

Here is the call graph for this function:

◆ rend() [2/2]

template<int BlobSize = 4096 * 8>

reverse_iterator bitdeque< BlobSize >::rend ( )

inlinenoexcept

Definition at line 308 of file bitdeque.h.

Here is the call graph for this function:

◆ resize()

template<int BlobSize = 4096 * 8>

void bitdeque< BlobSize >::resize ( size_type n )

inline

Resize the container.

Definition at line 438 of file bitdeque.h.

Here is the call graph for this function:

◆ shrink_to_fit()

template<int BlobSize = 4096 * 8>

void bitdeque< BlobSize >::shrink_to_fit ( )

inline

Release unused memory.

Definition at line 399 of file bitdeque.h.

◆ size()

template<int BlobSize = 4096 * 8>

size_type bitdeque< BlobSize >::size ( ) const

inlinenoexcept

Count the number of bits in the container.

Definition at line 323 of file bitdeque.h.

Here is the caller graph for this function:

◆ swap()

template<int BlobSize = 4096 * 8>

void bitdeque< BlobSize >::swap ( bitdeque< BlobSize > & other )

inlinenoexcept

Definition at line 447 of file bitdeque.h.

Friends And Related Symbol Documentation

◆ Iterator

template<int BlobSize = 4096 * 8>

template<bool Const>

friend class Iterator

friend

Definition at line 31 of file bitdeque.h.

◆ swap

template<int BlobSize = 4096 * 8>

void swap	(	bitdeque< BlobSize > &	b1,
		bitdeque< BlobSize > &	b2
	)

friend

Definition at line 452 of file bitdeque.h.

Member Data Documentation

◆ BITS_PER_WORD

template<int BlobSize = 4096 * 8>

constexpr int bitdeque< BlobSize >::BITS_PER_WORD = BlobSize

staticconstexprprivate

Definition at line 27 of file bitdeque.h.

◆ m_deque

template<int BlobSize = 4096 * 8>

deque_type bitdeque< BlobSize >::m_deque

private

Deque of bitsets storing the actual bit data.

Definition at line 174 of file bitdeque.h.

◆ m_pad_begin

template<int BlobSize = 4096 * 8>

int bitdeque< BlobSize >::m_pad_begin

private

Number of unused bits at the front of m_deque.front().

Definition at line 177 of file bitdeque.h.

◆ m_pad_end

template<int BlobSize = 4096 * 8>

int bitdeque< BlobSize >::m_pad_end

private

Number of unused bits at the back of m_deque.back().

Definition at line 180 of file bitdeque.h.

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

src/util/bitdeque.h

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Static Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ const_reverse_iterator

◆ deque_type

◆ difference_type

◆ iterator

◆ pointer

◆ reference

◆ reverse_iterator

◆ size_type

◆ value_type

◆ word_type

Constructor & Destructor Documentation

◆ bitdeque() [1/7]

◆ bitdeque() [2/7]

◆ bitdeque() [3/7]

◆ bitdeque() [4/7]

◆ bitdeque() [5/7]

◆ bitdeque() [6/7]

◆ bitdeque() [7/7]

Member Function Documentation

◆ assign() [1/3]

◆ assign() [2/3]

◆ assign() [3/3]

◆ at() [1/2]

◆ at() [2/2]

◆ back() [1/2]

◆ back() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ cend()

◆ clear()

◆ crbegin()

◆ crend()

◆ emplace()

◆ emplace_back()

◆ emplace_front()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase() [1/4]

◆ erase() [2/4]

◆ erase() [3/4]

◆ erase() [4/4]

◆ erase_back()

◆ erase_front()

◆ extend_back()

◆ extend_front()

◆ front() [1/2]

◆ front() [2/2]

◆ insert() [1/3]

◆ insert() [2/3]

◆ insert() [3/3]

◆ insert_zeroes()

◆ max_size()

◆ operator=() [1/3]

◆ operator=() [2/3]

◆ operator=() [3/3]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ pop_back()

◆ pop_front()

◆ push_back()

◆ push_front()

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ rend() [1/2]

◆ rend() [2/2]