error: invalid initialization of non-const reference of type ‘bool&’ from an rvalue of type ‘std::vector<bool>::reference {aka std::_Bit_reference}’

Question

Why do I get the error: invalid initialization of non-const reference of type ‘bool&’ from an rvalue of type ‘std::vector::reference {aka std::_Bit_reference}’?

vector<vector<bool>> vis;
bool& visited(int x, int y)
{
    return vis[x][y]; //error
}

As far as I know operator[] in vector returns reference, so it should be an lvalue, but it doesn't work. What should I do to make it work?

Answer 1

That's because std::vector< bool > is not what it looks like.

There's a specialization for std::vector with type bool - it's space optimized and uses a single bit for each element.

You can try to use uint8_t or something like this, if you need this functionality. Or just return bool, not bool&.

The reference, returned by operator[] is not a standard reference, but a proxy class, which complicates the things here.

There are a lot of similar questions about this here:

• operator |= on std::vector<bool>
• Why vector<bool>::reference doesn't return reference to bool?
• Is the use of std::vector<bool> objects in C++ acceptable, or should I use an alternative?

And others. Read more about std::vector< bool > specialization.

Answer 2

Normally, what you've assumed is the case, for literally any vector<T> except vector<bool>. The original C++98 standard specified that as a bit-packed vector, and so references to the individual elements are impossible.

This has since been recognized as an inconvenient mistake, but backward compatibility means that it can't be changed now.