Short:
How can I calculate correctly the memory space in bytes of std::vector<bool>
that store n bits?
std::vector<bool> vb(n, false);
int size_bytes = compute_space_memory_in_bytes(vb);
Detail:
In my algorithm i use vector<bool>
to store n bits. In order to measure it efficiently in practice, I need to know how to calculate the space memory in bytes. (In theory it is just O(n) bits).
There are 2 points:
If we have
std::vector<int>
, the solution from another answer is:
sizeof(std::vector<int>) + (sizeof(int) * MyVector.size())
Since vector store each Boolean value into a single bit
One potential optimization involves coalescing vector elements such that each element occupies a single bit instead of sizeof(bool) bytes.
Hence, from 1 and 2, my attempt solution is :
std::vector<bool> vb(100, false);
auto size_bytes = sizeof(vector<bool>) + vb.size()/8;
std::cout << "Hello, size = " << size_bytes << " bytes!\n";
Is that correct ?
Edit: To be more explicit (Thanks to @PaulMcKenzie comment):
Given n bits that to be determined at execution time. My problem is what is the space occupied (exactly or approximately) to store n bits in vector of bool?
std::vector<bool> vb;
// some processing to get n ..
vb.resize(n);
auto size_bytes = compute size of vb in bytes ???;
std::cout << "Hello, size = " << size_bytes << " bytes!\n";
sizeof(std::vector<bool>)
, is a compile-time value, and will not change regardless of the number of bools you assign to it at runtime.bool
) is completely implementation-defined. All you can say is that it’s ≥ 1, or ≥ number of elements / 8, whichever is larger (though in reality the implementation needs to store at least the size and the capacity, so these give a somewhat tighter lower bound).+ vb.capacity()/8;
is probably a little more accurate. A bunch of implementations use something like a int[] under the hood, so they will change the allocated memory in like 32-element increments at least. But even that is not fully accurate because it doesn't account for small-buffer optimization