如何获取 std::unordered_map 的最大元素？

Question

我知道如何通过使用 std::max_element 检索 std::map 的最大元素，但由于差异，我无法使用 std::unordered_map 实现相同的效果在容器类型之间。

如何求std::unordered_map和return对应的std::pair中的最大值？

显示了我目前使用 std::map 执行此操作的方法（基于 this answer）。我似乎无法弄清楚如何为 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;
                             });
}

当我尝试在 std::unorderd_map 上使用上述函数时（将 std::map 替换为 std::unordered_map，我收到 Segmentation fault (core dumped).

Answer 1

有序映射，顾名思义，是有序的，但是是通过键来排序的。在这里，您的目标是价值。

无论哪种情况，您都需要遍历整个地图才能找到最大值。有序映射可以有效地找到最大或最小键，但不能找到值。因此，采用全扫描方法对无序或有序地图均适用。

如果您需要有效地找到最大值，您可以考虑更改代码以使用有序集、反向有序映射（值与键）或有序包（同一键的多值映射）

Answer 2

使代码适用于 `unordered_map`

在这种情况下，我们实际上只需将类型从 map 更改为 unordered_map。

之前:

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: 我们将类型更改为 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;
                             });
}

使代码对两者都有效

我们可以非常简单地编写一个适用于所有标准容器的函数！这将适用于地图、矢量、列表以及几乎所有定义 begin()、end() 和 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);
}

segmentation fault呢？

如果地图或容器为空，则此代码可能会出现分段错误，这可能是因为您正在访问不属于您的内存；因为 map::end() 指向的内存包含垃圾，然后您尝试从中构造类似字符串的内容，或者因为它表示为空指针。

特别是对于地图，如果存在内存损坏，也可能会导致分段错误，尽管无论您尝试如何遍历地图都是如此。

如何获取 std::unordered_map 的最大元素？

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

c++

unordered-map

c++17

使代码适用于 `unordered_map`

使代码对两者都有效

segmentation fault呢？

如何获取 std::unordered_map 的最大元素？

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

c++

unordered-map

c++17

使代码适用于 unordered_map

使代码对两者都有效

segmentation fault呢？

使代码适用于 `unordered_map`