CODEWITHSUNDEEP
c++c++17unordered-map
patyx
patyx

Reputation: 329

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

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

Upvotes: 2

Views: 13562

Answers (2)

Dr Phil
Dr Phil

Reputation: 880

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)

Upvotes: 0

Alecto
Alecto

Reputation: 10740

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.

Upvotes: 6

Related Questions