Memory map of stl map

[wolle]

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.