在C++的unordered_map中查找最大密鑰

Question

這個問題是類似到this問題，但我需要在unordered_map（hashMap）而不是地圖中找到它。由於unordered_map中的元素顯然是無序的，因此我不能使用類似問題中提到的邏輯。

那麼，有沒有一種方法（順序迭代除外）找出unordered_map中的最大密鑰？也就是說，最好在O(1)或O(logN)而不是O(n)？

謝謝！

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)成本。