Why does vector pointers takes so much memory?

Question

I'm working on a project where I need to be as mean as possible regarding the memory usage. I'm trying to calculate the grand total size of a vector<bool> of size 32 in the example:

vector<bool> v(32);
cout << "sizeof: " << sizeof(v) << endl;
cout << "size: " << v.size() << endl;
cout << "capacity: " << v.capacity() << endl;
cout << "max_size: " << v.max_size() << endl;

which gives me:

sizeof: 40                     <- 40 byte? wtf?
size: 32                       <- hoping an element takes up 1 bit
                                  (instead of the usual 1 byte for booleans)
                                  this should take around 32 bit memory
capacity: 64                   <- I guess this is because minimum size is
                                  1 integer = 64 bit
max_size: 9223372036854775744  <- relevant somehow?

on my 64 bit ubuntu 12.04 machine. So I thought I could calculate the memory like so:

40 * 8 + 64 * 1 = 384 bit = 48 byte

So according to this calculation most of the memory is spent for the vector object of size 32. My question is why does a vector object need to use so much memory? And also are there any mistakes in my calculation? How can I be more efficient without doing bitwise manipulations myself for vector sizes around 32?

Answer 1

Those 40 bytes are administrative overhead. Among other things, a vector has to keep track of its size and capacity (that's two size_ts worth of bytes gone already), and very importantly, a pointer to the actual data!

The actual data kept by the vector is allocated on the heap by the default vector allocator, its memory consumption is not included in the result of sizeof.

Answer 2

sizeof(v) is getting the size of v's structure, not the size of v's data. It's like doing:

struct S { int* x };

S s;
s.x = new int[10000];

sizeof(s); // only the size of int* (it doesn't/can't check how much data is allocated)

As for why std::vector<bool> might have a larger structure size than, say, std::vector<int>, remember that the bool version is specialized. It's got to have some extra members for bitwise record keeping.

Answer 3

• v.size() returns the number of elements that can be stored in the vector. Not memory-size-directly-related
• v.capacity() returns the amount of memory cells allocated for the vector. Vectors allocate some memory in advance, but not all can be accessed initially. Not-memory-size-directly-related
• sizeof(v) is getting the size in bytes of the structure itself. I suppose some pointers go here. As well as the size variable etc.

If you want to get the memory the elements of the vector are taking probably this would be the closest expression: v.size() * sizeof(v[0])

Answer 4

Looking at the source of the g++ implementation I can find the following members:

vector inherits from _Bvector_impl _M_impl;

From the inherited _Bvector_impl

_Bit_iterator   _M_start;   16 bytes
_Bit_iterator   _M_finish;  16 bytes
_Bit_type*  _M_end_of_storage;  8 bytes

This sums up to 40 bytes.

_Bit_iterator contains

_M_offset, an unsigned int: 8 bytes
_M_p,      a pointer 8 bytes. 

Answer 5

That's the price you pay for a dynamically re-sizable structure. What's returned by sizeof(v) is actually just the overhead for the vector to keep track of the dynamically allocated memory where it stores its data. The space for storing the data is not included in that number.

If you know the number of items at compile time, you can use std::bitset instead. std::bitset actually will use 1 bit per boolean you store (rounded up to the word size it uses) without the overhead of std::vector.

Answer 6

If the size of your std::vector is actually fixed at compile-time, then it may make sense to use a std::array instead; an array does not have any overhead (there is padding though).

However, in the very specific case of bool, you should consider std::bitset! A bitset is parameterized by its size and packs the bool as to be as efficient as possible. It's not exactly as memory efficient as a packed array (than you would write yourself) because it keeps a count of the toggled bits.

Demo at liveworkspace:

#include <bitset>
#include <array>
#include <vector>

#include <iostream>

int main() {
   std::vector<bool> vec(32);
   std::array<bool, 32> arr;
   std::array<uint8_t, 4> packed;
   std::bitset<32> bs;

   std::cout << "vector: " << sizeof(vec) + vec.capacity()/8 << "\n";
   std::cout << "array : " << sizeof(arr) << "\n";
   std::cout << "packed: " << sizeof(packed) << "\n";
   std::cout << "bitset: " << sizeof(bs) << "\n";
}

Gives:

vector: 48
array : 32
packed: 4
bitset: 8

Where packed clearly is the most efficient container, but bitset provides a ready-made one for a quite low cost (just as much space as a pointer on 64 bits machines).