A dynamic size sequence of bits with efficient storage and manipulation operations. More...

#include <dynamic_bitset.hpp>

Inheritance diagram for sparrow::dynamic_bitset< T >:

Collaboration diagram for sparrow::dynamic_bitset< T >:

Public Types
using	base_type = dynamic_bitset_base<buffer<T>>
	Base class type.

using	storage_type = typename base_type::storage_type
	Underlying storage container type.

using	default_allocator = typename storage_type::default_allocator
	Type of default allocator.

using	block_type = typename base_type::block_type
	Type of each storage block (same as T)

using	value_type = typename base_type::value_type
	Type of individual bit values (bool)

using	size_type = typename base_type::size_type
	Type used for sizes and indices.

Public Types inherited from sparrow::dynamic_bitset_base< buffer< T > >
using	self_type
	This class type.

using	storage_type
	Underlying storage container type.

using	storage_type_without_cvrefpointer
	Storage type without CV/ref/pointer qualifiers.

using	block_type
	Type of each storage block (integral type)

using	value_type
	Type of individual bit values.

using	reference
	Mutable reference to a bit.

using	const_reference
	Immutable reference to a bit (plain bool)

using	size_type
	Type for sizes and indices.

using	difference_type
	Type for iterator differences.

using	iterator
	Mutable iterator type.

using	const_iterator
	Immutable iterator type.

using	self_type
	This class type.

using	storage_type
	Underlying storage container type.

using	storage_type_without_cvrefpointer
	Storage type without CV/ref/pointer qualifiers.

using	block_type
	Type of each storage block (integral type)

using	value_type
	Type of individual bit values.

using	reference
	Mutable reference to a bit.

using	const_reference
	Immutable reference to a bit (plain bool)

using	size_type
	Type for sizes and indices.

using	difference_type
	Type for iterator differences.

using	iterator
	Mutable iterator type.

using	const_iterator
	Immutable iterator type.

Public Member Functions
template<std::ranges::input_range R, allocator A = default_allocator> requires std::convertible_to<std::ranges::range_value_t<R>, value_type>
constexpr	dynamic_bitset (const R &r, const A &a=A())
	Constructs a dynamic_bitset from an input range of convertible values.

template<class A = default_allocator> requires (not std::same_as<A, dynamic_bitset<T>> and allocator<A>)
constexpr	dynamic_bitset (const A &a=A())
	Default constructor.

template<allocator A = default_allocator>
constexpr	dynamic_bitset (size_type n, const A &a=A())
	Constructs a bitset with n bits, all initialized to false.

template<allocator A = default_allocator>
constexpr	dynamic_bitset (size_type n, value_type v, const A &a=A())
	Constructs a bitset with n bits, all initialized to the specified value.

template<allocator A = default_allocator>
constexpr	dynamic_bitset (block_type *p, size_type n, const A &a=A())
	Constructs a bitset using existing memory.

template<allocator A = default_allocator>
constexpr	dynamic_bitset (block_type *p, size_type n, size_type null_count, const A &a=A())
	Constructs a bitset using existing memory with null count tracking.

constexpr	~dynamic_bitset ()=default

constexpr	dynamic_bitset (const dynamic_bitset &)=default

constexpr	dynamic_bitset (dynamic_bitset &&) noexcept=default

template<allocator A>
constexpr	dynamic_bitset (const dynamic_bitset &rhs, const A &a)

template<allocator A>
constexpr	dynamic_bitset (dynamic_bitset &&rhs, const A &a)

constexpr dynamic_bitset &	operator= (const dynamic_bitset &)=default

constexpr dynamic_bitset &	operator= (dynamic_bitset &&) noexcept=default

constexpr void	clear () noexcept
	Removes all bits from the bitset.

constexpr iterator	emplace (const_iterator pos, value_type value)
	< Remove all bits from the bitset

constexpr iterator	erase (const_iterator pos)
	< Emplace a bit at a specific position

constexpr iterator	erase (const_iterator first, const_iterator last)
	< Emplace a bit at a specific position

constexpr iterator	insert (const_iterator pos, value_type value)
	< Remove bits from the bitset

constexpr iterator	insert (const_iterator pos, size_type count, value_type value)
	< Remove bits from the bitset

