How is the STL card distributed? Stack or heap?

Question

I would like to know if the STL map in C ++ has contiguous memory - or memory allocated to the heap?

Answer 1

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

In addition, map is a container node , so each element goes into a separate selection (to allow the maximum iterator and the invalidity of the link). Elements are almost certainly not in contact in memory and are probably scattered, which reflects how you added them.

In practice, the map will be implemented as some type of balanced tree to achieve a logarithmic search, insertion and deletion times.

(If you need a data structure with adjacent storage and logarithmic search time, consider a sorted vector.)

Answer 2

This is more than likely an implementation, and y ou can certainly change the dispenser of any STL container , but this is not for the faint of heart, and you will need to look at the documentation for the standard library that you use.

In any case, the map is usually implemented as a red-black tree , and the tree nodes are on the heap.

(The tree nodes, if I understand correctly, contain instances of value_type , which are the key / value pairs of your map).

Note that the stack is an idea of ​​poor storage for any container, since the stack should be considered a scarce resource.