如何在C++中查找最大值地圖

我的數據結構類中的老師給了我們一個任務來閱讀一本書並計算出有多少單詞。那不是全部;我們需要顯示100個最常用的單詞。我的直覺說要對地圖進行排序，但我只需要地圖中的100個單詞。谷歌搜索後，有沒有一個「教科書答案」排序地圖的價值，而不是關鍵？如何在C++中查找最大值地圖

'std :: map'的鍵已經排序。如果不是，你會被詛咒的。另外，如果你冗餘地存儲單詞，我認爲'std :: multiset'對於你的問題是一個更好的容器。 –

可能的重複[優雅的方法來計算文件中的單詞頻率]（http://stackoverflow.com/questions/4888879/elegant-ways-to-count-the-frequency-of-words-in-a-文件） – jogojapan

@MarkGarcia我理解這個問題的方式是，按照頻率對單詞進行排序（以確定100個最常見單詞）。一個'std :: map'（其中的單詞是鍵）不會隱含地這樣做。 – jogojapan

我懷疑是否有「教科書答案」，答案是否定的：您無法按值分類地圖。

您可以隨時使用這些值創建另一個map。但是，這不是最有效的解決方案。我認爲更好的方法是讓你將這些值填入priority_queue，然後彈出第一個100。

請注意，您不需要將單詞存儲在第二個數據結構中。您可以存儲指向該單詞的指針或引用，甚至可以存儲map::iterator。

現在，您可以考慮另一種方法。這就是在您製作第一張地圖時，保持前100名候選人的順序。這樣就沒有必要做第二遍了，並且建立一個額外的結構，正如你所指出的那樣，它是浪費的。

爲了有效地做到這一點，您可能會使用類似堆的方法，並在更新值時進行冒泡操作。由於這個詞只會增加，所以這會很好地適合這個堆。但是，您的手上會有維修問題。那就是：如何引用堆中某個值的位置，並跟蹤掉落的值。

2013-07-02 03:01:07 paddy

回答