c++ - 将 'group by/count' std::vector 快速转换为 std::map

Question

我有一个函数可以将大约 10000 个单词读入一个 vector ，然后我想将所有单词分组到一个映射中以“计算”某个单词出现的次数。

虽然代码“有效”，但有时可能需要 2 秒才能重新构建 map 。

注意:不幸的是，我无法更改“读取”功能，我必须使用 std::u16string 的 vector 。

std::vector<std::u16string> vValues;
vValues.push_back( ... )
...

std::map<std::u16string, int> mValues;
for( auto it = vValues.begin(); it != vValues.end(); ++it )
{
  if( mValues.find( *it ) == mValues.end() )
  {
    mValues[*it] = 1;
  }
  else
  {
    ++mValues[*it];
  }
}

如何在跟踪单词在 vector 中出现的次数的同时加快“分组依据”？

Answer 1

如果您调用 std::map::operator[]在新键上，键的值将被值初始化(对于像 int 这样的 POD，初始化为 0)。因此，您的循环可以简化为:

for (auto it = vValues.begin(); it != vValues.end(); ++it)
    ++mValues[*it];

如果没有键*it，则默认值为0，但随后立即递增，变为1.

如果键已经存在，那么它只是递增。

此外，看起来您不需要对 map 进行排序，因此您可以使用 std::unordered_map 代替，因为插入是平均常数时间，而不是对数，这将进一步加快速度。