Memory map of stl map

Hello,

I want to know how the stl map is stored in memory (helpful if you answer with a diagram) ?

Also the complexity of finding or inserting the node .

Please help me with your inputs ?

thanks

How did you answer?

Quote:

---

Originally Posted by pdk5

how the stl map is stored ?
Also the complexity of finding or inserting the node .

---

The C++ standard states that the elements of an std::map are ordered (sorted) on key, and that accesses are logarithmic (O(log N)) in complexity.

The general data structure that best fits that requirement is the tree so although the standard doesn't say a tree must be used it's the most likely choice. Some even claim the tree used in most std::map implementations is the so called Red–black tree.

So std::map is ordered and logarithmic but to know exactly how this is accomplished one must ask those behind each concrete implementation.

Also interesting to know is that C++17 exposes more functionality to give you access to nodes in the data structure, though as Wolle said, the standard does mandate it to be a tree.
This is an interesting article: http://en.cppreference.com/w/cpp/container/node_handle