constexpr iterator	insert (const_iterator pos, InputIt first, InputIt last)
	< Remove bits from the bitset

constexpr iterator	insert (const_iterator pos, std::initializer_list< value_type > ilist)
	< Remove bits from the bitset

constexpr void	pop_back ()
	< Insert bits into the bitset

constexpr void	push_back (value_type value)
	< Remove the last bit

constexpr void	resize (size_type n, value_type b=false)
	< Add a bit to the end

Public Member Functions inherited from sparrow::dynamic_bitset_base< buffer< T > >
constexpr size_type	size () const noexcept
	Returns the number of bits in the bitset.

constexpr bool	empty () const noexcept
	Checks if the bitset contains no bits.

constexpr size_type	null_count () const noexcept
	Returns the number of bits set to false (null/invalid).

constexpr bool	test (size_type pos) const
	Tests the value of a bit at the specified position.

constexpr void	set (size_type pos, value_type value)
	Sets the value of a bit at the specified position.

constexpr const_reference	at (size_type pos) const
	Accesses a bit with bounds checking.

constexpr reference	at (size_type pos)
	Accesses a bit with bounds checking.

constexpr reference	operator[] (size_type i)
	Accesses a bit without bounds checking.

constexpr const_reference	operator[] (size_type i) const
	Accesses a bit without bounds checking.

constexpr block_type *	data () noexcept
	Returns a pointer to the underlying block storage.

constexpr const block_type *	data () const noexcept
	Returns a pointer to the underlying block storage.

constexpr size_type	block_count () const noexcept
	Returns the number of storage blocks.

constexpr void	swap (self_type &rhs) noexcept
	Swaps the contents with another bitset.

constexpr iterator	begin ()
	Returns a mutable iterator to the first bit.

constexpr iterator	end ()
	Returns a mutable iterator past the last bit.

constexpr const_iterator	begin () const
	Returns an immutable iterator to the first bit.

constexpr const_iterator	end () const
	Returns an immutable iterator past the last bit.

constexpr const_iterator	cbegin () const
	Returns an immutable iterator to the first bit.

constexpr const_iterator	cend () const
	Returns an immutable iterator past the last bit.

constexpr reference	front ()
	Accesses the first bit.

constexpr const_reference	front () const
	Accesses the first bit.

constexpr reference	back ()
	Accesses the last bit.

constexpr const_reference	back () const
	Accesses the last bit.

constexpr const storage_type_without_cvrefpointer &	buffer () const noexcept
	Returns an immutable reference to the underlying buffer.

constexpr storage_type_without_cvrefpointer &	buffer () noexcept
	Returns a mutable reference to the underlying buffer.

storage_type	extract_storage () noexcept
	Extracts the underlying storage (move operation).

constexpr size_type	size () const noexcept
	Returns the number of bits in the bitset.

constexpr bool	empty () const noexcept
	Checks if the bitset contains no bits.

constexpr size_type	null_count () const noexcept
	Returns the number of bits set to false (null/invalid).

constexpr bool	test (size_type pos) const
	Tests the value of a bit at the specified position.

constexpr void	set (size_type pos, value_type value)
	Sets the value of a bit at the specified position.

constexpr const_reference	at (size_type pos) const
	Accesses a bit with bounds checking.

constexpr reference	at (size_type pos)
	Accesses a bit with bounds checking.

constexpr reference	operator[] (size_type i)
	Accesses a bit without bounds checking.

constexpr const_reference	operator[] (size_type i) const
	Accesses a bit without bounds checking.

constexpr block_type *	data () noexcept
	Returns a pointer to the underlying block storage.

constexpr const block_type *	data () const noexcept
	Returns a pointer to the underlying block storage.

constexpr size_type	block_count () const noexcept
	Returns the number of storage blocks.

constexpr void	swap (self_type &rhs) noexcept
	Swaps the contents with another bitset.

constexpr iterator	begin ()
	Returns a mutable iterator to the first bit.

constexpr const_iterator	begin () const
	Returns an immutable iterator to the first bit.

constexpr iterator	end ()
	Returns a mutable iterator past the last bit.

constexpr const_iterator	end () const
	Returns an immutable iterator past the last bit.

constexpr const_iterator	cbegin () const
	Returns an immutable iterator to the first bit.

