CODEWITHSUNDEEP
c++vectorbooleansizeof
ibra
ibra

Reputation: 1304

The size in bytes of vector<bool> that store n bits in c++

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:

  1. If we have std::vector<int>, the solution from another answer is:
    sizeof(std::vector<int>) + (sizeof(int) * MyVector.size())

  2. 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";

Upvotes: 5

Views: 696

Answers (1)

Vlad Feinstein
Vlad Feinstein

Reputation: 11311

For your re-stated question:

How to compute the sizeof to get the answer of space occupied

As others pointed out, different implementation of vector may produce different answers to your question.

Generally speaking, the memory "occupied" by your boolean values, in bytes, is:

int s = (n + 7) / 8;

If your implementation uses 32- or 64-bit values to pack bool into a vector, you need to round up to 32 or 64:

int s = (n + 31) / 32;

or

int s = (n + 63) / 64;

There is some memory that an instance of the vector itself uses (pointer to the first element, number of elements or a pointer to the last element, capacity, etc.); as @paulsm4 stated, it is 40 bytes in his implementation of the vector.

You may also want to consider allocated but not yet occupied memory. This also depends on implementation.

In conclusion, you can definitely state only the MINIMUM size your vector will occupy.

Upvotes: 3

Related Questions