39

It appears that std::bitset does not come with STL iterators.
Therefore, I cannot do the following: 

std::bitset<8> bs;
for (auto it: bs) {
    std::cout << "this can not be done out of the box\n";
}

Instead I must: 

std::bitset<8> bs;
for (std::size_t i = 0; i < bs.size(); ++i) {
    std::cout << bs[i] << '\n';
}

Without iterators, I also can't use bitsets with any of the STL algorithms.
Why did the committee decide to exclude iterators from bitset?

Trevor Hickey
  • 36,288
  • 32
  • 162
  • 271
  • 1
    Just as a reference, from B.Stroustrup: "For historical reasons, bitset differs in style from other standard-library classes. ... No iterators are provided. " You can find it in the B.Stroustrup's "The C++ Programming Language" book. "34.2.2 bitset" – StahlRat Jan 11 '16 at 18:17
  • @StahlRat do you have a link to that? – NathanOliver Jan 11 '16 at 18:19
  • 1
    @NathanOliver https://books.google.co.uk/books?id=kCF4BgAAQBAJ&lpg=PA978&ots=hHkkK-K_dP&dq=stroustrup%20for%20historical%20reasons%2C%20bitset%20differs%20in%20style%20from%20other&pg=PA978#v=onepage&q&f=false – Columbo Jan 11 '16 at 18:20

2 Answers2

20

I don't think there was ever an actual decision to exclude iterators from bitset.

Rather, bitset is one of the classes that predates the proposal to add the original Standard Template Library to the C++ standard. When it was designed, essentially none of the standard library included iterators.

Then, Stepanov's library was proposed for addition, and quite a bit of it was accepted. In response to that, additions were made to some existing classes (e.g., std::string) to allow them to be used like the new container classes.

This was all happening quite late in the standards process though--in fact, they already bent the rules in a few places to add what they did. Among other things, just about the same time as the containers/iterators/algorithms were added to the library, the committee voted to consider the standard "feature complete", so from that point onward they'd only work on fixing bugs and such, not adding new features.

As such, even if a proposal had been written to add an iterator interface to bitset, about the only way the committee could have accepted it would have been to treat this as a bug being fixed rather than a new feature being added. If there'd been a really solid proposal, I suppose they could have done that, but I don't think there was such a proposal, and it would have been stretching the point quite a bit, so even a really good proposal might easily have been rejected.

Since then, there was one proposal, LEWG 1112, that would have added an iterator interface to std::bitset. This was proposed for C++11, and was proposed specifically to support the range-based for loop that was also being added in C++11. It suffered a rather ignominious fate: it was originally accepted, and wording was drafted. Then it looked like the proposal for adding Concepts to the language would be accepted, so this wording was rewritten to use the shiny, wonderful new concepts. Sometime later, concepts were removed from the language, and rather than rewording the proposal so it no longer depended on concepts, they tentatively marked it as "NAD Future", which means they treated it as not being a defect, and deferred any further work until some (indefinite) time in the future (and as far as I can see, haven't revisited it since).

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • 5
    It's also important to note that they could not be proper iterators until the committee allows proxy iterators to be genuine iterators. Most algorithms are allowed to assume that what is returned from `*it` is a genuine reference to a genuine `iterator::value_type`, instead of possibly being a proxy object. – Nicol Bolas Jan 11 '16 at 18:48
  • @NicolBolas: That, in itself, apparently didn't bother the committee too much at the time (c.f. `std::vector`). – Jerry Coffin Jan 11 '16 at 19:10
  • 1
    It's more likely that they simply weren't very aware of the problem at the time. Particularly with how easy it is to under-specify behavior without explicit concepts. Not that it took very long to discover of course; [the first widely publicized discussion of the problem being in 1999](http://www.gotw.ca/publications/mill09.htm); shortly after standardization but well after STL had been in semi-wide use. – Nicol Bolas Jan 11 '16 at 19:28
  • @NicolBolas: Oh, I don't think they were really entirely aware of the problem at the time--I just mean that they used a proxy iterator in one place already, so adding a second wouldn't necessarily have been a huge leap in itself. – Jerry Coffin Jan 11 '16 at 19:31
  • Oh. I was thinking more in terms of why they didn't add them in C++11/14. – Nicol Bolas Jan 11 '16 at 21:05
  • 1
    @NicolBolas: There, the closest it seems to have come was in [LEWG issue 1112](http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#1112), where they initially proposed adding iterators to support range-based for loops, then changed it to use Concept-based wording, then changed to "NAD Future" when concepts were removed. – Jerry Coffin Jan 11 '16 at 21:22
  • 3
    @RexYuan: At least as far as I can see, it still doesn't have iterator support. – Jerry Coffin Oct 05 '20 at 16:05
  • 2
    It's 2021 now! We have concepts! go go go `std::bitset::iterator`! – JHBonarius Dec 18 '21 at 11:24
2

You can create your own iterator, or just use mine

Usage is as follows:

#include <bitset>
#include "bitset_iterator.h"

std::bitset<32> indices{ 0b10101010101010101010101010101010 };

for (const auto& index : indices) {
  std::cout << index << ", ";
}
// Prints "1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, "
Diegum
  • 55
  • 4