BitArray - Documentation

Indices and tables

Docs

template<typename T>
class BitArray

Class to represent an array of bits.

Accepts any type fulfilling the std::is_integral constraint with a power of 2 size (in bytes) as its underlying block type.

tparam T

The type to use as the underlying block type

Public Types

using value_type = bool
using iterator = Iterator<block_type>
using const_iterator = Iterator<const block_type>
using reverse_iterator = ReverseIterator<block_type>
using const_reverse_iterator = ReverseIterator<const block_type>

Public Functions

inline BitArray()

Construct a new Bit Array object.

Calls

BitArray(long long num_bits)
with the default number of bits

inline BitArray(long long num_bits)

Construct a new Bit Array object of a given size.

Note that exactly num_bits bits are not stored, the size is rounded up to the nearest multiple of the size of the underlying block type

All bits are initialized to the cleared state

Parameters

num_bits – The number of bits to use

inline void set_all()

Sets all bits.

inline void clear_all()

Clears all bits.

inline bool accessible(std::size_t bit) const noexcept

Checks if a bit being accessed is within bounds.

Parameters

bit – The index of the bit

Returns

true If the bit is within bounds

Returns

false If the bit is out of bounds

inline void set(std::size_t index)

Sets a bit.

Applies the bitmask returned by block_bitmask to the required block

Parameters

index – The bit to be set

inline void clear(std::size_t index)

Clears a bit.

Does the exact opposite of set , applies the bit negation of the block bitmask to the required block

Parameters

index – The bit to be cleared

inline bool at(std::size_t index)

Access a bit at an index.

Throws

std::range_error – When the accessed bit is out of bounds

Parameters

index – The bit to be accessed

Returns

true If the bit is set

Returns

false If the bit is cleared

inline bool operator[](std::size_t index) const noexcept

Accesses a bit at an index (unchecked)

This function is potentially dangerous, as it does not check if the index is out of bounds

Parameters

index – The bit to be accessed

Returns

true If the bit is set

Returns

false If the bit is cleared

inline std::size_t size() const noexcept

Return the size of the array in terms of number of bits.

Returns

std::size_t The size of the array

inline iterator begin() const noexcept

Non-const bi-directional forward iterator.

Returns

iterator The iterator pointing to the first bit

inline iterator end() const noexcept

Non-const bi-directional forward iterator.

Returns

iterator The iterator pointing to one past the last bit

inline const_iterator cbegin() const noexcept

Const bi-directional forward iterator.

Returns

const_iterator The iterator pointing to the first bit

inline const_iterator cend() const noexcept

Const bi-directional forward iterator.

Returns

const_iterator The iterator pointing one past the last bit

inline reverse_iterator rbegin() const noexcept

Non-const bi-directional reverse iterator.

Returns

reverse_iterator The iterator pointing to the last bit

inline reverse_iterator rend() const noexcept

Non-const bi-directional reverse iterator.

Returns

reverse_iterator The iterator pointing one before the first bit

inline const_reverse_iterator crbegin() const noexcept

Const bi-directional reverse iterator.

Returns

const_reverse_iterator The iterator pointing to the last bit

inline const_reverse_iterator crend() const noexcept

Const bi-directional reverse iterator.

Returns

const_reverse_iterator The iterator pointing one before the last bit

inline ~BitArray()

Destroy the Bit Array object.

Private Types

using block_type = T

Private Functions

inline bool bit_at(std::size_t index) const noexcept

Return the bit at a given index.

Parameters

index – The value of the index

Returns

true If the bit at the index is set

Returns

false If the bit at the index is not set

Private Members

block_type *blocks = nullptr

The array storing the actual blocks of bits.

long long bits = 0

The number of bits stored in the array.

Private Static Functions

static inline block_type block_bitmask(std::size_t index) noexcept

Return a bitmask representing the bit at a particular index.

While the index used in the calculation refers to the array as a whole, the returned bitmask only applies to the block which contains the bit at the accessed index

Parameters

index – The index

Returns

block_type The mask used to extract the required bit

Private Static Attributes

static constexpr std::size_t bits_per_block = sizeof(block_type) * __CHAR_BIT__

The number of bits stored in a block, equivalent to the size of the type in bits.

static constexpr std::size_t default_size = 16

The default number of bits to be allocated for the bit array.

template<typename ...Ts>
static constexpr bool always_false = false
template<typename ...Ts>
static constexpr bool always_true = true
template<typename IterType>
class Iterator

Public Functions

inline Iterator()
inline Iterator(IterType *ptr, long long idx)
inline Iterator operator++()
inline Iterator operator--()
inline Iterator operator++(int)
inline Iterator operator--(int)
inline bool operator*()
inline bool *operator->()
inline bool operator==(Iterator other) const noexcept
inline bool operator!=(Iterator other) const noexcept

Private Members

IterType *ptr = {nullptr}
long long current_idx = {0}
template<typename IterType>
class ReverseIterator

Public Functions

inline ReverseIterator()
inline ReverseIterator(IterType *ptr, long long idx, long long nbits)
inline ReverseIterator operator++()
inline ReverseIterator operator--()
inline ReverseIterator operator++(int)
inline ReverseIterator operator--(int)
inline bool operator*()
inline bool *operator->()
inline bool operator==(ReverseIterator other) const noexcept
inline bool operator!=(ReverseIterator other) const noexcept

Private Members

IterType *ptr = {nullptr}
long long current_idx = {0}