A dynamically growing set of bits with small storage optimization. More...

#include <fe/bitset.h>

Classes
class	reference
	Proxy that Bitset::operator[] hands out to read/write the bit it refers to. More...
class	iterator
	Iterates over the indices of all set bits in ascending order. More...
struct	Hash

Public Member Functions
Access
constexpr bool	test (size_t i) const noexcept
constexpr bool	operator[] (size_t i) const noexcept
constexpr reference	operator[] (size_t i) noexcept
constexpr size_t	next (size_t i) const noexcept
	Index of the first bit that is set at or after `i` - or npos, if there is none.
Modifiers
Bitset::set and Bitset::flip grow the storage as needed; the others never allocate.
constexpr Bitset &	set (size_t i)
constexpr Bitset &	set (size_t i, bool b)
constexpr Bitset &	flip (size_t i)
constexpr Bitset &	clear (size_t i) noexcept
constexpr Bitset &	clear () noexcept
	Clears all bits and releases the heap storage again.
Queries
constexpr size_t	count () const noexcept
constexpr bool	any () const noexcept
constexpr bool	none () const noexcept
constexpr size_t	capacity () const noexcept
	Number of bits available without growing.
constexpr bool	on_heap () const noexcept
	Outgrown the inline storage?
Comparisons
The bits beyond Bitset::capacity are all zero, so a different capacity does not make two Bitsets differ.
constexpr bool	operator== (const Bitset &other) const noexcept
constexpr bool	subset_of (const Bitset &other) const noexcept
	Is every bit set in this also set in `other`?
constexpr bool	intersects (const Bitset &other) const noexcept
	Do this and `other` have at least one bit in common?
Iterators
Yield the index of each set bit in ascending order.
constexpr iterator	begin () const noexcept
constexpr iterator	end () const noexcept
Hash
constexpr size_t	hash () const noexcept

Static Public Attributes
static constexpr size_t	Bits_Per_Word = sizeof(uint64_t) * 8
	Number of bits in one word.
static constexpr size_t	Inline_Bits = Bits_Per_Word
	Number of bits available without allocating.
static constexpr size_t	npos = size_t(-1)
	Returned by Bitset::next if there is no set bit.

Constructors, Destructor, Assignment
constexpr	Bitset () noexcept=default
constexpr	Bitset (std::initializer_list< size_t > bits)
constexpr	Bitset (const Bitset &other)
constexpr	Bitset (Bitset &&other) noexcept
constexpr	~Bitset () noexcept
constexpr Bitset &	operator= (Bitset other) noexcept
constexpr void	swap (Bitset &b1, Bitset &b2) noexcept

Set Operations
Union, intersection, symmetric difference, and difference.
constexpr Bitset &	operator\|= (const Bitset &other)
constexpr Bitset &	operator&= (const Bitset &other) noexcept
constexpr Bitset &	operator^= (const Bitset &other)
constexpr Bitset &	operator-= (const Bitset &other) noexcept
constexpr Bitset	operator\| (Bitset b1, const Bitset &b2)
constexpr Bitset	operator& (Bitset b1, const Bitset &b2)
constexpr Bitset	operator^ (Bitset b1, const Bitset &b2)
constexpr Bitset	operator- (Bitset b1, const Bitset &b2)

Output
void	dump () const
std::ostream &	operator<< (std::ostream &os, const Bitset &bitset)

Detailed Description

A dynamically growing set of bits with small storage optimization.

The first Bitset::Inline_Bits bits live inside the Bitset itself; only beyond that it allocates on the heap. Think of a Bitset as an infinite sequence of bits that are zero except for the ones you set: Bitset::set/Bitset::flip grow the storage on demand, while testing or clearing a bit beyond Bitset::capacity needs no storage at all.

Note: Everything is constexpr as long as the Bitset stays inline: the heap words hide in a uint64_t and are only recovered by a std::bit_cast that a constant evaluation rejects.

Definition at line 28 of file bitset.h.

Constructor & Destructor Documentation

◆ Bitset() [1/4]

fe::Bitset::Bitset ( )

constexprdefaultnoexcept

Referenced by Bitset(), Bitset(), Bitset(), clear(), clear(), flip(), intersects(), operator&, operator&=(), fe::Bitset::Hash::operator()(), operator-, operator-=(), operator<<, operator=(), operator==(), operator^, operator^=(), operator|, operator|=(), set(), set(), subset_of(), and swap.

