以相反的顺序搜索多地图

Question

有没有一种方法可以在对数复杂度中以逆序搜索multimap (C/C++ STL)？

Answer 1

你的问题可以有两种解释。如果您的意思是已经插入了一组具有相同键的元素，并且希望找到具有该键的最后插入的元素，那么可以尝试使用equal_range(key)，它返回一对迭代器(一个指向第一个元素，另一个指向最后一个元素)。但是，我不知道multimap是否保证了具有相同键的元素的存储顺序。

ALternatively，如果你想以相反的顺序遍历multimap，你可以使用rbegin()和rend()来获得反向迭代器。

Answer 2

我非常确定，由于multimap基本上是一个树表示，唯一的搜索机制是遍历树-没有“向前”和“向后”。

您可以使用lower_bound查找第一个匹配的元素，使用upper_bound查找最后一个匹配的元素，或者使用equal_range查找与键匹配的整个范围。编辑:所有这些方法都以对数复杂度运行。

你能更详细地说一下你需要什么吗？

Answer 3

你可以像平常一样使用upper_bound和lower_bound，但是颠倒你的迭代代码。

使用以下命令找到最后一个匹配的元素：

ub = m.upper_bound(1);
lb = m.lower_bound(1);
if (ub != lb) {
  --ub;
  return ub->second;
}

或者只需要一次查找：

ub = m.upper_bound(1);
if (ub != m.begin()) {
  --ub;
  if (ub->first == 1) {
    return ub->second;
  }
}