is there an iterator across unique keys in a std::multimap?

Solution 1:

You can use upper_bound to increment the iterator position instead of ++:

#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;
}

This results in:

1 a
2 peacock
3 angel

Solution 2:

Using upper_bound would result in an easy-to-read loop but each call will perform a binary tree search, resulting in an O(n log n) instead of O(n) traversal. If the difference in efficiency matters, you can structure your traversal like this:

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);
}