是否存在跨std :: multimap中唯一键的迭代器？

Question

是否有一种简单或标准的方法来使用多图迭代器迭代多图中的唯一键？

即对于一个看起来像的集合:{1, "a"}, {1, "lemon"}, {2, "peacock"}, {3, "angel"} 一个迭代器,它会在{1, "a"}然后开始递增,指向{2, "peacock"}然后再次递增会指向{3, "angel"}？

Answer 1

您可以使用upper_bound增加迭代器位置而不是++:

#include <map>
#include <string>
#include <iostream>

using namespace std;

int main()
{
  multimap<int,string> mm;
  mm.insert(make_pair(1, "a"));
  mm.insert(make_pair(1, "lemon"));
  mm.insert(make_pair(2, "peacock"));
  mm.insert(make_pair(3, "angel"));

  for( auto it = mm.begin(), end = mm.end();
       it != end;
       it = mm.upper_bound(it->first)
  )
    cout << it->first << ' ' << it->second << endl;
  return 0;
}

这导致:

1 a
2 peacock
3 angel

Answer 2

使用upper_bound将导致易于读取的循环,但每次调用将执行二叉树搜索,从而导致O(n log n)而不是O(n)遍历.如果效率差异很重要,您可以像这样构建遍历:

typedef std::multimap<std::string, int> MapType;
MapType container;
for (MapType::iterator it = container.begin(); it != container.end(); ) {
  std::string key = it->first;

  doSomething(key);

  // Advance to next non-duplicate entry.
  do {
    ++it;
  } while (it != container.end() && key == it->first);
}

Answer 3

如所选答案中所述，重复使用multimap::upper_bound会导致 O(n log n) 遍历地图。使用外部upper_bound函数为您提供 O(n)。但是，您需要确保只比较地图的键：

std::multimap<int, std::string> myMap = ... ;
const auto compareFirst = [](const std::pair<const int, std::string>& lhs, const std::pair<const int, std::string>& rhs) {
    return lhs.first < rhs.first;
};

for(auto it = myMap.begin(); it != myMap.end(); it = std::upper_bound(it, myMap.end(), *it, compareFirst)) {
    // Do stuff...

}

底层方法本质上与 user3701170 的解决方案相同 - 即线性搜索 - 但我们将增量步骤放在for适当的语句中，而不是循环的主体中。除了将增量放在它“通常”所在的位置之外，这也意味着continue循环中的任何语句都将按预期运行。