A Simple Collection of Bits
In Redmond, Washington last October, I attended the C++ standards committee meeting for the first time in five years. Many faces were familiar, as were the procedures. There were two noticeable differences from previous meetings, however: 1) all members had their laptops constantly hooked up to the Internet, allowing us to spend as much time reading mail and playing games as we did listening, so almost every statement of consequence had to be repeated before action could be taken (kudos to Matt Austern for his patience with the Library Group), and 2) there was a whole lot more experience with advanced C++ techniques and concerns in the brains of Smart People there to help the committee make better decisions. So I guess things sort of balanced out.
Perhaps the most noteworthy item on the committee’s To Do list was to discuss what should constitute C++0x. (Yes, gentle reader, it’s time again for a new version of C++). See this month’s installments of “Sutter’s Mill” and “The Standard Librarian” for interesting copy on that topic.
Perhaps less noteworthy but still noticed by This Prodigal were the not-so-subtle barbs levied at valarray and vector<bool>. The valarray class template, as you may recall, is the slice-‘em-and-dice-‘em array class defined by and for scientific programmers. Supposedly no one is using this “embarrassment.” (If anyone “out there” is actually using it, please let me know.) Even more maligned is vector<bool>, the STL-ized version of the bitstring class I proposed and which was accepted into the standard library in 1993. I actually proposed two companion classes: bitset and bitstring. bitset holds bits the number of which is fixed at compile time, and was the first (and only?) class in the library to use a non-type template parameter. bitstring was a dynamic version of bitset — less efficient but more flexible (the quintessential trade-off). Both classes overloaded operator[] to use proxied indexing to allow for the optimization of packing bits into words. It seemed like a good idea at the time. I needed both in my work, so I proposed them, the committee accepted them, and that settled it.
And then along came STL. It was “obvious” that bitstring was just a simple sequence of bits, so the vector<bool> specialization took its place. As the requirements for STL containers were tightened up, I had to leave the committee, and like the proverbial neglected stepchild, vector<bool> was soon forgotten... until the Standard was finished and people actually started using the library. It turns out the vector<bool> is not a container after all; the proxy class gets in the way of getting a direct reference to an individual bit (of course). Furthermore, operator[] is defined, but the equivalent of a random access iterator is not. It is not possible, therefore, to use most standard algorithms on a vector<bool> object. So here we have a specialization of a container that itself is not a container.
Fine. I always thought we should have left bitstring alone anyway. But I thought a lot of things (like we should be able to define conversion operators to be explicit, just like single-arg constructors, for example). It turns out that the bitstring will reappear in a more modern form in a future proposal from that fleet of Smart People I alluded to in the first paragraph above. Then maybe we’ll have a more politically correct collection of bits (for those of us who care).
Chuck Allison
Senior Editor