c++ - 插入的最有效数据结构，然后按不同条件排序

Question

我想知道从文本中读取不同单词并制作频率表(按出现次数递减排序)的最佳数据结构是什么。

我的想法是使用结构:

struct info {
    string word;
    int num;
};

考虑到这一点，我想知道我应该使用什么: vector 、集合、列表...？ 我有两个 vector 实现:

1) 对 vector 进行排序并对单词进行线性搜索，如果单词不在 vector 中，我会在末尾添加元素。当我读完单词时，我按频率递减对 vector 进行排序。

2) 对 vector 进行排序并使用双分搜索，将元素添加到其相应的位置，如果是，则将 num 添加 1。然后我通过降低频率对 vector 进行排序。

你怎么看，做这种运动最好的方法是什么？

Answer 1

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;
}