I am working on an application in which I am planning to use couple of STL containers. The application will take certain steps if memory consumption reaches a threshold. For that purpose I need to perform a close to accurate calculation on how much memory is used by STL containers.
vector<string> StringList
map<string, int> mapstring
This is how I am estimating memory:
For size of StringList
, loop over all the elements of the vector and keep adding the string sizes.
string size = sizeof(string) + string.capacity()*sizeof(char)
Then finally add to this sizeof(StringList);
For size of mapstring, loop over all the keys of the container and keep adding the string sizes and then add the sizes of int which is mapstring.size()*sizeof(int)
. Then finally add to this sizeof(mapstring);
I guess a better approach would be specifying own allocator class and keeping track of memory usage inside it but writing one could be non-trivial. Does this estimation look good ?
So there is no surprise regarding std::vector. It uses 4 bytes to store each 4 byte elements. It is very efficient. However, both std::set and std::unordered_set use nearly an order of magnitude more memory than would be strictly necessary.
As addressed in the comments by Kamil, a std::vector keeps track of three pointers internally. One pointer to the begin, one to end and one to the end of allocated memory (see stack post). Now, the size of a pointer should be 8 bytes on any 64-bit C/C++ compiler so, 3 * 8 bytes = 24 bytes (see wiki).
In C++, there are generally 3 kinds of STL containers: Sequential Containers. Associative Containers. Unordered Associative Containers.
For std::vector
and std::string
, capacity, rather than size, would
be a better approximation. For node based containers (std::set
,
etc.), you'd want multiply the number of nodes (roughly the number of
elements) times the size of each node. This only accurate, however, if
the allocator doesn't use an optimized pool allocator for the nodes.
If you really want to know how much memory is being used, however, a
better strategy would be to replace the global operator new
and
operator delete
, and keep track of the actual allocations. Even more
accurate would be to replace malloc
and free
. Formally, this is not
allowed, but in practice, I've never encountered an implementation where
it doesn't work. On the other hand, if you replace malloc
and free
,
you have to implement the actual memory management yourself. If you
replace operator new
and operator delete
, you can use malloc
and
free
, which makes it fairly trivial.
Note too that each allocation has some fixed overhead. A 100000 allocations of 10 bytes each will consume significantly more memory than 10 allocations of 100000 bytes each.
A std::vector<element>
typically takes 3 machine words in total + sizeof(element) * capacity()
of memory. For typical implementations, the overhead consist of pointers to the beginning, end and current size of the vector. The elements themselves are stored in contiguous memory. capacity()
typically has room for up to twice the actual number of elements.
A std::map<element, int>
typically takes about 2 machine words in total + 3 machine words per element + [ sizeof(element) +sizeof(int) ] * num_elements of memory. For typical implementations, the overhead consists of pointers to the stored elements. The elements themselves are stored in a binary tree, with pointers to its parent and two children.
With these rules of thumb, all you need to know is the average number of characters per string and the total number of strings to know total memory consumption.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With