2010-10-19

C++ STL containers: memory experimentations

For future reference (mainly for myself), here's how some C++ STL containers behave in terms of memory consumption.
g++ (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5
64-bit (i'm sure the values will be different in 32-bit)
Compiled with -O3.
E is number of elements in the container
std::vector:
24 bytes + 1*E (but memory is allocated in chunks: 0, 16, 32, ... *bytes* (not elements))
std::list:
16 bytes + { 128 (char)  || 128 (one int or long) || 192 (3 longs) 256 (4 longs) || 256 (5 longs) || 320 (6 longs) } * E
So, it appears std::list allocates 16 bytes (one pointer), but then allocates, per element, always a multiple of 64 bytes!
In any case surprises to be expected.  std::vector allocates 24+16 = 40 bytes for a vector with only one "char".  An std::list of char's appears to need 128 bytes to store each char!

Update:

std::set of int*:   48 bytes + 192*E



Update2:
I have measured the previous values using MAX RSS of the process (/usr/bin/time). Running with massif, I am obtaining a value of 40 bytes for each element of a std::list<int*>. But still, theoretical value would be 24 bytes (3 pointers), not 40. And massif is a simulator, not a real implementation. What matters is the memory occupied by a process in a real system, and for that MAX RSS is a more accurate measure.