以有效的方式找到std :: vector中每个唯一值的频率 [英] Efficient way to find frequencies of each unique value in the std::vector

问题描述

给定向量 std :: vector< double> v ，我们可以通过以下方式有效地找到唯一元素：

Given a vector std::vector<double> v, we can find unique elements efficiently by:

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创建一个向量：

What would the be the nicest way (without loops, with STL or lambdas) to create a vector:

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

其中包含 v （顺序与排序的唯一值相同）？

which would contain frequencies of each distinct element appearing in v (order the same as sorted unique values)?

注意：type可以是任何值，而不仅仅是 double

Note: type can be anything, not just double

推荐答案

排序后，在您清除之前：

After you sort, before you erase:

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();
}

请注意，虽然我一般喜欢用地图计算发生次数，在这种情况下，我认为它是做了很多不必要的工作，因为我们已经知道向量是排序的。

Note that, while I generally like to count occurences with a map, as Yakk is doing, in this case I think it is doing a lot of unnecessary work as we already know the vector is sorted.

另一种可能是使用 std :: map （不是无序的），而是的排序。这将获得您的频率第一。然后，由于地图是有序的，您可以直接从地图创建排序的，唯一的向量和频率向量。

Another possibility is to use a std::map (not unordered), instead of sorting. This will get your frequencies first. Then, since the map is ordered, you can just create the sorted, unique vector, and the frequency vector directly from the 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);
}

这篇关于以有效的方式找到std :: vector中每个唯一值的频率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！