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: 
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.
There are only two options that do much better than O(N) on total bits:

1. Using specialty bit-scan instructions available in certain architectures like [BSF in x86](http://www.posix.nl/linuxassembly/nasmdochtml/nasmdoca.html#section-A.10).
2. There are O(log2(N)) algorithms for finding the lowest bit set in a word. This, of course does not scale well when the bitset is dense, rather than sparse. Resurrecting some foggy memory of mine, I found the source in the [FXT library](http://www.jjj.de/fxt/) Details can be found in the [FXT book (pdf)](http://www.jjj.de/fxt/fxtbook.pdf), in section 1.3.2.