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

Question

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

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

谢谢!

Answer 1

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

但是，没有什么可以阻止您提供您的自己的 类，该类派生自(或包含)无序映射并向其添加功能。在伪代码中，包含类可能是这样的:

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)仅当您删除当前具有最高值(value)的最后一项时，才会进行搜索。

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