c++ - 迭代 std::map 如何返回基于键值的排序元素

Question

容器std::map是STL提供的一种数据结构。在几乎所有的编译器中，它都被实现为一个 R&B 树，保证了 log(n) 的插入、查找和删除时间。

在红黑树中，元素根据存储元素的“less”运算符进行排序。所以基本上如果一个根是 N + 1 ， N 将在左子树上，而 N + 2 将在右子树上，这个顺序将由 less 运算符决定。

我的问题是在执行以下代码时:

  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;
  }

这是代码的输出:一种bCd电子FG

元素以基于键值的排序顺序返回。考虑到底层数据结构是红黑树这一事实，这怎么可能呢？ c++如何从最左边的子树迭代到最右边的子树是双向链接的r&b树吗？

Answer 1

从广义上讲，有两种方法可以遍历树的内容:广度优先和深度优先。在进入下一个级别之前，广度首先查看一个级别的所有元素。深度首先沿着树的一个分支向下到达它的叶子，然后向上返回到下一个叶子，依此类推。对于表示排序数据的树，深度优先可以为您提供排序的数据顺序，这就是 map 迭代器所做的，因为它最有用。