CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums
Results 1 to 4 of 4
  1. #1
    Join Date
    May 2015

    Memory map of stl map


    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 ?

    Last edited by pdk5; June 20th, 2018 at 01:19 AM.

  2. #2
    Arjay's Avatar
    Arjay is offline Moderator / EX MS MVP Power Poster
    Join Date
    Aug 2004

    Re: Memory map of stl map

    How did you answer?

  3. #3
    Join Date
    Feb 2017

    Re: Memory map of stl map

    Quote Originally Posted by pdk5 View Post
    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.
    Last edited by wolle; June 20th, 2018 at 01:48 AM.

  4. #4
    Join Date
    Nov 2003

    Re: Memory map of stl map

    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:
    Marc Gregoire - NuonSoft (
    My Blog
    Wallpaper Cycler

    Author of Professional C++, 4th Edition by Wiley/Wrox (includes C++17 features)
    ISBN: 978-1-119-42130-6
    [ ]

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts

Click Here to Expand Forum to Full Width