有效的方法来查找std :: vector中每个唯一值的频率

Question

给定一个向量std::vector<double> v,我们可以有效地找到独特的元素:

std::vector<double> uv(v.begin(), v.end());
std::sort(uv.begin(), uv.end());
std::erase(std::unique(uv.begin, uv.end()), uv.end());

用最好的方法(没有循环,使用STL或lambdas)创建一个向量:

std::vector<double> freq_uv(uv.size());

其中包含出现的每个不同元素的频率v(与排序的唯一值的顺序相同)？

注意:类型可以是任何东西,而不仅仅是 double

Answer 1

排序后,在删除之前:

std::vector<int> freq_uv;
freq_uv.push_back(0);
auto prev = uv[0];        // you should ensure !uv.empty() if previous code did not already ensure it.
for (auto const & x : uv)
{
    if (prev != x)
    {
        freq_uv.push_back(0);
        prev = x;
    }
    ++freq_uv.back();
}

请注意,虽然我通常喜欢使用地图计算出现次数,但正如Yakk所做的那样,在这种情况下,我认为它正在做很多不必要的工作,因为我们已经知道向量已经排序.

另一种可能性是使用std::map(非无序),而不是排序.这将首先获得您的频率.然后,由于地图是有序的,您可以直接从地图创建已排序的唯一向量和频率向量.

// uv not yet created
std::map<T, int> freq_map;
for (auto const & x : v)
    ++freq_map[x];
std::vector<T> uv;
std::vector<int> freq_uv;
for (auto const & p : freq_map)
{
    uv.push_back(p.first);
    freq_uv.push_back(p.second);
}