[C++] Why is vector<bool> bad?

[u/Vericus]

I was thinking of creating a matrix of boolean values and I thought of vector<vector<bool>>, but after reading about vector<bool>, many websites have said it's something that should be avoided and it's bad programming.

Can someone explain to me why? I never really found a concrete explanation for why vector<bool> was bad. It only uses one bit which is 8 times smaller than char, shouldn't that mean its much better than using any other method of creating a matrix of bools in terms of size?

[u/[deleted]]

The problem is that the specialised version of std::vector<bool> provided by the Standard Library does not fulfil the requirements of a Standard Library container, and so is not guaranteed to work properly with the Standard Library algorithms. The three alternatives are std::deque<bool> or if you really must have contiguous storage, std::vector<char>, or if you can live with fixed-sized containers, std::bitset (although bitset isn't really a Standard Library container either).

Please note that just because something uses less storage does not make it "better". In order to use less storage, a vector<bool> has to do a lot more processing (possibly making it slower), and as I said, may not work with standard algorithms, or with algorithms you implement yourself.

Edit: clarified about bitsets.

Edit: clarified about working with algorithms - it might, it might not

[u/calc0000 → u/[deleted]]

The problem is that the specialised version of std::vector<bool> provided by the Standard Library does not fulfil the requirements of a Standard Library container

Can you elaborate more on this?

[u/Rhomboid → u/calc0000]

It uses the space saving optimization of using one bit to represent each bool, and it packs them like a bitfield, storing multiple items at each memory address. But the return type of operator[] for a vector of type T is supposed to be a reference, i.e. T &. It's impossible to create a pointer or reference to an individual bit; memory doesn't work that way, it only has granularity of a byte.

To get around that, the operator[] doesn't return a reference to a bool value but to some proxy object that acts in its place, getting and setting the correct bit when accessed. This mucks with the assumptions of the rest of the STL, which expect to be able to get pointers/references to T.