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

Question

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

4

这个问题与这个问题类似，但我需要在unordered_map（hashMap）中查找它，而不是在map中查找。由于unordered_map中的元素显然是无序的，因此我无法使用类似问题中提到的逻辑。那么，有没有一些方法（除了顺序迭代）可以找出unordered_map中的最大键？也就是说，最好是以O(1)或O(logN)而不是O(n)的时间复杂度解决。谢谢！

- user8305079

4

简短回答：没有。 - Sam Varshavchik

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- paxdiablo · Answer 1

不，按其本质，无序映射无法轻松地提供其最大值，所以如果你只有无序映射，你将不得不顺序搜索。

然而，并没有阻止你提供自己的类，该类可以派生自（或包含）无序映射并添加功能。伪代码中，一个包含类可能如下所示：

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)的代价更新最大值。