在 C++ 中查找 unordered_map 中的最大键

Question

此问题与 this 问题相似，但我需要在 unordered_map (hashMap) 而不是地图中找到它。由于 unordered_map 中的元素显然是无序的，所以我不能使用类似问题中提到的逻辑。

那么，有什么方法（顺序迭代除外）可以找出 unordered_map 中的最大键值吗？也就是说，最好在 O(1) 或 O(logN) 而不是 O(n)?

谢谢！

Answer 1

不，就其本质而言，无序地图无法轻易提供其最大值，因此，如果您只有无序地图，则必须按顺序搜索。

但是，没有什么可以阻止您提供您的 自己的 class，它源自（或包含）无序映射并向其添加功能。在伪代码中，包含 class 的内容可能类似于：

class my_int_map:
    unordered_int_map m_map;  # Actual underlying map.
    int m_maxVal = 0;         # Max value (if m_count > 0).
    bool m_count = 0;         # Count of items with max value.

    int getMaxVal():
        # No max value if map is empty (throws, but you
        # could return some sentinel value like MININT).

        if m_map.size() == 0:
            throw no_max_value

        # If max value unknown, work it out.

        if m_count == 0:
            m_maxVal = m_map[0]
            m_count = 0
            for each item in m_map:
                if item > m_maxVal:
                    m_maxVal = item
                    m_count = 1
                else if item == m_maxVal:
                    m_count++

        return m_maxVal

    addVal(int n):
        # Add it to real map first.

        m_map.add(n)

        # If it's only one in map, it's obviously the max.

        if m_map.size() == 1:
            m_maxVal = n
            m_count = 1
            return

        # If it's equal to current max, increment count.

        if m_count > 0 and n == m_maxVal:
            m_count++
            return

        # If it's greater than current max, fix that.

        if m_count > 0 and n > m_maxVal:
            m_maxVal = n
            m_count = 1

    delIndex(int index):
        # If we're deleting a largest value, we just decrement
        # the count, but only down to zero.

        if m_count > 0 and m_map[index] == m_maxVal:
            m_count--
        m_map.del(index)

这是对某些集合的标准优化，因为它提供了一些属性的惰性评估，同时仍然缓存它以提高速度。

只有当您删除当前具有最高价值的最后一项时，O(n) 搜索才会发生。

所有其他操作（获取最大值、添加、删除不是最终最大项时）以 O(1) 成本更新最大值。

在 C++ 中查找 unordered_map 中的最大键

Finding max key in an unordered_map in c++

c++

unordered-map

hashmap