pasta::bit_vector  v1.0.0
Compact and Fast Rank and Select Data Structure for Bit Vectors
pasta::BitVector Class Reference

Uncompressed, highly tuned, fixed size bit vector. More...

#include <bit_vector.hpp>

Classes

struct  Iterator
 Custom iterator for BitVector. More...
 

Public Types

using RawDataType = uint64_t
 Type that is used to store the raw data of the bit vector.
 
using RawDataPointer = RawDataType *
 
using RawDataConstAccess = RawDataType const *
 

Public Member Functions

 BitVector ()=default
 Default empty constructor.
 
 BitVector (BitVector const &)=delete
 Deleted copy constructor.
 
BitVectoroperator= (BitVector const &)=delete
 Deleted copy assignment.
 
 BitVector (size_t const size) noexcept
 Constructor. Creates a bit vector that holds a specific, fixed number of bits. More...
 
 BitVector (size_t const size, bool const init_value) noexcept
 Constructor. Creates a bit vector that holds a specific, fixed number of bits set to a default value. More...
 
BitAccess operator[] (size_t const index) noexcept
 Access operator to read/write to a bit of the bit vector. More...
 
BitAccess operator[] (size_t const index) const noexcept
 Access operator to read to a bit of the bit vector. More...
 
void resize (size_t const size) noexcept
 Resize the bit vector to contain size bits. More...
 
void resize (size_t const size, bool const init_value) noexcept
 Resize the bit vector to contain size bits and fill new bits with default value. More...
 
Iterator begin () noexcept
 Get iterator representing the first element of the BitVector. More...
 
Iterator end () noexcept
 Get iterator representing the end of the BitVector. More...
 
std::span< uint64_t > data () noexcept
 Direct access to the raw data of the bit vector. More...
 
std::span< uint64_t > data () const noexcept
 Direct access to the raw data of the bit vector. More...
 
uint64_t data (size_t const index) const noexcept
 Direct access to one 64-bit element of the raw data of the bit vector. More...
 
size_t space_usage () const
 Estimate for the space usage. More...
 
size_t size () const noexcept
 Get the size of the bit vector in bits. More...
 

Friends

template<OptimizedFor o, typename v >
class Rank
 Forward declaration.
 
template<OptimizedFor o, typename v >
class FlatRank
 Forward declaration.
 
template<OptimizedFor o, typename v >
class WideRank
 Forward declaration.
 
template<OptimizedFor o, typename v >
class RankSelect
 Forward declaration.
 
template<OptimizedFor o, FindL2FlatWith f, typename v >
class FlatRankSelect
 Forward declaration.
 
template<OptimizedFor o, FindL2WideWith f, typename v >
class WideRankSelect
 Forward declaration.
 
std::ostream & operator<< (std::ostream &os, BitVector const &bv)
 formatted output of the BitVector
 

Detailed Description

Uncompressed, highly tuned, fixed size bit vector.

The uncompressed bit vector can be used as a replacement for std::vector<bool>, when the size of the vector is known in advance. It provides an access operator.

Important: If you plan on accessing the data directly, note that the bits are stored in reverse order in the 64-bit words. This saves an subtraction, when shifting the bits for access. To be more precise, the bits are stored as follows (for simplicity, we show it for 8-bit words):

| 7 6 5 4 3 2 1 0 | 15 14 13 12 11 10 9 8 | 23 22 21 20 19 18 17 16 | ...

Member Typedef Documentation

◆ RawDataConstAccess

Type that can be used to access constant values of the raw data used to represent the bit vector.

◆ RawDataPointer

Pointer to the data type that is used to store the raw data of the bit vector.

Constructor & Destructor Documentation

◆ BitVector() [1/2]

pasta::BitVector::BitVector ( size_t const  size)
inlinenoexcept

Constructor. Creates a bit vector that holds a specific, fixed number of bits.

Parameters
sizeNumber of bits the bit vector contains.

◆ BitVector() [2/2]

pasta::BitVector::BitVector ( size_t const  size,
bool const  init_value 
)
inlinenoexcept

Constructor. Creates a bit vector that holds a specific, fixed number of bits set to a default value.

Parameters
sizeNumber of bits the bit vector contains.
init_valueValue all bits initially are set to. Either 0 (false) or 1 (true).

Member Function Documentation

◆ begin()

Iterator pasta::BitVector::begin ( )
inlinenoexcept

Get iterator representing the first element of the BitVector.

Returns
Iterator representing the first element of the BitVector.

◆ data() [1/3]

std::span< uint64_t > pasta::BitVector::data ( ) const
inlinenoexcept

Direct access to the raw data of the bit vector.

Note that the raw data does not contain the bits from left to right. A detailed description can be found at the top of this file.

Returns
std::span<uint64_t> pointing to the bit vector's raw data.

◆ data() [2/3]

std::span< uint64_t > pasta::BitVector::data ( )
inlinenoexcept

Direct access to the raw data of the bit vector.

Note that the raw data does not contain the bits from left to right. A detailed description can be found at the top of this file.

Returns
std::span<uint64_t> pointing to the bit vector's raw data.

◆ data() [3/3]

uint64_t pasta::BitVector::data ( size_t const  index) const
inlinenoexcept

Direct access to one 64-bit element of the raw data of the bit vector.

Note that the raw data does not contain the bits from left to right. A detailed description can be found at the top of this file.

Parameters
indexIndex of the 64-bit bit word that should be returned.
Returns
index-th 64-bit word of the raw bit vector data.

◆ end()

Iterator pasta::BitVector::end ( )
inlinenoexcept

Get iterator representing the end of the BitVector.

The end() method returns an iterator that may refers to an invalid memory address. It should never be accessed directly.

Returns
Iterator representing the end of the BitVector.

◆ operator[]() [1/2]

BitAccess pasta::BitVector::operator[] ( size_t const  index) const
inlinenoexcept

Access operator to read to a bit of the bit vector.

Parameters
indexIndex of the bit to be read to in the bit vector.
Returns
BitAccess that allows to read access to a single bit.

◆ operator[]() [2/2]

BitAccess pasta::BitVector::operator[] ( size_t const  index)
inlinenoexcept

Access operator to read/write to a bit of the bit vector.

Parameters
indexIndex of the bit to be read/write to in the bit vector.
Returns
BitAccess that allows to access to a single bit.

◆ resize() [1/2]

void pasta::BitVector::resize ( size_t const  size)
inlinenoexcept

Resize the bit vector to contain size bits.

Parameters
sizeNumber of bits the resized bit vector contains.

◆ resize() [2/2]

void pasta::BitVector::resize ( size_t const  size,
bool const  init_value 
)
inlinenoexcept

Resize the bit vector to contain size bits and fill new bits with default value.

Parameters
sizeNumber of bits the resized bit vector contains.
init_valueValue all bits that are appended to the bit vector (if any) will have.

◆ size()

size_t pasta::BitVector::size ( ) const
inlinenoexcept

Get the size of the bit vector in bits.

Returns
Size of the bit vector in bits.

◆ space_usage()

size_t pasta::BitVector::space_usage ( ) const
inline

Estimate for the space usage.

Returns
Number of bytes used by this data structure.

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