constexpr const_iterator	cend () const
	Returns an immutable iterator past the last bit.

constexpr reference	front ()
	Accesses the first bit.

constexpr const_reference	front () const
	Accesses the first bit.

constexpr reference	back ()
	Accesses the last bit.

constexpr const_reference	back () const
	Accesses the last bit.

constexpr const storage_type_without_cvrefpointer &	buffer () const noexcept
	Returns an immutable reference to the underlying buffer.

constexpr storage_type_without_cvrefpointer &	buffer () noexcept
	Returns a mutable reference to the underlying buffer.

storage_type	extract_storage () noexcept
	Extracts the underlying storage (move operation).

Additional Inherited Members
Static Public Member Functions inherited from sparrow::dynamic_bitset_base< buffer< T > >
static constexpr size_type	compute_block_count (size_type bits_count) noexcept
	Computes the number of blocks needed to store the specified number of bits.

static constexpr size_type	compute_block_count (size_type bits_count) noexcept
	Computes the number of blocks needed to store the specified number of bits.

Protected Member Functions inherited from sparrow::dynamic_bitset_base< buffer< T > >
constexpr	dynamic_bitset_base (storage_type buffer, size_type size)
	Constructs a bitset with the given storage and size.

constexpr	dynamic_bitset_base (storage_type buffer, size_type size, size_type null_count)
	Constructs a bitset with the given storage, size, and null count.

constexpr	~dynamic_bitset_base ()=default

constexpr	dynamic_bitset_base (const dynamic_bitset_base &)=default

constexpr	dynamic_bitset_base (dynamic_bitset_base &&) noexcept=default

constexpr dynamic_bitset_base &	operator= (const dynamic_bitset_base &)=default

constexpr dynamic_bitset_base &	operator= (dynamic_bitset_base &&) noexcept=default

constexpr void	resize (size_type n, value_type b=false)
	Resizes the bitset to contain n bits.

constexpr void	clear () noexcept
	Removes all bits from the bitset.

constexpr iterator	insert (const_iterator pos, value_type value)
	Inserts a single bit at the specified position.

constexpr iterator	insert (const_iterator pos, size_type count, value_type value)
	Inserts multiple bits with the same value at the specified position.

constexpr iterator	insert (const_iterator pos, InputIt first, InputIt last)
	Inserts bits from an iterator range at the specified position.

constexpr iterator	insert (const_iterator pos, std::initializer_list< value_type > ilist)
	Inserts bits from an initializer list at the specified position.

constexpr iterator	emplace (const_iterator pos, value_type value)
	Constructs a bit in-place at the specified position.

constexpr iterator	erase (const_iterator pos)
	Removes a single bit at the specified position.

constexpr iterator	erase (const_iterator first, const_iterator last)
	Removes bits in the specified range.

constexpr void	push_back (value_type value)
	Adds a bit to the end of the bitset.

constexpr void	pop_back ()
	Removes the last bit from the bitset.

constexpr void	zero_unused_bits ()
	Clears any unused bits in the last storage block.

size_type	count_non_null () const noexcept
	Counts the number of bits set to true.

constexpr	dynamic_bitset_base (storage_type buffer, size_type size)
	Constructs a bitset with the given storage and size.

constexpr	dynamic_bitset_base (storage_type buffer, size_type size, size_type null_count)
	Constructs a bitset with the given storage, size, and null count.

constexpr	dynamic_bitset_base (const dynamic_bitset_base &)=default

constexpr	dynamic_bitset_base (dynamic_bitset_base &&) noexcept=default

constexpr	~dynamic_bitset_base ()=default

constexpr dynamic_bitset_base &	operator= (const dynamic_bitset_base &)=default

constexpr dynamic_bitset_base &	operator= (dynamic_bitset_base &&) noexcept=default

constexpr void	resize (size_type n, value_type b=false)
	Resizes the bitset to contain n bits.

constexpr void	clear () noexcept
	Removes all bits from the bitset.

constexpr iterator	insert (const_iterator pos, value_type value)
	Inserts a single bit at the specified position.

constexpr iterator	insert (const_iterator pos, size_type count, value_type value)
	Inserts multiple bits with the same value at the specified position.

