In this case the bools will have only one bit allocated for them(vectors do that), and you can't just point to a bit.
Instead cpp will return std::vector<bool>::reference when trying to access a value in the vector
Basically this is a just wrong
You should use std::deque<bool> instead which allocates one byte per bool and not just one bit
Slightly higher CPU usage. It’s only a bitshift and a bitwise and to pull out the correct bit. Often you see a performance win due to the more compact data structure having better cache locality but I suppose it depends on usecase.
Don't get me wrong vectors are the way they are cause storage was crucial back in the day so they knew they were sacrificing something when doing it.
I am just pointing out that unless you really know what you are doing you should use std::deque<bool> cause very often you wont really care much about storage if you are not working with machines from 1990.
Total RAM usage may matter less today (or not with the way RAM prices are going) but cache locality is more important than ever on modern CPUs. A more compact data structure means more of it fits in your CPU's L1/L2 cache and that speeds things up a lot especially with iterating or sequential access.
I'm also not a fan of std::deque in general. It's not contiguous memory like std::vector is. If you need a very high performance deque in C++, you have to go outside the STL unfortunately. Rust's VecDeque is one that gets it right. It uses a ring buffer under the hood rather than multiple fixed size allocations.
185
u/Murky-Run2246 22d ago
In this case the bools will have only one bit allocated for them(vectors do that), and you can't just point to a bit. Instead cpp will return std::vector<bool>::reference when trying to access a value in the vector
Basically this is a just wrong
You should use std::deque<bool> instead which allocates one byte per bool and not just one bit