Sparse bit vector that stores only elements containing set bits.

Synopsis

Declared in <llvm/ADT/SparseBitVector.h>

template<unsigned int ElementSize = 128>
class SparseBitVector;

Description

SparseBitVector is an implementation of a bitvector that is sparse by only storing the elements that have non‐zero bits set. In order to make this fast for the most common cases, SparseBitVector is implemented as a linked list of SparseBitVectorElements. We maintain a pointer to the last SparseBitVectorElement accessed (in the form of a list iterator), in order to make multiple in‐order test/set constant time after the first one is executed. Note that using vectors to store SparseBitVectorElement's does not work out very well because it causes insertion in the middle to take enormous amounts of time with a large amount of bits. Other structures that have better worst cases for insertion in the middle (various balanced trees, etc) do not perform as well in practice as a linked list with this iterator kept up to date. They are also significantly more memory intensive.

Type Aliases

Name

Description

iterator

Forward iterator yielding the indices of set bits in ascending order.

Member Functions

Name

Description

SparseBitVector [constructor]

Constructors

operator=

Assignment operators

begin

Return an iterator to the first set bit, or end() if none are set.

clear

Remove all elements, leaving this vector empty.

contains

Return true if every bit set in RHS is also set in this vector.

count

Return the total number of bits set across all elements.

empty

Return true if this vector stores no elements (no bits are set).

end

Return a past‐the‐end iterator for the set‐bits range.

find_first

Return the index of the first set bit, or ‐1 if none are set.

find_last

Return the index of the last set bit, or ‐1 if none are set.

intersectWithComplement

intersectWithComplement overloads

intersects

intersects overloads

operator&=

Intersect this vector with RHS in place.

operator|=

Union this vector with RHS in place.

reset

Clear bit Idx, erasing its element if it becomes empty.

set

Set bit Idx, inserting an element if needed.

test

Return true if bit Idx is set.

test_and_set

Set bit Idx if it was clear.

operator==

Return true if this vector has the same set bits as RHS.

operator!=

Return true if this vector's set of bits differs from RHS.

Non-Member Functions

Name

Description

dump

Write the set‐bit indices of LHS to out as a bracketed space list.

operator&

Return a sparse bit vector that is the intersection of LHS and RHS.

operator&=

Intersect LHS with *RHS in place.

operator&=

Intersect *LHS with RHS in place.

operator‐

Return a sparse bit vector with bits of LHS that are clear in RHS.

operator|

Return a sparse bit vector that is the union of LHS and RHS.

operator|=

Union *LHS with RHS in place.

operator|=

Union LHS with *RHS in place.

Created with MrDocs