How iterating on std::map returns sorted elements based on the key value

Question

The container std::map is a data structure that STL provides. In almost all compilers it is implemented as a R&B tree with guaranteed log(n) insertion, find and removal time.

In a red and black tree the elements are sorted based on the "less" operator of the stored element. So basically if a root is N + 1 , N will be on the left sub-tree while N + 2 will be on the right sub-tree and this ordering will be decided by the less operator.

My question is when executing the below code:

  std::map<char,int> testMap;

  testMap['a']=10;
  testMap['b']=30;
  testMap['g']=50;
  testMap['d']=70;
  testMap['h']=23;
  testMap['f']=44;
  testMap['c']=100;
  testMap['e']=10;

  typedef std::map<char, int>::iterator it_type;
  for(it_type iterator = testMap.begin(); iterator != testMap.end(); iterator++) {
      std::cout << iterator->first << std::endl;
  }

This is the output of the code: a b c d e f g h

The elements are returned in a sorted order based on the key value. How can this be possible considering the fact that the underlying data structure is a red and black tree? How c++ iterates from the leftmost sub-tree to rightmost sub-tree is it a doubly linked r&b tree?

Answer 1

Broadly speaking, there are two ways to iterate through the contents of a tree: breadth first and depth first. Breadth first looks at all the elements at one level before going down to the next level. Depth first goes down one branch of the tree to it's leaf, then comes up and back down to the next leaf, etc. For a tree that represents sorted data, depth first can give you the data in sorted order, and that's what map iterators do, because it's most useful.