A vector of bits. More...

#include <bitvector.h>

Classes
class	reference
	An lvalue proxy for single bits. More...

Public Types
typedef size_t	block_type

typedef size_t	size_type

typedef bool	const_reference
	Unlike the reference type, a const_reference does not need lvalue semantics and can thus represent simply a boolean (bit) value. More...

Public Member Functions
	bitvector ()
	Constructs an empty bit vector.

	bitvector (size_type size, bool value=false)
	Constructs a bit vector of a given size. More...

template<typename InputIterator >
	bitvector (InputIterator first, InputIterator last)
	Constructs a bit vector from a sequence of blocks.

	bitvector (bitvector const &other)
	Copy-constructs a bit vector. More...

	bitvector (bitvector &&other)
	Move-constructs a bit vector. More...

bitvector &	operator= (bitvector other)
	Assigns another bit vector to this instance. More...

bitvector	operator~ () const

bitvector	operator<< (size_type n) const

bitvector	operator>> (size_type n) const

bitvector &	operator<<= (size_type n)

bitvector &	operator>>= (size_type n)

bitvector &	operator&= (bitvector const &other)

bitvector &	operator\|= (bitvector const &other)

bitvector &	operator^= (bitvector const &other)

bitvector &	operator-= (bitvector const &other)

template<typename Iterator , typename std::enable_if< std::is_same< typename std::iterator_traits< Iterator >::iterator_category, std::forward_iterator_tag >::value >::type = 0>
void	append (Iterator first, Iterator last)
	Appends the bits in a sequence of values. More...

void	append (block_type block)
	Appends the bits in a given block. More...

void	push_back (bool bit)
	Appends a single bit to the end of the bit vector. More...

void	clear () noexcept
	Clears all bits in the bitvector.

void	resize (size_type n, bool value=false)
	Resizes the bit vector to a new number of bits. More...

bitvector &	set (size_type i, bool bit=true)
	Sets a bit at a specific position to a given value. More...

bitvector &	set ()
	Sets all bits to 1. More...

bitvector &	reset (size_type i)
	Resets a bit at a specific position, i.e., sets it to 0. More...

bitvector &	reset ()
	Sets all bits to 0. More...

bitvector &	flip (size_type i)
	Toggles/flips a bit at a specific position. More...

bitvector &	flip ()
	Computes the complement. More...

reference	operator[] (size_type i)
	Retrieves a single bit. More...

const_reference	operator[] (size_type i) const
	Retrieves a single bit. More...

size_type	count () const
	Counts the number of 1-bits in the bit vector. More...

size_type	blocks () const
	Retrieves the number of blocks of the underlying storage. More...

size_type	size () const
	Retrieves the number of bits the bitvector consist of. More...

bool	empty () const
	Checks whether the bit vector is empty. More...

size_type	find_first () const
	Finds the bit position of of the first 1-bit. More...

size_type	find_next (size_type i) const
	Finds the next 1-bit from a given starting position. More...

Static Public Attributes
static size_type constexpr	npos = static_cast<size_type>(-1)

static block_type constexpr	bits_per_block

Private Member Functions
block_type	extra_bits () const
	Computes the number of excess/unused bits in the bit vector.

void	zero_unused_bits ()

size_type	find_from (size_type i) const
	Looks for the first 1-bit starting at a given position. More...

Static Private Member Functions
static size_type constexpr	block_index (size_type i)
	Computes the block index for a given bit position.

static block_type constexpr	bit_index (size_type i)
	Computes the bit index within a given block for a given bit position.

static block_type constexpr	bit_mask (size_type i)
	Computes the bitmask block to extract a bit a given bit position.

static size_type constexpr	bits_to_blocks (size_type bits)
	Computes the number of blocks needed to represent a given number of bits. More...

static size_type	lowest_bit (block_type block)
	Computes the bit position first 1-bit in a given block. More...

Private Attributes
std::vector< block_type >	bits_

size_type	num_bits_

Friends
std::string	to_string (bitvector const &, bool, size_t)

void	swap (bitvector x, bitvector y)
	Swaps two bit vectors.

bitvector	operator& (bitvector const &x, bitvector const &y)

bitvector	operator\| (bitvector const &x, bitvector const &y)

bitvector	operator^ (bitvector const &x, bitvector const &y)

