插入然後按不同條件排序的最有效的數據結構

我想知道從文本中讀取不同詞和做頻率表的最佳數據結構是什麼，通過減少出現次數排序。插入然後按不同條件排序的最有效的數據結構

我的想法是使用結構：

struct info { 
    string word; 
    int num; 
};

有這個想法我不知道我應該用什麼：向量，集合，列表...？我有兩個向量的實現：

1）使矢量未排序，並有一個單詞的線性搜索，如果單詞不在矢量，我在最後添加元素。我讀完了我按照頻率降低排列矢量的單詞。

2）對矢量進行排序並使用dicotomic搜索，將元素添加到其相應的位置或添加1到num（如果是）。然後我通過降低頻率對矢量進行排序。

您怎麼看，做這種練習的最好方法是什麼？

來源

2016-05-08 KooPad

你可以使用'std :: map '來計算特定的單詞。 –

我認爲我必須使用2種排序：首先使用字母順序，然後按頻率排序。 – KooPad

std::map<std::string, unsigned int> dictionary; 

//where words is a list, vector of your words, replace this with reading from your text file word by word 
for(const auto& word : words) 
{ 
    dictionary[word]++; 
} 

//now the dictionary has your words in alphabetical order and the frequency (number of occurrences) 
std::multimap<int, std::string> histogram; 
for(const auto& elem : dictionary) 
{ 
    histogram.insert(std::make_pair(elem.second(), elem.first())); 
} 

//print the histogram 
for(const auto& elem : histogram) 
{ 
    cout << elem.first() << " : " << elem.second() << endl; 
}

來源

2016-05-08 09:47:14 T33C

正如在評論中提到的（對不起，太難輸入信用），您可以使用std::map。一個maps元素被排序，並且節省了「手工」操作的額外工作量。如果你需要兩種不同的排序方式，你可以使用兩張地圖或其他容器，然後排序兩次。例如。與一個向量：

#include <string> 
#include <vector> 
#include <algorithm> 

struct info { 
    std::string word; 
    int num; 
}; 

bool sortViaNum(const info& a,const info& b) { return a.num > b.num; } 
bool sortViaWord(const info& a,const info& b) { return a.word > b.word; } 

int main() { 

    std::vector<info> vect; 
    // fill the vector 
    std::sort(vect.begin(),vect.end(),sortViaNum); 
    std::sort(vect.begin(),vect.end(),sortViaWord); 
    return 0; 
}

來源

2016-05-08 10:08:47 user463035818

插入然後按不同條件排序的最有效的數據結構

回答

相關問題