How do I get the max element of a std::unordered_map?

Question

I know how to retrieve the maximum element of a std::map through the use of std::max_element, but I am unable to achieve the same affect with a std::unordered_map due to the differences between the container types.

How can I find the maximum value in a std::unordered_map and return the corresponding std::pair?

My current method for doing this with a std::map is shown (based on this answer). I can't seem to figure out how to do the same for a std::unordered_map.

template <typename KEY_T, typename VALUE_T>
std::pair<KEY_T, VALUE_T> findMaxValuePair(
    std::map<KEY_T, VALUE_T> const &x)
{
    return *std::max_element(x.begin(), x.end(),
                             [](const std::pair<KEY_T, VALUE_T> &p1,
                                const std::pair<KEY_T, VALUE_T> &p2)
                             {
                                 return p1.second < p2.second;
                             });
}

When I attempt to use the above function on a std::unorderd_map (replacing std::map with std::unordered_map, I receive a Segmentation fault (core dumped).

And what happens when you simply replace `std::map` with `std::unordered_map`, here? — Sam Varshavchik, May 02 '19 at 23:09
@SamVarshavchik a `Segmentation fault (core dumped)` occurs. — patyx, May 02 '19 at 23:12
@paddycakes -- Then you need to post a [mcve]. We have no idea where, when, or how you're calling this function. — PaulMcKenzie, May 02 '19 at 23:13
This must be due to some other unrelated problem with the code; but unfortunately it's not possible to figure out what is the problem with some code that's not shown; but only with code that's shown and meets all requirements of a [mcve], as explained in stackoverflow.com's [help]. — Sam Varshavchik, May 02 '19 at 23:14
@paddycakes Also, in all likelihood, your `std::map` version is hiding the bug. You should be glad `unordered_map` uncovered it. — PaulMcKenzie, May 02 '19 at 23:15

score 6 · Accepted Answer · edited Jul 13 '21 at 22:00

Making the code work for `unordered_map`

In this case, we can actually do it just by changing the type from map to unordered_map.

Before:

template <class Key, class Value>
std::pair<Key, Value> findMaxValuePair(
    std::map<Key, Value> const &x)
{
    return *std::max_element(x.begin(), x.end(),
                             [](const std::pair<Key, Value> &p1,
                                const std::pair<Key, Value> &p2)
                             {
                                 return p1.second < p2.second;
                             });
}

After: we changed the type to unordered_map.

template <class Key, class Value>
std::pair<Key, Value> findMaxValuePair(
    std::unordered_map<Key, Value> const &x)
{
    return *std::max_element(x.begin(), x.end(),
                             [](const std::pair<Key, Value> &p1,
                                const std::pair<Key, Value> &p2)
                             {
                                 return p1.second < p2.second;
                             });
}

Making the code work for both

We can write a function that works with all of the standard containers really simply! This will work for maps, vectors, lists, and pretty much everything else that defines begin(), end(), and value_type!

template <class Container>
auto findMaxValuePair(Container const &x)
    -> typename Container::value_type
{
    using value_t = typename Container::value_type;
    const auto compare = [](value_t const &p1, value_t const &p2)
    {
        return p1.second < p2.second;
    };
    return *std::max_element(x.begin(), x.end(), compare);
}

What about the segmentation fault?

This code may segmentation fault if the map or container is empty, either because you're accessing memory you don't own; because the memory pointed to by map::end() contains garbage that you then try to construct something like a string out of, or because it's represented as a null pointer.

For maps in particular, if there's memory corruption, that could also result in a segmentation fault, although that would be true independent of how you tried iterating through the map.

I'm sure OP has thought of that (which you can read in the question's comment section). — Timo, May 02 '19 at 23:18
The segfault is an issue unrelated to the algorithm used to find the maximum element, but I updated my answer to address the possible reasons — Alecto Irene Perez, May 02 '19 at 23:26
As you suggested. The segfault occured due to the map being empty. A `if(x.size() ==0) return Container::value_type();` check accounted for the issue. — patyx, May 02 '19 at 23:42
@paddy returning a flag value on empty or error is a bad idea. — Yakk - Adam Nevraumont, May 03 '19 at 00:15
@Yakk The flag value is favored over other exception handling as no error is thrown and the entire program should not crash due to an empty container. — patyx, May 06 '19 at 15:35
@paddycakes See `expected` or `optional`. Or, return a non-owning possibly-null pointer to the element. None of these are flag values. — Yakk - Adam Nevraumont, May 06 '19 at 17:16

Dr Phil · Answer 2 · 2021-07-17T12:25:56.033

0

An ordered map , as the name says, is ordered, but by the key. Here you are aiming for the values.

In either case you would need to iterate through the whole map in order to find the maximum value. An ordered map can efficiently find the maximum or minimum keys, but not the values. So a full-scan approach taken will work both for an unordered or ordered maps.

If you need to efficiently find the max values you might consider changing your code to use an ordered set, reverse ordered map (value vs key) or ordered bag (multi-value map for the same key)

edited Jul 17 '21 at 12:25

answered May 02 '19 at 23:15

Dr Phil

833
6
18

What do you mean by *"but the key"*? – Peter Mortensen Jul 13 '21 at 22:03

How do I get the max element of a std::unordered_map?

2 Answers2

Making the code work for unordered_map

Making the code work for both

What about the segmentation fault?

Making the code work for `unordered_map`