Iterate over all elements with key k in a std::unordered_multimap in O(count(k))

Question

I have a std::unordered_multimap, and would like to iterate over all elements with a given key k, without iterating the full map, but optimally traversing only the matching items.

While I can do this with upper_bound in an ordered std::multimap, I can nowhere find the specification that find() followed by forward iteration until the key differs, will traverse all occurences of key k, since find(k) is only guaranteed to return an arbitrary item with key k

Edit : I know that in my specific case, I can use a std::unordered_map<Key, std::vector> instead, and it will match all my needs. The question is more out of curiosity.

Or am I missing something?

My source is: https://en.cppreference.com/w/cpp/container/unordered_multimap/find

Answer 1

The example from cppreference for unordered_map::equal_range:

#include <iostream>
#include <unordered_map>
 
int main()
{  
    std::unordered_multimap<int,char> map = {{1,'a'},{1,'b'},{1,'d'},{2,'b'}};
    auto range = map.equal_range(1);
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->first << ' ' << it->second << '\n';
    }
}

Output:

1 a
1 b
1 d

Complexity is

Average case linear in the number of elements with the key key, worst case linear in the size of the container.

Note that the complexity is to get the iterators. Once you got them, the loop is the desired O(count(k)).