# [ACCEPTED]-is there an iterator across unique keys in a std::multimap?-multimap

Score: 51

You can use `upper_bound` to increment the iterator position 1 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
``````
Score: 32

Using `upper_bound` would result in an easy-to-read loop 4 but each call will perform a binary tree 3 search, resulting in an O(n log n) instead of O(n) traversal. If 2 the difference in efficiency matters, you 1 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);
}
``````
Score: 5

As noted in the selected answer, repeated 11 use of `multimap::upper_bound` leads to an O(n log n) traversal 10 of the map. Using the external `upper_bound` function 9 gives you O(n). However, you need to ensure 8 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 7 underlying approach is essentially the same 6 as user3701170's solution - i.e linear search 5 - but we put the increment step in the `for` statement 4 proper, not the loop's body. Aside from 3 putting the increment where it "usually" lives, this 2 also means any `continue` statements in the loop will 1 behave as expected.

Score: 2

Runnable example

This is a slight improvement over https://stackoverflow.com/a/24212648/895245 with 1 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}));
}
``````
Score: 1

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

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

Insertion 6 would be more difficult, However you can 5 iterate over all keys without having to 4 bother with duplicate entries. Insertion 3 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 2 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 1 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;
}
``````
Score: 0

Try `equal_range`:

http://en.cppreference.com/w/cpp/container/multimap/equal_range

That must be an exact match.

0

More Related questions