Bitcoin Core  24.99.0
P2P Digital Currency
Classes | Public Types | Public Member Functions | Private Types | Private Member Functions | Private Attributes | Static Private Attributes | Friends | List of all members
bitdeque< BlobSize > Class Template Reference

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. More...
 
void assign (size_type count, bool val)
 Set the container equal to count times the value of val. More...
 
 bitdeque (size_type count, bool val)
 Construct a container containing count times the value of val. More...
 
 bitdeque (size_t count)
 Construct a container containing count false values. More...
 
 bitdeque (const bitdeque &)=default
 Copy constructor. More...
 
 bitdeque (bitdeque &&) noexcept=default
 Move constructor. More...
 
bitdequeoperator= (const bitdeque &other)=default
 Copy assignment operator. More...
 
bitdequeoperator= (bitdeque &&other) noexcept=default
 Move assignment operator. More...
 
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. More...
 
bool empty () const noexcept
 Determine whether the container is empty. More...
 
size_type max_size () const noexcept
 Return the maximum size of the container. More...
 
template<typename It >
void assign (It first, It last)
 Set the container equal to the bits in [first,last). More...
 
void assign (std::initializer_list< bool > ilist)
 Set the container equal to the bits in ilist. More...
 
bitdequeoperator= (std::initializer_list< bool > ilist)
 Set the container equal to the bits in ilist. More...
 
template<typename It >
 bitdeque (It first, It last)
 Construct a container containing the bits in [first,last). More...
 
 bitdeque (std::initializer_list< bool > ilist)
 Construct a container containing the bits in ilist. More...
 
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. More...
 
void clear () noexcept
 Empty the container. More...
 
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. More...
 
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. More...
 
void extend_back (size_type n)
 Extend the container by n bits, adding at the end. More...
 
void erase_front (size_type n)
 Shrink the container by n bits, removing from the beginning. More...
 
void extend_front (size_type n)
 Extend the container by n bits, adding at the beginning. More...
 
void insert_zeroes (size_type before, size_type count)
 Insert a sequence of falses anywhere in the container. More...
 

Private Attributes

deque_type m_deque
 Deque of bitsets storing the actual bit data. More...
 
int m_pad_begin
 Number of unused bits at the front of m_deque.front(). More...
 
int m_pad_end
 Number of unused bits at the back of m_deque.back(). More...
 

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 120 of file bitdeque.h.

◆ const_pointer

template<int BlobSize = 4096 * 8>
using bitdeque< BlobSize >::const_pointer = void

Definition at line 122 of file bitdeque.h.

◆ const_reference

template<int BlobSize = 4096 * 8>
using bitdeque< BlobSize >::const_reference = bool

Definition at line 118 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 124 of file bitdeque.h.

◆ deque_type

template<int BlobSize = 4096 * 8>
using bitdeque< BlobSize >::deque_type = std::deque<word_type>
private

Definition at line 26 of file bitdeque.h.

◆ difference_type

template<int BlobSize = 4096 * 8>
using bitdeque< BlobSize >::difference_type = typename deque_type::difference_type

Definition at line 116 of file bitdeque.h.

◆ iterator

template<int BlobSize = 4096 * 8>
using bitdeque< BlobSize >::iterator = Iterator<false>

Definition at line 119 of file bitdeque.h.

◆ pointer

template<int BlobSize = 4096 * 8>
using bitdeque< BlobSize >::pointer = void

Definition at line 121 of file bitdeque.h.

◆ reference

template<int BlobSize = 4096 * 8>
using bitdeque< BlobSize >::reference = typename word_type::reference

Definition at line 117 of file bitdeque.h.

◆ reverse_iterator

template<int BlobSize = 4096 * 8>
using bitdeque< BlobSize >::reverse_iterator = std::reverse_iterator<iterator>

Definition at line 123 of file bitdeque.h.

◆ size_type

template<int BlobSize = 4096 * 8>
using bitdeque< BlobSize >::size_type = std::size_t

Definition at line 115 of file bitdeque.h.

◆ value_type

template<int BlobSize = 4096 * 8>
using bitdeque< BlobSize >::value_type = bool

Definition at line 114 of file bitdeque.h.

◆ word_type

template<int BlobSize = 4096 * 8>
using bitdeque< BlobSize >::word_type = std::bitset<BlobSize>
private

Definition at line 25 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 213 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 231 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 234 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 313 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 316 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 283 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 216 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 294 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 319 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 324 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 335 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 336 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 251 of file bitdeque.h.

◆ begin() [2/2]

template<int BlobSize = 4096 * 8>
iterator bitdeque< BlobSize >::begin ( )
inlinenoexcept

Definition at line 249 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 252 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 254 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 345 of file bitdeque.h.

◆ crbegin()

template<int BlobSize = 4096 * 8>
const_reverse_iterator bitdeque< BlobSize >::crbegin ( ) const
inlinenoexcept

Definition at line 258 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 260 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 441 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 357 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 371 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 266 of file bitdeque.h.

◆ end() [1/2]

template<int BlobSize = 4096 * 8>
const_iterator bitdeque< BlobSize >::end ( ) const
inlinenoexcept

Definition at line 253 of file bitdeque.h.

◆ end() [2/2]

template<int BlobSize = 4096 * 8>
iterator bitdeque< BlobSize >::end ( )
inlinenoexcept

Definition at line 250 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 411 of file bitdeque.h.

Here is the call graph for this function:

◆ erase() [2/4]

template<int BlobSize = 4096 * 8>
iterator bitdeque< BlobSize >::erase ( const_iterator  pos)
inline

Definition at line 428 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 427 of file bitdeque.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ erase() [4/4]

template<int BlobSize = 4096 * 8>
iterator bitdeque< BlobSize >::erase ( iterator  pos)
inline

Definition at line 429 of file bitdeque.h.

Here is the call graph for this function:
Here is the caller 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 137 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 168 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 156 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 187 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 333 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 334 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 432 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 455 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 443 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 199 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 272 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 305 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 331 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 332 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 380 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 386 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 352 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 366 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 257 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 255 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 259 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 256 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 392 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 339 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 263 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 402 of file bitdeque.h.

Friends And Related Function Documentation

◆ Iterator

template<int BlobSize = 4096 * 8>
template<bool Const>
friend class Iterator
friend

Definition at line 32 of file bitdeque.h.

◆ swap

template<int BlobSize = 4096 * 8>
void swap ( bitdeque< BlobSize > &  b1,
bitdeque< BlobSize > &  b2 
)
friend

Definition at line 408 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 28 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 128 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 131 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 134 of file bitdeque.h.


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