Efficient way to find frequencies of each unique value in the std::vector

user_2028058 0
Viewed 6219

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

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

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

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

Note: type can be anything, not just double

vector c++11 unique stl c++
4 Answers

An O(n) solution when the range of values is limited, for example chars. Using less than the CPU level 1 cache for the counter leaves room for other values.

(untested code)

constexp int ProblemSize = 256;
using CountArray = std::array<int, ProblemSize>;

CountArray CountUnique(const std::vector<char>& vec) {
  CountArray count;
  for(const auto ch : vec)
    count[ch]++;

  return count;
}
user_40132580
Related