C++计数映射

Question

C++计数映射

c++dictionarycounting

7

最近我遇到了一个非常普遍的问题，主要可以归结为以下内容：

给定一段长文本，计算文本中每个单词出现的频率。

我使用了std::unordered_map解决了这个问题。然而，这样做相当丑陋，因为对于文本中的每个单词，如果已经遇到过，我必须执行查找、删除，然后重新插入到地图中并增加值。

我意识到还有其他方法可以解决这个问题，比如在普通数组/向量上使用哈希函数并增加值，但我想知道是否有更优雅的方法来解决这个问题，例如具有类似于Python Counter Collections的接口的STL组件或函数。

我知道C++作为C++，我不能总是指望高级概念为我实现，但我只是想知道你们是否知道任何东西（或者至少你们的Google技巧比我强），可以使我的代码更好一些。

- Tomasz Kaminski

为什么不使用std::unordered_multiset<std::string>或std::unordered_map<std::string, int>？ - user1804599

实际上我正在使用一个unordered_map。抱歉，打错字了 :( - Tomasz Kaminski

2个回答

-1

另一种解决方案：

std::multiset<std::string> m;
for (auto w: words) m.insert(w);

m.count("some word");

优点是您不必依赖于使用operator[]的“技巧”，使代码更易读。

编辑：正如Kerrek在评论中指出的那样，这种解决方案速度较慢。multiset存储您插入的所有元素，即使它们被认为是相等的（它们仍然可能在某些方面上有所不同，而operator==没有检查）。与unordered_map<std::string, int>相比，这会导致显着的开销，后者只需要存储每个单词一次。

（顺便说一句，在我的机器上使用map解决方案处理威廉·莎士比亚的全部作品大约需要0.33秒，而使用multiset解决方案则需要0.78秒。）

- Evert Heylen

1

这是一个非常可怕的解决方案 :-( - Kerrek SB

@KerrekSB为什么？如果您搜索multisets的实现，许多人都会使用映射到int，所以这基本上是相同的东西，只是稍微更高级一些。(例子: https://groups.google.com/forum/#!msg/golang-nuts/NBXJ6tAWj48/uzp5nFqjnZAJ ) - Evert Heylen

想象一下，你想要在从网络流入的数千兆字节的文本中计算单词的直方图... - Kerrek SB

@KerrekSB：你说得对，我对这两种解决方案进行了基准测试，这个方案有相当大的开销。我已将细节添加到我的答案中。 - Evert Heylen

为什么要踩我？我解释了一种替代方案，虽然性能较差，但仍为遇到相同问题的人提供了一些额外信息，说明为什么这个解决方案不太好（尽管多重集合（在数学上看）基本上是为这样的用例而设计的，只是C++的版本不太适合）。 - Evert Heylen

multiset 在这里确实不是正确的工具。它会为每个字符串的每个出现次数保留一份副本，这是非常不必要的。你只需要存储每个字符串的计数，而不是每个字符串。 - Andreas Haferburg

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jerry Coffin · Accepted Answer

我不太确定为什么一个 std::unordered_map（或只是 std::map）会涉及很多复杂性。我会这样编写代码：

我不确定为什么std::unordered_map（或者只是std::map）会涉及太多复杂性。我的代码将会像下面这样：

std::unordered_map<std::string, int> words;

std::string word;
while (word = getword(input))
   ++words[word];

不需要任何形式的查找/删除/重新插入。

如果不清楚为什么以及如何工作：operator[]会在地图中还不存在指定键时创建条目，相关值将是指定类型的值初始化对象，如果是int（或类似），则该值将为零。然后我们每次遇到该单词时都会对其进行递增。