I've had this sitting in my drafts for a while, the other bitset thread
inspired me to post it. Decided to make a new thread to avoid derailing the
other one.


I think it would be nice if std::bitset had a way to find the first/next
set bit.

MOTIVATION

I recently sped up some code quite a lot. It had a container of optional
work items. I changed to using a separate std::bitset to mark whether each
element contained a valid work item. Something like this:

some_container_smaller_than_65 work_items;
std::bitset<64> valid;

When looking for a valid work item, one can simply pick the first set bit
in the "valid" bitset. This can be done very efficiently with e.g. the
tzcnt instruction on x86, or rbit+clz on ARM.

Similarly, one can also very efficiently (with an extra instruction or two)
find the next set bit after a given index, making it possible to
efficiently iterate over the set bits.

(In my case, we also had "ready" and "done" bitsets, so it took only a few
instructions to find the first/next work item that was valid and ready but
not done.)

EXISTING IMPLEMENTATIONS

libstdc++ already supports _Find_first() and _Find_next():
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/std/bitset#L1450-L1471

Would there be interest in standardizing these functions?

We also implemented an iterator to iterate over the set bits, but that
might be a bit too unconventional to fit into the standard? And if we
standardize find_first and find_next, it's easy to implement an iterator
yourself.

Interested to hear your thoughts before writing a proper proposal.

Thanks,
Anders Schau Knatten