Efficient way to iterate over each key exactly once in unordered_multimap

Question

I have a std::unordered_multimap and I want to iterate over each key exactly once.

What I'm currently doing is copying all keys into a std::set. This seems rather inefficient to me and I'm wondering if there is a smarter way of doing this. If it were a std::multiset I would use the std::multiset::upper_bound() member to access the next key, but this member is obviously not available in the unordered version.

I have found a few somewhat related questions and answers but they seem outdated/overcomplicated for my purpose.

So is there a good way of iterating through the different keys? I'm still learning so pointing me in the right direction would also be very much appreciated! Thanks.

Answer 1

[...] elements with equivalent keys are adjacent to each other in the iteration order of the container.

Source, or you can consider that this is guaranteed by the existence of equal_range. Note that "equivalent" is under KeyEqual i.e. it means == if the default std::equal_to<Key> is specified.

So iteration by element, skipping elements with equal keys, will work:

for (auto it = c.begin(); it != c.end(); ) {
    auto const& key = it->first;
    std::cout << key << std::endl;
    while (++it != c.end() && it->first == key) // or c.key_eq()
        ;
}