c++ - 不确定使用哪种数据结构

Question

假设我有以下文本:

today was a good day and today was a sunny day. 

我把这个文本分成几行，用空格分隔，这是

Today

was

a

good

等等

现在我使用 vector 数据结构通过 .size() 简单地计算文本中的单词数。完成了。

但是，我还想检查一个词是否出现不止一次，如果出现了多少次。在我的示例中，“今天”出现了 2 次。

我想存储“今天”并附加一个 2/x(取决于它在大文本中出现的频率)。现在，这不仅适用于“今天”，还适用于文本中的每个单词。我想查看一个单词出现的频率，附加一个计数器，然后按降序对它(单词 + 计数器)进行排序(那是另一回事，但是现在不重要)。

我不确定在这里使用哪种数据结构。也许是 map ？但是我不能在 map 上添加计数器。

编辑:这是我到目前为止所做的:http://pastebin.com/JncR4kw9

Answer 1

你应该使用 map 。事实上，你应该使用 unordered_map .

unordered_map<string,int>将为您提供一个哈希表，该表将使用字符串作为键，您可以增加整数以保持计数。

unordered_map具有 O(1) 查找和插入优于 O(logn) 查找和插入 map 的优势.这是因为前者使用数组作为容器，而后者使用树的一些实现(我认为是红黑)。

unordered_map 的唯一缺点就是正如它的名字所提到的，你不能按词法顺序遍历所有元素。从上面对它们结构的解释中应该清楚这一点。但是，您似乎不需要这样的遍历，因此这应该不是问题。

unordered_map<string,int> mymap;
mymap[word]++; // will increment the counter associated with the count of a word.