Bitset Reference

Question

From http://www.cplusplus.com/reference/stl/bitset/:

Because no such small elemental type exists in most C++ environments, the individual elements are accessed as special references which mimic bool elements.

How, exactly, does this bit reference work?

The only way I could think of would be to use a static array of chars, but then each instance would need to store its index in the array. Since each reference instance would have at least the size of a size_t, that would destroy the compactness of the bitset. Additionally, resizing may be slow, and bit manipulation is expected to be fast.

Answer 1

I think you are confusing two things.

The bitset class stores the bits in a compact representations, e.g. in a char array, typically 8 bits per char (but YMMV on "exotic" platforms).

The bitset::reference class is provided to allow users of the bitset class to have reference-like objects to the bits stored in a bitset.

Because regular pointers and references don't have enough granularity to point to the single bits stored in the bitset (their minimum granularity is the char), such class mimics the semantic of a reference to fake reference-like lvalue operations on the bits. This is needed, in particular, to allow the value returned by operator[] to work "normally" as an lvalue (and it probably costitutes 99% of its "normal" use). In this case it can be seen as a "proxy-object".

This behavior is achieved by overloading the assignment operator and the conversion-to-bool operator; the bitset::reference class will probably encapsulate a reference to the parent bitset object and the offset (bytes+bit) of the referenced bit, that are used by such operators to retrieve and store the value of the bit.

---EDIT---

Actually, the g++ implementation makes the bitset::reference store directly a pointer to the memory word in which the byte is stored, and the bit number in such word. This however is just an implementation detail to boost its performance.

By the way, in the library sources I found a very compact but clear explanation of what bitset::reference is and what it does:

  /**
   *  This encapsulates the concept of a single bit.  An instance of this
   *  class is a proxy for an actual bit; this way the individual bit
   *  operations are done as faster word-size bitwise instructions.
   *
   *  Most users will never need to use this class directly; conversions
   *  to and from bool are automatic and should be transparent.  Overloaded
   *  operators help to preserve the illusion.
   *
   *  (On a typical system, this <em>bit %reference</em> is 64
   *  times the size of an actual bit.  Ha.)
   */

Answer 2

I haven't looked at the STL source, but I would expect a Bitset reference to contain a pointer to the actual bitset, and a bit number of size size_t. The references are only created when you attempt to get a reference to a bitset element.

Normal use of bitsets is most unlikely to use references extensively (if at all), so there shouldn't be much of a performance issue. And, it's conceptually similar to char types. A char is normally 8 bits, but to store a 'reference' to a char requires a pointer, so typically 32 or 64 bits.