Main Page My Games My Projects My Music My Art My Literature - Technical Articles - | - - | - - | - - Poems - Definitions - Quotes - Language Problems - Stories - Documentation Links |
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; myArray.resize(30); myArray[5]=true; 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 { private: std::vector<bool> &mySource; unsigned int myIndex; public: 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.
|