constexpr iterator	insert (const_iterator pos, InputIt first, InputIt last)
	Inserts bits from an iterator range at the specified position.

constexpr iterator	insert (const_iterator pos, std::initializer_list< value_type > ilist)
	Inserts bits from an initializer list at the specified position.

constexpr iterator	emplace (const_iterator pos, value_type value)
	Constructs a bit in-place at the specified position.

constexpr iterator	erase (const_iterator pos)
	Removes a single bit at the specified position.

constexpr iterator	erase (const_iterator first, const_iterator last)
	Removes bits in the specified range.

constexpr void	push_back (value_type value)
	Adds a bit to the end of the bitset.

constexpr void	pop_back ()
	Removes the last bit from the bitset.

constexpr void	zero_unused_bits ()
	Clears any unused bits in the last storage block.

size_type	count_non_null () const noexcept
	Counts the number of bits set to true.

Detailed Description

template<std::integral T>
class sparrow::dynamic_bitset< T >

A dynamic size sequence of bits with efficient storage and manipulation operations.

This class provides a container for storing and manipulating sequences of boolean values using an underlying integer type for efficient bit-level operations. The bitset can grow and shrink dynamically, similar to std::vector, while providing specialized bit manipulation methods.

Template Parameters

T	The integer type used to store the bits. Must satisfy std::integral. Common choices are std::uint8_t, std::uint32_t, or std::uint64_t.

Note: The class inherits from dynamic_bitset_base which provides the core bit manipulation functionality. This class adds constructors and manages the underlying buffer storage.

Example usage:

//Create a bitset with 10 bits, all set to false
dynamic_bitset<std::uint8_t> bits(10);
 
//Create from a range of boolean values
std::vector<bool> values = {true, false, true, false};
dynamic_bitset<std::uint8_t> bits_from_range(values);
 
//Set and test individual bits
bits.set(5, true);
bool bit_value = bits.test(5);

Definition at line 56 of file dynamic_bitset.hpp.

Member Typedef Documentation

◆ base_type

template<std::integral T>

using sparrow::dynamic_bitset< T >::base_type = dynamic_bitset_base<buffer<T>>

Base class type.

Definition at line 60 of file dynamic_bitset.hpp.

◆ block_type

template<std::integral T>

using sparrow::dynamic_bitset< T >::block_type = typename base_type::block_type

Type of each storage block (same as T)

Definition at line 63 of file dynamic_bitset.hpp.

◆ default_allocator

template<std::integral T>

using sparrow::dynamic_bitset< T >::default_allocator = typename storage_type::default_allocator

Type of default allocator.

Definition at line 62 of file dynamic_bitset.hpp.

◆ size_type

template<std::integral T>

using sparrow::dynamic_bitset< T >::size_type = typename base_type::size_type

Type used for sizes and indices.

Definition at line 65 of file dynamic_bitset.hpp.

◆ storage_type

template<std::integral T>

using sparrow::dynamic_bitset< T >::storage_type = typename base_type::storage_type

Underlying storage container type.

Definition at line 61 of file dynamic_bitset.hpp.

◆ value_type

template<std::integral T>

using sparrow::dynamic_bitset< T >::value_type = typename base_type::value_type

Type of individual bit values (bool)

Definition at line 64 of file dynamic_bitset.hpp.

Constructor & Destructor Documentation

◆ dynamic_bitset() [1/10]

template<std::integral T>

template<std::ranges::input_range R, allocator A = default_allocator>
requires std::convertible_to<std::ranges::range_value_t<R>, value_type>

sparrow::dynamic_bitset< T >::dynamic_bitset	(	const R &	r,
		const A &	a = A() )

inlineexplicitconstexpr

Constructs a dynamic_bitset from an input range of convertible values.

Creates a bitset with the same size as the input range, where each bit is set according to the truthiness of the corresponding range element. Non-zero/true values result in set bits (1), while zero/false values result in unset bits (0).

Template Parameters

R	Input range type that must satisfy std::ranges::input_range
A	Allocator type that must satisfy sparrow::allocator

Parameters

r	The input range whose elements will be converted to bits
a	The allocator used internally

Precondition: The range elements must be convertible to value_type (bool); The range must have a computable size via std::ranges::size

Example:

