Pitfalls with vector<bool>

The std::vector template has one special case: std::vector<bool>. Since the bool datatype has only two possible values, the values of eight bools can be packed into a single byte. std::vector<bool> uses this optimization, which means that it uses eight times less heap-allocated memory than you might naturally expect.

The downside of this packing is that the return type of vector<bool>::operator[] cannot be bool&, because the vector doesn't store actual bool objects anywhere. Therefore, operator[] returns a customized class type, std::vector<bool>::reference, which is convertible to bool but which is not, itself, a bool (types like this are often called "proxy types" or "proxy references").

The result type of operator[] const is "officially" bool, but in practice, some libraries (notably libc++) return a proxy type for operator[] const. This means that code using vector<bool> is not only subtle but sometimes non-portable as well; I advise avoiding vector<bool> if you can:

    std::vector<bool> vb = {true, false, true, false};

    // vector<bool>::reference has one public member function:
    vb[3].flip();
    assert(vb[3] == true);

    // The following line won't compile!
    // bool& oops = vb[0];

    auto ref = vb[0];
    assert((!std::is_same_v<decltype(ref), bool>));
    assert(sizeof vb[0] > sizeof (bool));

    if (sizeof std::as_const(vb)[0] == sizeof (bool)) {
      puts("Your library vendor is libstdc++ or Visual Studio");
    } else {
      puts("Your library vendor is libc++");
    }