◆ Bitset() [2/4]

fe::Bitset::Bitset ( std::initializer_list< size_t > bits )

inlineconstexpr

Definition at line 99 of file bitset.h.

References Bitset(), and set().

◆ Bitset() [3/4]

fe::Bitset::Bitset ( const Bitset & other )

inlineconstexpr

Definition at line 103 of file bitset.h.

References Bitset(), and on_heap().

◆ Bitset() [4/4]

fe::Bitset::Bitset ( Bitset && other )

inlineconstexprnoexcept

Definition at line 113 of file bitset.h.

References Bitset(), and swap.

◆ ~Bitset()

fe::Bitset::~Bitset ( )

inlineconstexprnoexcept

Definition at line 114 of file bitset.h.

References on_heap().

Member Function Documentation

◆ any()

bool fe::Bitset::any ( ) const

inlinenodiscardconstexprnoexcept

Definition at line 185 of file bitset.h.

◆ begin()

iterator fe::Bitset::begin ( ) const

inlinenodiscardconstexprnoexcept

Definition at line 259 of file bitset.h.

References next().

◆ capacity()

size_t fe::Bitset::capacity ( ) const

inlinenodiscardconstexprnoexcept

Number of bits available without growing.

Definition at line 188 of file bitset.h.

References Bits_Per_Word.

◆ clear() [1/2]

Bitset & fe::Bitset::clear ( )

inlineconstexprnoexcept

Clears all bits and releases the heap storage again.

Definition at line 169 of file bitset.h.

References Bitset(), and on_heap().

◆ clear() [2/2]

Bitset & fe::Bitset::clear ( size_t i )

inlineconstexprnoexcept

Definition at line 164 of file bitset.h.

References Bits_Per_Word, and Bitset().

Referenced by set().

◆ count()

size_t fe::Bitset::count ( ) const

inlinenodiscardconstexprnoexcept

Definition at line 179 of file bitset.h.

◆ dump()

void fe::Bitset::dump ( ) const

inline

Definition at line 289 of file bitset.h.

◆ end()

iterator fe::Bitset::end ( ) const

inlinenodiscardconstexprnoexcept

Definition at line 260 of file bitset.h.

◆ flip()

Bitset & fe::Bitset::flip ( size_t i )

inlineconstexpr

Definition at line 159 of file bitset.h.

References Bits_Per_Word, and Bitset().

◆ hash()

size_t fe::Bitset::hash ( ) const

inlinenodiscardconstexprnoexcept

Definition at line 265 of file bitset.h.

References fe::hash_begin(), and fe::hash_combine().

◆ intersects()

bool fe::Bitset::intersects ( const Bitset & other ) const

inlinenodiscardconstexprnoexcept

Do this and other have at least one bit in common?

Definition at line 249 of file bitset.h.

References Bitset().

◆ next()

size_t fe::Bitset::next ( size_t i ) const

inlinenodiscardconstexprnoexcept

Index of the first bit that is set at or after i - or npos, if there is none.

Definition at line 138 of file bitset.h.

References Bits_Per_Word, and npos.

Referenced by begin().

◆ none()

bool fe::Bitset::none ( ) const

inlinenodiscardconstexprnoexcept

Definition at line 186 of file bitset.h.

◆ on_heap()

bool fe::Bitset::on_heap ( ) const

inlinenodiscardconstexprnoexcept

Outgrown the inline storage?

Definition at line 190 of file bitset.h.

Referenced by Bitset(), clear(), and ~Bitset().

◆ operator&=()

Bitset & fe::Bitset::operator&= ( const Bitset & other )

inlineconstexprnoexcept

Definition at line 203 of file bitset.h.

References Bitset().

◆ operator-=()

Bitset & fe::Bitset::operator-= ( const Bitset & other )

inlineconstexprnoexcept

Definition at line 218 of file bitset.h.

References Bitset().

◆ operator=()

Bitset & fe::Bitset::operator= ( Bitset other )

inlineconstexprnoexcept

Definition at line 117 of file bitset.h.

References Bitset(), and swap.

◆ operator==()

bool fe::Bitset::operator== ( const Bitset & other ) const

inlinenodiscardconstexprnoexcept

Definition at line 233 of file bitset.h.

References Bitset().

◆ operator[]() [1/2]

bool fe::Bitset::operator[] ( size_t i ) const

inlinenodiscardconstexprnoexcept

Definition at line 134 of file bitset.h.

References test().

◆ operator[]() [2/2]

reference fe::Bitset::operator[] ( size_t i )

inlinenodiscardconstexprnoexcept

Definition at line 135 of file bitset.h.

◆ operator^=()

Bitset & fe::Bitset::operator^= ( const Bitset & other )

inlineconstexpr

Definition at line 211 of file bitset.h.

References Bitset().

◆ operator|=()

Bitset & fe::Bitset::operator|= ( const Bitset & other )

inlineconstexpr

Definition at line 196 of file bitset.h.

References Bitset().

◆ set() [1/2]

Bitset & fe::Bitset::set ( size_t i )

inlineconstexpr

Definition at line 153 of file bitset.h.

References Bits_Per_Word, and Bitset().

Referenced by Bitset().

◆ set() [2/2]

Bitset & fe::Bitset::set	(	size_t	i,
		bool	b )

inlineconstexpr

Definition at line 158 of file bitset.h.

References Bitset(), clear(), and set().

Referenced by set().

◆ subset_of()

bool fe::Bitset::subset_of ( const Bitset & other ) const

inlinenodiscardconstexprnoexcept

Is every bit set in this also set in other?

Definition at line 241 of file bitset.h.

References Bitset().

◆ test()

bool fe::Bitset::test ( size_t i ) const

inlinenodiscardconstexprnoexcept

Definition at line 130 of file bitset.h.

References Bits_Per_Word.

Referenced by operator[]().

◆ operator&

Bitset operator&	(	Bitset	b1,
		const Bitset &	b2 )

friend

Definition at line 225 of file bitset.h.

References Bitset().

◆ operator-

Bitset operator-	(	Bitset	b1,
		const Bitset &	b2 )

friend

Definition at line 227 of file bitset.h.

References Bitset().

◆ operator<<

std::ostream & operator<<	(	std::ostream &	os,
		const Bitset &	bitset )

friend

Definition at line 291 of file bitset.h.

References Bitset().

◆ operator^

Bitset operator^	(	Bitset	b1,
		const Bitset &	b2 )

friend

Definition at line 226 of file bitset.h.

References Bitset().

◆ operator|

Bitset operator\|	(	Bitset	b1,
		const Bitset &	b2 )

friend

Definition at line 224 of file bitset.h.

References Bitset().

◆ swap

void swap	(	Bitset &	b1,
		Bitset &	b2 )

friend

Definition at line 121 of file bitset.h.

References Bitset(), and swap.

Referenced by Bitset(), operator=(), and swap.

Member Data Documentation

◆ Bits_Per_Word

size_t fe::Bitset::Bits_Per_Word = sizeof(uint64_t) * 8

staticconstexpr

Number of bits in one word.

Definition at line 30 of file bitset.h.

Referenced by capacity(), clear(), flip(), next(), set(), and test().

◆ Inline_Bits

size_t fe::Bitset::Inline_Bits = Bits_Per_Word

staticconstexpr

Number of bits available without allocating.

Definition at line 31 of file bitset.h.

◆ npos

size_t fe::Bitset::npos = size_t(-1)

staticconstexpr

Returned by Bitset::next if there is no set bit.

Definition at line 32 of file bitset.h.

Referenced by next(), and fe::Bitset::iterator::operator++().

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

fe/bitset.h

Classes

Public Member Functions

Static Public Attributes

Constructors, Destructor, Assignment

Set Operations

Output

Detailed Description

Constructor & Destructor Documentation

◆ Bitset() [1/4]

◆ Bitset() [2/4]

◆ Bitset() [3/4]

◆ Bitset() [4/4]

◆ ~Bitset()

Member Function Documentation

◆ any()

◆ begin()

◆ capacity()

◆ clear() [1/2]

◆ clear() [2/2]

◆ count()

◆ dump()

◆ end()

◆ flip()

◆ hash()

◆ intersects()

◆ next()

◆ none()

◆ on_heap()

◆ operator&=()

◆ operator-=()

◆ operator=()

◆ operator==()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ operator^=()

◆ operator|=()

◆ set() [1/2]

◆ set() [2/2]

◆ subset_of()

◆ test()

Friends And Related Symbol Documentation

◆ operator&

◆ operator-

◆ operator<<

◆ operator^

◆ operator|

◆ swap

Member Data Documentation

◆ Bits_Per_Word

◆ Inline_Bits

◆ npos