First, std::map
is particularly inefficent with regards to
memory use. Each value you insert will be placed in a separate
node, which in addition to the value, typically contains three
pointers and some additional information (2 char
in the MS
implementation). In addition, each node is typically allocated
separately, so the extra overhead needed by the allocator must
be added. On a 32 bit system, the total overhead will be at
least 20 bytes; on a 64 bit system, 40.
As for std::vector
(which underlies your std::stack
), it is
much, much better, but if you don't use reserve
to
pre-allocate, it will reallocate from time to time, usually
multiplying the capacity by 1.5 or 2. Which means that it may
end up occupying a lot more memory than necessary. (Also,
depending on the patterns of allocation, the system may not be
able to effectively reuse the memory freed during
a reallocation.)
Still, it's often preferrable to use an std::vector, kept in
order using std::lower_bound
, instead of an std::map
.
Finally, if you know in advance exactly how many entries the
vector will have, or can establish some reasonable upper bound,
you can use reserve
to pre-allocate. This avoids any risk of
doubling the size.