std::vector<int> values = {1, 0, 3, 0, 5}; // non-zero = true, zero = false

dynamic_bitset<std::uint8_t> bits(values); // Results in: 10101

Definition at line 90 of file dynamic_bitset.hpp.

Here is the caller graph for this function:

◆ dynamic_bitset() [2/10]

template<std::integral T>
requires (not std::same_as<A, dynamic_bitset<T>> and allocator<A>)

template<class A>
requires (not std::same_as<A, dynamic_bitset<T>> and allocator<A>)

sparrow::dynamic_bitset< T >::dynamic_bitset ( const A & a = A() )

constexpr

Default constructor.

Creates an empty bitset.

Constructs a bitset with zero bits. The bitset can later be resized or bits can be added using the provided methods.

Definition at line 199 of file dynamic_bitset.hpp.

Here is the call graph for this function:

◆ dynamic_bitset() [3/10]

template<std::integral T>

template<allocator A>

sparrow::dynamic_bitset< T >::dynamic_bitset	(	size_type	n,
		const A &	a = A() )

explicitconstexpr

Constructs a bitset with n bits, all initialized to false.

Parameters

n	The number of bits in the bitset

Postcondition: size() == n; All bits are set to false

Definition at line 207 of file dynamic_bitset.hpp.

Here is the call graph for this function:

◆ dynamic_bitset() [4/10]

template<std::integral T>

template<allocator A>

sparrow::dynamic_bitset< T >::dynamic_bitset	(	size_type	n,
		value_type	v,
		const A &	a = A() )

constexpr

Constructs a bitset with n bits, all initialized to the specified value.

Parameters

n	The number of bits in the bitset
v	The value to initialize all bits to (true or false)

Postcondition: size() == n; All bits are set to v

Definition at line 215 of file dynamic_bitset.hpp.

Here is the call graph for this function:

◆ dynamic_bitset() [5/10]

template<std::integral T>

template<allocator A>

sparrow::dynamic_bitset< T >::dynamic_bitset	(	block_type *	p,
		size_type	n,
		const A &	a = A() )

constexpr

Constructs a bitset using existing memory.

Creates a bitset that uses the provided memory buffer for storage. The bitset takes ownership of the memory.

Parameters

p	Pointer to the memory buffer containing bit data
n	The number of bits represented in the buffer

Precondition: If p is not nullptr, it must point to valid memory of sufficient size

Postcondition: size() == n

Warning: The caller must ensure the memory pointed to by p remains valid and contains properly formatted bit data.

Definition at line 227 of file dynamic_bitset.hpp.

Here is the call graph for this function:

◆ dynamic_bitset() [6/10]

template<std::integral T>

template<allocator A>

sparrow::dynamic_bitset< T >::dynamic_bitset	(	block_type *	p,
		size_type	n,
		size_type	null_count,
		const A &	a = A() )

constexpr

Constructs a bitset using existing memory with null count tracking.

Creates a bitset that uses the provided memory buffer and tracks the number of null (unset) bits for optimization purposes.

Parameters

p	Pointer to the memory buffer containing bit data
n	The number of bits represented in the buffer
null_count	The number of bits that are set to false/null

Precondition: If p is not nullptr, it must point to valid memory of sufficient size; null_count must accurately reflect the number of unset bits

Postcondition: size() == n; null_count() == null_count

Definition at line 235 of file dynamic_bitset.hpp.

Here is the call graph for this function:

◆ ~dynamic_bitset()

template<std::integral T>

sparrow::dynamic_bitset< T >::~dynamic_bitset ( )

constexprdefault

◆ dynamic_bitset() [7/10]

template<std::integral T>

sparrow::dynamic_bitset< T >::dynamic_bitset ( const dynamic_bitset< T > & )

constexprdefault

◆ dynamic_bitset() [8/10]

template<std::integral T>

sparrow::dynamic_bitset< T >::dynamic_bitset ( dynamic_bitset< T > && )

constexprdefaultnoexcept

◆ dynamic_bitset() [9/10]

template<std::integral T>

template<allocator A>

sparrow::dynamic_bitset< T >::dynamic_bitset	(	const dynamic_bitset< T > &	rhs,
		const A &	a )

constexpr

Definition at line 244 of file dynamic_bitset.hpp.

