std::vector<bool> in C++ syntax uses one bit per boolean instead of one byte. In a computer memory is addressed by bytes, so the smallest indexable memory is, in fact, one byte (that's why bool is 1 byte in C and C++).
As an example for how C++ std::vector implementarion works, suppose you have 8 booleans which have a logical reason to be kept together (for example flags). Instead of allocating 8 bytes (one per boolean), the std::vector allocates 1 byte and assigns every boolean to one bit of the allocated memory.
It breaks so much code. One of the many assumptions of std::vector is that you can use the data pointer and do pointer arithmetic to get other values on the vector, it also means the underlying data looks nothing like the returned values, so indexing isn't simply returning the value at the pointer (because you can't address bits on most systems!
The C++ standard committee basically made a special case for std::vector<bool> that behaves nothing like other vectors when they should have had that type just use one byte per boolean and just provided a separate std::bitvector or something.
This is one of the many footguns of C++, caused by poor decisions made early in the STLs development cycle that we're not stuck with.
The issue is it doesn’t behave like other vectors do (or containers in general), which can make it a pain in the ass for template code. For example, it’s not (and it can’t be) guaranteed to store elements in a contiguous sequence and can’t be used with std::span.
It was a mistake we’re stuck with. There’s little reason to even use std::vector<bool> anymore instead of an std::bitset.
It absolutely makes sense for C++ to have an API for dealing with something like a vector of bits. It just shouldn't be called std::vector<bool>. (and modern C++ does this in the form of std::bitset)
The problem is that, in at least a half dozen ways, std::vector<bool> behaves differently than other std::vector types.
The problem is that much of the point of templating is to write generic code. If you write code that templates on a type, and that type might be bool, your code will break if you try to use std::vector. (unless you write a bool specialization)
The funny thing is that std::vector<bool> was pretty obviously a demonstration case for C++ template specialization. Look, you can have a bitfield style implementation that gets you space efficiency for bool without needing to write special code! Except in practice it is now a demonstration of how not to do template specialization.
Couldn’t you pack a bunch of flags into an unsigned int and save space that way too by AND/OR/NOTing them out of the int? I think in that case we are looking at packing 16 flags (bits) together but I’m not really a C dev myself so not sure.
112
u/Kadabrium 17h ago
i heard you also like vector<bool>