-3

In this map example:

std::map<int, int> m; 
for (int i = 0; i < 1000; i++) 
    m[2*i] = i;
for (i = 0; i < 1000; i++)   // just an example of filling a map
    m[2*i + 1] = i;

how to know how the internal "red-black tree" will look like?

Which nodes will be a child of which other nodes?

Understanding this (visually) in such a simple example, would allow me to grasp better how the red-black tree map implementation work.

I read many answers such as Why is std::map implemented as a red-black tree? about implementation of std::map as a red-black tree, but it didn't help. I also read Red–black tree, but again, a simple example in the case of a map would help to understand how it works.

Basj
  • 41,386
  • 99
  • 383
  • 673
  • 2
    What is your question? Do you want to know how the standard specifies `std::map`? Do you want to know how red-black trees work? Note either question is ill-fitted for SO. – Passer By Jul 30 '17 at 10:53
  • @PasserBy I want to know, with some C++ code, which node will be child of other nodes in the example given here (more precisely, in the underlying tree of the std::map structure). – Basj Jul 30 '17 at 11:13

1 Answers1

1

You cannot know without digging into the internals of your vendor's std::map implementation. For instance, on vendor make std::map<int use tries rather than red-black trees.

The standard allows many different choices, and vendors do not agree on some single best choice.

jbapple
  • 3,297
  • 1
  • 24
  • 38
  • I understand it's implementation-dependent, but isn't there a way to analyse *what has been done* by looking at the bytes near address `&m`? – Basj Jul 30 '17 at 17:22
  • @Basj, Whether one can determine such a thing depends on the implementation. If you want to test it out, you might have success by running your programming in a debugger and stepping into the methods on `std::map`. – jbapple Jul 30 '17 at 17:24