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

Question

Is there a simple or standard way to have a multimap iterator which iterate across unique keys in a multimap?

i.e. for a set that looks like: {1, "a"}, {1, "lemon"}, {2, "peacock"}, {3, "angel"} an iterator which would start at {1, "a"} then incrementing would point to {2, "peacock"} and then incrementing again would point to {3, "angel"}?

Answer 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

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

Answer 3

As noted in the selected answer, repeated use of multimap::upper_bound leads to an O(n log n) traversal of the map. Using the external upper_bound function gives you O(n). However, you need to ensure you only compare the key of the map:

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...

}

The underlying approach is essentially the same as user3701170's solution - i.e linear search - but we put the increment step in the for statement proper, not the loop's body. Aside from putting the increment where it "usually" lives, this also means any continue statements in the loop will behave as expected.

Answer 4

Runnable example

This is a slight improvement over https://stackoverflow.com/a/24212648/895245 with a runnable unit test:

#include <cassert>
#include <map>
#include <vector>

int main() {

    // For testing.
    auto m = std::multimap<int, int>{
        {1, 2},
        {1, 3},
        {2, 4}
    };
    std::vector<int> out;

    // The algorithm.
    auto it = m.begin();
    auto end = m.end();
    while (it != end) {
        auto key = it->first;

        // Do what you want to do with the keys.
        out.push_back(key);

        do {
            if (++it == end)
                break;
        } while (it->first == key);
    }

    // Assert it worked.
    assert(out == std::vector<int>({1, 2}));
}

Answer 5

if you have to pass over all unique keys quickly then you can use std::map instead;

typedef std::map< KeyType, std::list< ValueType > > MapKeyToMultiValue;

Insertion would be more difficult, However you can iterate over all keys without having to bother with duplicate entries. Insertion would look as follows:

void insert_m(MapKeyToMultiValue &map, const KeyType key, const ValueType value )
{
  auto it = map.find( key );
  if (it == map.end())
  {
     std::list<ValueType> empty;
     std::pair< MapKeyToMultiValue::iterator, bool > ret =
        map.insert( MapKeyToMultiValue::value_type( key, empty ) );
     it = ret.first;
  }

  it->second.push_back( value );
}

or you can make that very templated:

template<typename KeyType, typename ValueType, 
     typename MapType = std::map< KeyType, std::list< ValueType > > >
void insert_multi( MapType &map, const KeyType key, const ValueType value )
{

  auto it = map.find( key );
  if (it == map.end())
  {
     std::list<ValueType> empty;
     std::pair< typename MapType::iterator, bool > ret =
        map.insert( typename MapType::value_type( key, empty ) );
     it = ret.first;
  }

  it->second.push_back( value );
}

The full test program looks as follows:

#include <map>
#include <list>
#include <string>
#include <stdio.h>

typedef std::string KeyType;  
typedef int ValueType;

typedef std::map< KeyType, std::list< ValueType > >  MapKeyToMultiValue;

void insert_m(MapKeyToMultiValue &map, const KeyType key, const ValueType value )
{
  auto it = map.find( key );
  if (it == map.end())
  {
     std::list<ValueType> empty;
     std::pair< MapKeyToMultiValue::iterator, bool > ret =
        map.insert( MapKeyToMultiValue::value_type( key, empty ) );
     it = ret.first;
  }

  it->second.push_back( value );
}


template<typename KeyType, typename ValueType, 
   typename MapType = std::map< KeyType, std::list< ValueType > > >
void insert_multi( MapType &map, const KeyType key, const ValueType value )
{

  auto it = map.find( key );
  if (it == map.end())
  {
     std::list<ValueType> empty;
     std::pair< typename MapType::iterator, bool > ret =
        map.insert( typename MapType::value_type( key, empty ) );
     it = ret.first;
  }

  it->second.push_back( value );
}


int main()
{
    MapKeyToMultiValue map;


    insert_m(map, std::string("aaa"), 1 );
    insert_m(map, std::string("aaa"), 2 );
    insert_m(map, std::string("bb"), 3 );
    insert_m(map, std::string("cc"), 4 );


    insert_multi(map, std::string("ddd"), 1 );
    insert_multi(map, std::string("ddd"), 2 );
    insert_multi(map, std::string("ee"), 3 );
    insert_multi(map, std::string("ff"), 4 );


    for(auto i = map.begin(); i != map.end(); ++i)
    {
      printf("%s\n", i->first.c_str() );
    }


    return 0;
}