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

    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
    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
    Posts
    13,490

    Re: Memory map of stl map

    How did you answer?

  3. #3
    Join Date
    Feb 2017
    Posts
    677

    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
    Location
    Belgium
    Posts
    8,150

    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: http://en.cppreference.com/w/cpp/container/node_handle
    Marc Gregoire - NuonSoft (http://www.nuonsoft.com)
    My Blog
    Wallpaper Cycler 3.5.0.97

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

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

Featured