快速'分组/计数'std :: vector <std :: u16string>到std :: map <u16string,int>

Question

我有一个函数可以将~10000个单词读入一个向量,然后我想将所有单词分组到一个地图中以"计算"某个单词出现的次数.

虽然代码"有效"但有时需要2秒才能重新构建地图.

NB:不幸的是,我不能改变'读'功能,我必须使用矢量std::u16string.

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

如何在跟踪单词出现在向量中的次数的同时加快"分组"的速度？

Answer 1

如果您调用std::map::operator[]新密钥,则密钥的值将初始化为值(对于POD而言为0 int).因此,您的循环可以简化为:

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

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

如果密钥已经存在,那么它只是递增.

此外,它看起来不像你需要订购地图,所以你可以使用一个std::unordered_map替代,因为插入是平均恒定时间,而不是对数,这将进一步加快它.