Here is the call graph for this function:

◆ dynamic_bitset() [10/10]

template<std::integral T>

template<allocator A>

sparrow::dynamic_bitset< T >::dynamic_bitset	(	dynamic_bitset< T > &&	rhs,
		const A &	a )

constexpr

Definition at line 251 of file dynamic_bitset.hpp.

Here is the call graph for this function:

Member Function Documentation

◆ clear()

template<std::integral T>

void sparrow::dynamic_bitset_base< buffer< T > >::clear ( )

constexprnoexcept

Removes all bits from the bitset.

Postcondition: size() == 0; empty() == true; null_count() == 0

◆ emplace()

template<std::integral T>

iterator sparrow::dynamic_bitset_base< buffer< T > >::emplace	(	const_iterator	pos,
		value_type	value )

constexpr

< Remove all bits from the bitset

◆ erase() [1/2]

template<std::integral T>

iterator sparrow::dynamic_bitset_base< buffer< T > >::erase	(	const_iterator	first,
		const_iterator	last )

constexpr

< Emplace a bit at a specific position

◆ erase() [2/2]

template<std::integral T>

iterator sparrow::dynamic_bitset_base< buffer< T > >::erase ( const_iterator pos )

constexpr

< Emplace a bit at a specific position

◆ insert() [1/4]

template<std::integral T>

iterator sparrow::dynamic_bitset_base< buffer< T > >::insert	(	const_iterator	pos,
		InputIt	first,
		InputIt	last )

constexpr

< Remove bits from the bitset

◆ insert() [2/4]

template<std::integral T>

iterator sparrow::dynamic_bitset_base< buffer< T > >::insert	(	const_iterator	pos,
		size_type	count,
		value_type	value )

constexpr

< Remove bits from the bitset

◆ insert() [3/4]

template<std::integral T>

iterator sparrow::dynamic_bitset_base< buffer< T > >::insert	(	const_iterator	pos,
		std::initializer_list< value_type >	ilist )

constexpr

< Remove bits from the bitset

◆ insert() [4/4]

template<std::integral T>

iterator sparrow::dynamic_bitset_base< buffer< T > >::insert	(	const_iterator	pos,
		value_type	value )

constexpr

< Remove bits from the bitset

◆ operator=() [1/2]

template<std::integral T>

dynamic_bitset & sparrow::dynamic_bitset< T >::operator= ( const dynamic_bitset< T > & )

constexprdefault

◆ operator=() [2/2]

template<std::integral T>

dynamic_bitset & sparrow::dynamic_bitset< T >::operator= ( dynamic_bitset< T > && )

constexprdefaultnoexcept

◆ pop_back()

template<std::integral T>

void sparrow::dynamic_bitset_base< buffer< T > >::pop_back ( )

constexpr

< Insert bits into the bitset

◆ push_back()

template<std::integral T>

void sparrow::dynamic_bitset_base< buffer< T > >::push_back ( value_type value )

constexpr

< Remove the last bit

◆ resize()

template<std::integral T>

void sparrow::dynamic_bitset_base< buffer< T > >::resize	(	size_type	n,
		value_type	b = false )

constexpr

< Add a bit to the end

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

/home/runner/work/sparrow/sparrow/include/sparrow/buffer/dynamic_bitset/dynamic_bitset.hpp

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ base_type

◆ block_type

◆ default_allocator

◆ size_type

◆ storage_type

◆ value_type

Constructor & Destructor Documentation

◆ dynamic_bitset() [1/10]

◆ dynamic_bitset() [2/10]

◆ dynamic_bitset() [3/10]

◆ dynamic_bitset() [4/10]

◆ dynamic_bitset() [5/10]

◆ dynamic_bitset() [6/10]

◆ ~dynamic_bitset()

◆ dynamic_bitset() [7/10]

◆ dynamic_bitset() [8/10]

◆ dynamic_bitset() [9/10]

◆ dynamic_bitset() [10/10]

Member Function Documentation

◆ clear()

◆ emplace()

◆ erase() [1/2]

◆ erase() [2/2]

◆ insert() [1/4]

◆ insert() [2/4]

◆ insert() [3/4]

◆ insert() [4/4]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ pop_back()

◆ push_back()

◆ resize()