Main Page

My Games

My Projects

My Music

My Art

My Literature
- Technical Articles
- | - Particle Systems
- | - The Mystery of std::vector<bool>::operator[]
- | - ASN.1 BER Basics
- Poems
- Definitions
- Quotes
- Language Problems
- Stories
- Documentation


The Mystery of std::vector<bool>::operator[]

The vector<bool> class

vector<bool> is just a specialization of the stl vector. With no specialization, every bool in the array would require 4 bytes (may be more maybe less, depending on compiler and platfrom) to store. In the specialized version of the class, each bool is packed so that it only requires 1 bit to store. For large arrays of boolean data, this is a huge memory savings.

The Mysterious operator[]

In the non-specialized case, after template expansion, you might have your [] operators defined something like this:
  const bool& operator[](unsigned int i) const;
  bool& operator[](unsigned int i);
This would allow statements like this to work as expected:
  std::vector<bool> myArray;
  bool something=myArray[5];

Now consider the specialized case. For simplicity, lets assume that an array of 32 bit unsigned ints is used internally. Then 32 bools would fit in a single int. So internally, to "store" or "retrieve" a bool from part of an int, bitwise & and | operators would be applied. Now, recall that pointers can only point to byte boundaries. You cannot create a pointer (and hence a reference) to just a single bit floating out in memory somewhere. This means that the above definition for the [] operators cannot be used here. Consider for example, how the myArray[5]=true; would work.

Creating a Proxy class.

It is impossible to return a reference to a single bit within the array of ints. This is where a proxy class comes in. The idea is that the non-const version will return a copy of a class that will "act like" a bool. Consider this class as an example:
  class ProxyBool
     std::vector<bool> &mySource;
     unsigned int myIndex;
     inline ProxyBool(std::vector<bool> &scr, unsigned int &ind): mySource(src), myIndex(ind) {}
     inline operator bool() { return mySource.GetBit(myIndex); }
     inline const bool operator=(const bool &value) { mySource.SetBit(myIndex,value); }
Where the SetBit and GetBit functions of the std::vector<bool> just set or retrieve a specific bit in the array. Now you can define your [] operators as follows:
  const bool operator[](unsigned int i) const;
  inline ProxyBool operator[](unsigned int i) { return ProxyBool(*this,i); }
Now the myArray[5]=true; from the above code will work as expected. First the [] operator is called, which returns a ProxyBool. Then the operator= on the ProxyBool is called which sets the bit in myArray correctly.

(c)2012 Luke Lenhart   -  81165 total visitors