-
June 19th, 2018, 04:28 PM
#1
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.
-
June 19th, 2018, 08:25 PM
#2
Re: Memory map of stl map
-
June 20th, 2018, 01:43 AM
#3
Re: Memory map of stl map
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.
Last edited by wolle; June 20th, 2018 at 01:48 AM.
-
June 21st, 2018, 05:52 AM
#4
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
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|