`bit::vector` — Iteration Over Set Bits

We provide methods to iterate over the set elements/bits in a bit-vector.

1constexpr std::size_t first_set() const;
2constexpr std::size_t final_set() const;
3constexpr std::size_t next_set(std::size_t pos) const;
4constexpr std::size_t prev_set(std::size_t pos) const;

1: Returns the index of the first set element or npos if none are set.
2: Returns the index of the final set element or npos if none are set.
3: Returns the index of the next set element after the argument or npos if there are no more set elements.
4: Returns the index of the previous set element before the argument or npos if there are no more set elements.

In these methods, pos is the index from which to start a search. It doesn’t have to be the index of a set element.

A return value of bit::vector::npos indicates that the search failed.

Example

#include <bit/bit.h>
int main()
{
1    bit::vector<> v(11, [&](size_t k) { return (k + 1) % 2; });
    std::cout << "The set indices in " << v << " are ";
2    auto pos = v.first_set();
3    while (pos != bit::vector<>::npos) {
        std::cout << pos << ' ';
4        pos = v.next_set(pos);
    }
    std::cout << '\n';
}

1: Creates a vector of size 11 by calling a lambda that sets all the even indices.
2: Find the index of the first set element (should be 0).
3: Keep going until the search fails.
4: Find the index of a set bit after the current pos.

Output

The set indices in [1 0 1 0 1 0 1 0 1 0 1] are 0 2 4 6 8 10

See Also