c++ - 使用 STL Map 查找对中第一个元素的最低 key 对

Question

我有一个 map ，它的键是一对 std::map<std::pair<int, int>, struct A> myMap .我如何找到并访问该对中每个唯一的第一个元素的最低对？例如，

struct A a;
myMap.insert(std::make_pair(std::pair<int, int>(1, 200), a));
myMap.insert(std::make_pair(std::pair<int, int>(1, 202), a));
myMap.insert(std::make_pair(std::pair<int, int>(2, 198), a));
myMap.insert(std::make_pair(std::pair<int, int>(2, 207), a));

我想使用的键是 <1, 200> 和 <2, 198>。我不需要它们一起返回，我只需要对每个进行操作。

感谢您的宝贵时间!

Answer 1

我会选择最直接的解决方案:

auto previous_first = 0;
auto is_first_iteration = true;
for (const auto& key_value : myMap) {
  const auto& key = key_value.first;
  const auto& value = key_value.second;
  if (is_first_iteration || key.first != previous_first) {
    is_first_iteration = false;
    previous_first = key.first;
    // do something here!
  }
}

这里你只是简单地遍历每个元素(我们依赖于 std::map 元素被排序的属性。并且对按第一个元素排序，然后按第二个元素排序)。在每一步中，我们都会记住之前的第一个元素 - 如果在这一步中它是相同的，我们就跳过这一步。

@AndrewDurward 指出这个问题可以在对数时间内解决。这只是部分正确。首先，这个问题只有在最好的情况下才能在对数时间内解决。如果您有 N 个元素并且每个元素都有不同的 first 怎么办？你的答案中有 N 个元素，显然你不能在对数时间内输出 N 个元素。