c++ - c++学习map入口的顺序

Question

如果我有一个带有键作为字符串的地图。我怎么知道哪个字符串在地图的哪个位置？例如，“cats”是第一个条目，“dogs”是第二个条目。我怎么知道狗是地图中的第二个条目？我应该浏览地图并搜索/检查订单还是有更简单的方法？

Answer 1

您可以find()元素，然后计算distance元素和地图之间的begin(). 由于这是 a map，因此复杂度distance将O(n)与地图中元素的数量有关。我怀疑与简单地循环地图和计数相比，你会看到很多性能改进，但我宁愿不编写这样的手写循环。

但这闻起来像XY 问题。为什么需要地图中元素的位置？

Answer 2

无论如何，你不能做得更好，这里有两个原因：

a) std::map 里面有一棵树，所以最初树的叶子没有线性顺序，只有部分顺序（当然你可以比较两个键，但是对于一般的二叉树你不能这样做 -这就是复杂化的原因）。

b) std::map 有双向迭代器，所以你不能有有效的迭代器算术。你可以这样做：

typedef map<string, int> MyMapT;
MyMapT data;
// ...
auto it = data.find("dog");
if (it == data.end()) {
  // don't have such a key
}
auto position = distance(data.begin(), data.end());

不幸的是，这不是最好的方法，因为对于双向迭代器，距离函数在 O(n) 时间内工作。同样，这是因为 std::map 内的树结构。