这个问题类似于this问题，但是我需要在unordered_map（hashMap）而不是地图中找到它。由于unordered_map中的元素显然是无序的，因此我无法使用类似问题中提到的逻辑。
那么，是否有某种方法（顺序迭代除外）来找出unordered_map中的最大密钥？也就是说，最好是在O(1)或O(logN)中而不是O(n)中？
谢谢！
最佳答案
不，就其本质而言，无序地图无法轻易提供其最大值，因此，如果您只有无序地图，则必须按顺序搜索。
但是，没有什么可以阻止您提供自己的类，该类是从（或包含）无序映射派生的，并为其添加了功能。在伪代码中，包含类可能类似于：
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++ - 在C++中的unordered_map中查找最大键，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45179398/