Why the std::swap of Bits in a std::bitset instance doesn't work?

Question

In the following example i expected the swap of the bits. Instead the second bit becomes overwritten, but why and how could i achieve the expected behavior?

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    bitset<2> test(string("10"));
    cout << test; // Prints "10"
    swap(test[0], test[1]);
    cout << test; // Prints "11", why not "01"?
}

Answer 1

This is pure nasty. First we have to look at the declaration of swap:

template<class T>
void swap(T &left, T &right);

Now, operator[]() on bitset has two overloads:

bool operator[](size_type _Pos) const;
reference operator[](size_type _Pos);

Here reference is bitset::reference, a nested class in bitset that effectively acts as a proxy reference to the one of the underlying bits. What it encapsulates is the bitset and a position in the bitset. Because of the declaration of swap, the second overload is chosen and we are swapping two bitset::references. Now here's where it gets nasty. Let's look at a typical implementation of swap:

template class<T> swap(T &left, T &right) {
    T temp = left;
    left = right;
    right = temp;
}

The problem is that left and right are both references to a bitset::reference. They have the same underlying data (because they are proxies; same meaning the both point to the same bitset!) they just encapsulate different positions in that bitset. Thus, think of it like this left is position 0 in some bitset and right is position 1 in some bitset and that bitset is the same bitset as left! Let's forever refer to this bitset as BS (chosen intentionally).

So,

T temp = left;

says that temp is position 0 in BS.

left = right;

sets position 0 in left to position 1 in BS (which simultaneously changes position 0 in temp!)

right = temp;

sets position 1 in right to position 0 in BS (which was just set to position 1 in BS!). So at the end of this mess have that position 0 is whatever position 1 was and position 1 is unchanged! Now, because position 0 is the LSB and position 1 is the MSB we have that "10" becomes "11". Ugly.

You can get around this with a template specialization:

namespace std {
    template<>
    void swap<bitset<2>::reference>(
        bitset<2>::reference &left,
        bitset<2>::reference &right
    ) {
        bool temp = (bool)left;
        left = (bool)right;
        right = (bool)temp;
    }
}

Then:

int main() {
    bitset<2> test(string("10"));
    cout << test; // Prints "10"
    swap(test[0], test[1]);
    cout << test; // Prints "01", hallelujah!
}

Answer 2

There's no value type in C++ to represent a single bit, so when you use the [] operator to access an element of a bitset, what you get is a proxy object that serves as an alias for the bit you requested. Assigning to that proxy object changes the corresponding bit value in the original bitset object.

As Victor's answer shows, your code doesn't compile with GCC. But let's suppose the call to swap would compile. You'd get code that amounts to something like this:

void swap(std::bitset<2>::reference& a, std::bitset<2>::reference& b)
{
  std::bitset<2>::reference tmp = a;
  a = b;
  b = tmp;
}

The tmp declaration initializes the variable with a, but that doesn't make a copy of the bit. Instead, it makes a copy of the proxy object, so tmp refers to the same bit in the same bitset that a refers to. The next line assigns b to a, which copies the bit value from the location a refers to and stores it in the bit location b refers to. Finally, there's the assignment of tmp into b. But remember that tmp still refers to the bit that a refers to. Reading tmp is the same as reading a, so you ultimately get the same effect you'd get if swap were just these two lines:

a = b;
b = a;

In your code, a is 0 and b is 1, so with those two assignment statements, 11 is exactly what we'd expect to see.