bitvector	operator- (bitvector const &x, bitvector const &y)

bool	operator== (bitvector const &x, bitvector const &y)

bool	operator!= (bitvector const &x, bitvector const &y)

bool	operator< (bitvector const &x, bitvector const &y)

Detailed Description

A vector of bits.

Definition at line 12 of file bitvector.h.

Member Typedef Documentation

typedef bool bf::bitvector::const_reference

Unlike the reference type, a const_reference does not need lvalue semantics and can thus represent simply a boolean (bit) value.

Definition at line 53 of file bitvector.h.

Constructor & Destructor Documentation

bf::bitvector::bitvector	(	size_type	size,
		bool	value = `false`
	)

explicit

Constructs a bit vector of a given size.

Parameters

size	The number of bits.
value	The value for each bit.

Definition at line 98 of file bitvector.cc.

bf::bitvector::bitvector ( bitvector const & other )

Copy-constructs a bit vector.

Parameters

other The bit vector to copy.

Definition at line 104 of file bitvector.cc.

bf::bitvector::bitvector ( bitvector && other )

Move-constructs a bit vector.

Parameters

other The bit vector to move.

Definition at line 110 of file bitvector.cc.

Member Function Documentation

template<typename Iterator , typename std::enable_if< std::is_same< typename std::iterator_traits< Iterator >::iterator_category, std::forward_iterator_tag >::value >::type = 0>

void bf::bitvector::append	(	Iterator	first,
		Iterator	last
	)

inline

Appends the bits in a sequence of values.

Template Parameters

Iterator A forward iterator.

Parameters

first	An iterator pointing to the first element of the sequence.
last	An iterator pointing to one past the last element of the sequence.

Definition at line 127 of file bitvector.h.

References blocks(), and extra_bits().

Here is the call graph for this function:

void bf::bitvector::append ( block_type block )

Appends the bits in a given block.

Parameters

block The block containing bits to append.

Definition at line 324 of file bitvector.cc.

References extra_bits().

Here is the call graph for this function:

static size_type constexpr bf::bitvector::bits_to_blocks ( size_type bits )

inlinestaticprivate

Computes the number of blocks needed to represent a given number of bits.

Parameters

bits	the number of bits.

Returns: The number of blocks to represent bits number of bits.

Definition at line 260 of file bitvector.h.

Referenced by resize().

Here is the caller graph for this function:

size_type bf::bitvector::blocks ( ) const

Retrieves the number of blocks of the underlying storage.

Parameters

The	number of blocks that represent `size()` bits.

Definition at line 419 of file bitvector.cc.

Referenced by append(), count(), find_from(), flip(), and resize().

Here is the caller graph for this function:

size_type bf::bitvector::count ( ) const

Counts the number of 1-bits in the bit vector.

Also known as population count or Hamming weight.

Returns: The number of bits set to 1.

Definition at line 399 of file bitvector.cc.

References blocks().

Here is the call graph for this function:

bool bf::bitvector::empty ( ) const

Checks whether the bit vector is empty.

Returns: true iff the bitvector has zero length.

Definition at line 429 of file bitvector.cc.

size_type bf::bitvector::find_first ( ) const

Finds the bit position of of the first 1-bit.

Returns: The position of the first bit that equals to one or npos if no such bit exists.

Definition at line 434 of file bitvector.cc.

References find_from().

Here is the call graph for this function:

size_type bf::bitvector::find_from ( size_type i ) const

private

Looks for the first 1-bit starting at a given position.

Parameters

i	The block index to start looking.

Returns: The block index of the first 1-bit starting from i or bitvector::npos if no 1-bit exists.

Definition at line 469 of file bitvector.cc.

References blocks(), and lowest_bit().

Referenced by find_first(), and find_next().

Here is the call graph for this function:

Here is the caller graph for this function:

size_type bf::bitvector::find_next ( size_type i ) const

Finds the next 1-bit from a given starting position.

Parameters

i	The index where to start looking.

Returns: The position of the first bit that equals to 1 after position i or npos if no such bit exists.

Definition at line 439 of file bitvector.cc.

References bit_index(), block_index(), find_from(), lowest_bit(), and size().

Here is the call graph for this function:

bitvector & bf::bitvector::flip ( size_type i )

