How is a STL map allocated? Stack or Heap?

Question

I would like to know if the STL map in c++ has contiguous memory - or is the memory assigned to the heap?

Solution

Since map is a dynamic container, the memory for its elements is dynamically allocated (whatever that means (it depends on a configurable allocator)!).

Moreover, map is a node-based container, so each element goes into a distinct, separate allocation (so as to permit maximal iterator and reference non-invalidation). Elements are almost certainly not contiguous in memory, and probably scattered about in a way that reflects how you added them.

Practically, a map will be implemented as some type of balanced tree in order to achieve logarithmic lookup, insertion and deletion times.

(If you want a data structure with contiguous storage and logarithmic lookup time, consider a sorted vector.)