Question: Is there a way of iterating over a (possibly huge) `std::bitset` that is *linear* in the *number of bits that are set to true*? I want to prevent having to check every single position in the bitset. The iteration should successively return the indices of each bit that is set to true.

Answer: 
A standard bitvector does not support efficient iteration over true bits - the runtime is always O(n), where n is the number of total bits, which has no dependence on k. However, there are specialized data structures like [van Emde Boas trees](http://en.wikipedia.org/wiki/Van_Emde_Boas_tree) and [y-fast tries](http://web.stanford.edu/class/archive/cs/cs166/cs166.1196/lectures/15/Slides15.pdf), that support iteration over the bits in time O(k lg lg n), where n is the number of bits and k is the number of true bits.
For that to be linear, you'd need a linked-list/array/set of the indices set true. Keeping such a secondary index is not part of the performance/storage tradeoffs required by std::bitset, and given it would disadvantage everyone without your specific requirement, there's no way an implementation will provide this. You could consider supplementing your bitset with such a container yourself, or using boost's multi-index container library.