Toggles/flips a bit at a specific position.

Parameters

i	The bit position.

Returns: A reference to the bit vector instance.

Definition at line 372 of file bitvector.cc.

References bit_mask(), and block_index().

Here is the call graph for this function:

bitvector & bf::bitvector::flip ( )

Computes the complement.

Returns: A reference to the bit vector instance.

Definition at line 379 of file bitvector.cc.

References blocks().

Here is the call graph for this function:

size_type bf::bitvector::lowest_bit ( block_type block )

staticprivate

Computes the bit position first 1-bit in a given block.

Parameters

block The block to inspect.

Returns: The bit position where block has its first bit set to 1.

Definition at line 449 of file bitvector.cc.

Referenced by find_from(), and find_next().

Here is the caller graph for this function:

bitvector & bf::bitvector::operator= ( bitvector other )

Assigns another bit vector to this instance.

Parameters

other The RHS of the assignment.

Definition at line 124 of file bitvector.cc.

References swap.

bitvector::reference bf::bitvector::operator[] ( size_type i )

Retrieves a single bit.

Parameters

i	The bit position.

Returns: A mutable reference to the bit at position i.

Definition at line 393 of file bitvector.cc.

References bit_index(), and block_index().

Here is the call graph for this function:

bool bf::bitvector::operator[] ( size_type i ) const

Retrieves a single bit.

Parameters

i	The bit position.

Returns: A const-reference to the bit at position i.

Definition at line 387 of file bitvector.cc.

References bit_mask(), and block_index().

Here is the call graph for this function:

void bf::bitvector::push_back ( bool bit )

Appends a single bit to the end of the bit vector.

Parameters

bit	The value of the bit.

Definition at line 317 of file bitvector.cc.

References resize(), and size().

Here is the call graph for this function:

bitvector & bf::bitvector::reset ( size_type i )

Resets a bit at a specific position, i.e., sets it to 0.

Parameters

i	The bit position.

Returns: A reference to the bit vector instance.

Definition at line 359 of file bitvector.cc.

References bit_mask(), and block_index().

Referenced by bf::counter_vector::clear(), bf::basic_bloom_filter::clear(), and bf::basic_bloom_filter::remove().

Here is the call graph for this function:

Here is the caller graph for this function:

bitvector & bf::bitvector::reset ( )

Sets all bits to 0.

Returns: A reference to the bit vector instance.

Definition at line 366 of file bitvector.cc.

Referenced by set().

Here is the caller graph for this function:

void bf::bitvector::resize	(	size_type	n,
		bool	value = `false`
	)

Resizes the bit vector to a new number of bits.

Parameters

n	The new number of bits of the bit vector.
value	The bit value of new values, if the vector expands.

Definition at line 295 of file bitvector.cc.

References bits_to_blocks(), blocks(), and extra_bits().

Referenced by bf::basic_bloom_filter::basic_bloom_filter(), and push_back().

Here is the call graph for this function:

Here is the caller graph for this function:

bitvector & bf::bitvector::set	(	size_type	i,
		bool	bit = `true`
	)

Sets a bit at a specific position to a given value.

Parameters

i	The bit position.
bit	The value assigned to position i.

Returns: A reference to the bit vector instance.

Definition at line 340 of file bitvector.cc.

References bit_mask(), block_index(), and reset().

Referenced by bf::basic_bloom_filter::add().

Here is the call graph for this function:

Here is the caller graph for this function:

bitvector & bf::bitvector::set ( )

Sets all bits to 1.

Returns: A reference to the bit vector instance.

Definition at line 352 of file bitvector.cc.

size_type bf::bitvector::size ( ) const

Retrieves the number of bits the bitvector consist of.

Returns: The length of the bit vector in bits.

Definition at line 424 of file bitvector.cc.

Referenced by bf::basic_bloom_filter::add(), extra_bits(), find_next(), bf::basic_bloom_filter::lookup(), push_back(), bf::basic_bloom_filter::remove(), and bf::counter_vector::size().

Here is the caller graph for this function:

Member Data Documentation

block_type constexpr bf::bitvector::bits_per_block

static

Initial value:

=

std::numeric_limits<block_type>::digits

Definition at line 20 of file bitvector.h.

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

Classes

Public Types

Public Member Functions

Static Public Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation