STL vector memory footprint

Apologies if this has been answered somewhere, but Google did not
produce any concrete
results. I would like to find out the memory footprint of a vector<T>.

I tried to dig in the STL code and if I understand correctly, its 3 *
void(*) +
sizeof(T) * size_of_vector. (3 ptrs for __M_start, __M_finish and
__M_end_of_storage).
If any STL guru could confirm my findings, that would be much
appreciated.
Also, if someone could throw in the memory numbers for STL hashmap and
set,
that would be great!

Thanks.

Varun Kacholia <kacholia@gmail.com> wrote:[color=blue]
> Apologies if this has been answered somewhere, but Google did not
> produce any concrete
> results. I would like to find out the memory footprint of a vector<T>.
>
> I tried to dig in the STL code and if I understand correctly, its 3 *
> void(*) +
> sizeof(T) * size_of_vector. (3 ptrs for __M_start, __M_finish and
> __M_end_of_storage).
> If any STL guru could confirm my findings, that would be much
> appreciated.
> Also, if someone could throw in the memory numbers for STL hashmap and
> set,
> that would be great![/color]

What you dug up is specific to your implementation. Mine might be
completely different. What is wrong with using sizeof (std::vector <T>)
(where T is the type you are storing)?

hth
--
jb

(reply address in rot13, unscramble first)

Varun Kacholia wrote:[color=blue]
> I would like to find out the memory footprint of a vector<T>.
> I tried to dig in the STL code and if I understand correctly, its 3 *
> void(*) + sizeof(T) * size_of_vector.[/color]

Essentially, '3 * sizeof(T*) + v.capacity() * sizeof(T)' is essentially
the minimum storage requirement. There may be an additional word for
the allocator which can be optimized away for the standard allocator
but might require additional memory for other allocators.

The memory footprint for 'std::set<T>' or 'std::tr1::unordered_set<T>'
will be bigger per object and probably also per container. For
'std::set<T>' the computation is probably something like
'3 * sizeof(Node*) + s.size() * (sizeof(T) + 3 * sizeof(Node*) +
sizeof(void*))'. This is effectively a pointer to the tree root, the
left most and the right most tree nodes for the container. For each
object, a node stores the object plus pointers to the left and right
subtree and some representation of the relative balance e.g. colors
"red" and "black" or some integer value. This effectively ends up to
be the size of a pointer due to padding. An additional pointer would
point to the parent of the node although this is not really
necessary to meet the standard's performance requirements but would
impede iteration. Depending on the allocator, an extra word per
object might be necessary to contain the size of the memory block but
this can be relatively easily avoided and be traded for something like
one word for 'block / sizeof(Node)' elements.

For 'std::tr1::unordered_set<T>' things become even more unclear: the
hashing strategies can be rather different and there are various
trade-offs with respect to object allocation and conflicts. This will
affect both the container size and the per object size. I would
expect that in general the overhead is a little bit smaller than that
of the 'std::set<T>' but substantially bigger than that of
'std::vector<T>'.

What is your actual problem, BTW?
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
<http://www.eai-systems.com> - Efficient Artificial Intelligence

> What is your actual problem, BTW?

Trying to optimize the memory usage by comparing the consumption of
different containers.

jb: sizeof(vector<T>) wont work as STL containers allocate some memory
on
the heap too.

Varun Kacholia wrote:[color=blue][color=green]
>> What is your actual problem, BTW?[/color]
>
> Trying to optimize the memory usage by comparing the consumption of
> different containers.
>
> jb: sizeof(vector<T>) wont work as STL containers allocate some memory
> on
> the heap too.[/color]

vector has the smallest requirement per element of any of the containers.

If vector suits your needs, then use that.

If not, then what are your requirements?

Ben Pope
--
I'm not just a number. To many, I'm known as a string...

Ben,
I understand that vector has the smallest requirement per element.
However I
was interested in finding out how much memory does it exactly require
per
element (since I am curious to find the exact numbers, and also I need
to compare
them with some alternate containers--similar to vector-- that we have)

Varun Kacholia <kacholia@gmail.com> wrote:
[color=blue]
> jb: sizeof(vector<T>) wont work as STL containers allocate some memory
> on
> the heap too.[/color]

Yes, I assumed you would add the size of the actual elements as you
did in your original post.

You are right tho, for other containers, this is admittingly not as
simple. I did not think about those when answering.

regards
--
jb

(reply address in rot13, unscramble first)

In article <1142710389.176310.5100@v46g2000cwv.googlegroups.c om>,
"Varun Kacholia" <kacholia@gmail.com> wrote:
[color=blue]
> Apologies if this has been answered somewhere, but Google did not
> produce any concrete
> results. I would like to find out the memory footprint of a vector<T>.
>
> I tried to dig in the STL code and if I understand correctly, its 3 *
> void(*) +
> sizeof(T) * size_of_vector. (3 ptrs for __M_start, __M_finish and
> __M_end_of_storage).
> If any STL guru could confirm my findings, that would be much
> appreciated.
> Also, if someone could throw in the memory numbers for STL hashmap and
> set,
> that would be great!
>
> Thanks.[/color]

The area of a vector (the total number of bytes it occupies) is sizeof(
vector<T> ) + sizeof(T) * vec.capacity(). Understand though, there is no
requirement for vector to reduce its area when elements are removed from
it.

--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.

Varun Kacholia wrote:[color=blue]
> Ben, I understand that vector has the smallest requirement per
> element. However I was interested in finding out how much memory does
> it exactly require per element (since I am curious to find the exact
> numbers, and also I need to compare them with some alternate
> containers--similar to vector-- that we have)[/color]

I'm pretty sure sure the element size of:
std::vector<T>
is
sizeof(T)

In just about every implementation (probably all), the underlying data
structure is an array of T.

Ben Pope
--
I'm not just a number. To many, I'm known as a string...

Daniel, Thanks! That does sound fair enough. Any pointers as to going
about
measuring the memory footprint of STL map<X,Y>?

Ben Pope wrote:
[color=blue]
> Varun Kacholia wrote:[color=green]
>> Ben, I understand that vector has the smallest requirement per
>> element. However I was interested in finding out how much memory does
>> it exactly require per element (since I am curious to find the exact
>> numbers, and also I need to compare them with some alternate
>> containers--similar to vector-- that we have)[/color]
>
> I'm pretty sure sure the element size of:
> std::vector<T>
> is
> sizeof(T)[/color]

However, the size of the allocated memory may be quite a bit larger. When
push_back() decides to reallocate, it usually gets a block that is larger
than required (often twice as large), so it doesn't need to reallocate each
time. Another thing is that vectors don't shrink, so if you remove a lot of
elements, the amount of allocated memory won't be reduced.

In article <1142815737.202005.61770@i39g2000cwa.googlegroups. com>,
"Varun Kacholia" <kacholia@gmail.com> wrote:
[color=blue]
> Daniel, Thanks! That does sound fair enough. Any pointers as to going
> about
> measuring the memory footprint of STL map<X,Y>?[/color]

std::map doesn't have a proscribed implementation like std::vector does.
However all standard containers have a complexity guarantee in this
regard... sizeof( container ) + (K + sizeof( element ) ) *
container.size();

What you are asking for is the value of K in the above equation. I
suggest you ask the company that implemented the STL that you are using.

--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.

Varun Kacholia wrote:[color=blue]
> Daniel, Thanks! That does sound fair enough. Any pointers as to going
> about
> measuring the memory footprint of STL map<X,Y>?
>[/color]

One way to do this is to use an allocator that reports all of its
allocations and deallocations. Try this one:

http://www.josuttis.com/libbook/memory/myalloc.hpp.html

Mark