c++ - 以相反的顺序搜索多图

Question

有没有一种方法可以在对数复杂度中以相反的顺序搜索多图（C/C++ STL）？

Answer 1

你的问题可以用两种方式解释。如果你的意思是你用相同的键插入了一堆元素，并且你想用那个键找到最后插入的元素，那么你可以尝试equal_range(key)，它返回一对迭代器（一个指向第一个元素，其他最后一个）。但是我不知道是否multimap对存储具有相同键的元素的顺序提供任何保证。

或者，如果您的意思是要以multimap相反的顺序遍历，您可以使用rbegin()andrend()获取反向迭代器。

Answer 2

我很确定，因为 amultimap基本上是一个树表示，唯一的搜索机制是遍历树 - 没有“向前”和“向后”。

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

你能更详细地了解你需要什么吗？

Answer 3

您可以像往常一样使用upper_boundand但反转您的迭代代码。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;
  }
}

Answer 4

我猜您正在寻找一种搜索算法来定位 a 中的键std::multimap，即

1. 保证在一个键中O(log n)找到任何键multimapn

2. 保证O(1)找到最大的密钥multimap

没有内置这样的东西。大多数（全部？）多图都实现为平衡树，并且首先调用multimap::find()测试图的中间，因为那是树的根所在的位置。如果您实施嘈杂的operator<.

rbegin()在调用之前简单地测试指向的键是否multimap::find()满足您的要求？

如果“最后插入”实际上是指最近添加到地图中的元素，则根本无法找到它，multimap并且其他关联容器不会保留有关插入顺序的信息。