Get distinct vector of vector with count

Question

What is the best way to return only the unique element with the counts from vector of vectors?

std::vector<std::vector<string>> vec_vec{{a,a,b,c},{a,c,c}};

The results should be :

{a, b, c} // This is the vector that contains the unique items.
{3, 1, 3} //a exists three times, b only one time, and c is three times.

To solve this I use the following:

1- Copy all the items in the vector of vector to single vector, so the output will be:

vec_vec{{a,a,b,c},{a,c,c}} -> vec{a,a,b,c,a,c,c} 

2- Now I'm dealing with a single vector (not vector of vector), so it's much easier to sort, get the unique items and them (I may use the code here1 and here2)

Is converting the vector of vector to one vector is a good idea? Any better solution?

Can we find better way with less complexity comparing with the current way (c++11, c++14)?

Answer 1

From the top of my mind:

std::unordered_map<std::string, std::size_t> counters;
for(auto const& inner : vec_vec)
  for(auto const& v : inner)
    counters[v]++;

for(auto const& cnt : counters)
  std::cout << cnt.first << " appears " << cnt.second << std::endl;

Answer 2

Use hash maps.

std::unordered_map<string, int> result;
for (const auto& x : vec_vec) 
  for (const string& y : x)
     result[y]++;

Answer 3

I would just use a map as "tally" structure:

std::map<string, unsigned int> tally;
for(auto subvector : vector) {  // subvector is std::vector<std::string>
  for(auto item : subvector) {  // item is a std::string
    ++tally[item];
  }
}

If you insist on having the result as two parallel vectors (but why would you?) simply construct them from the map:

std::vector<std::string> unique_items;
unique_items.reserve(tally.size());
std::vector<unsigned int> counts;
counts.reserve(tally.size());
for(auto item : tally) {
  unique_items.push_back(item.first);
  counts.push_back(item.second);
}

If you don't want the result vector to be sorted, you can use an unordered_map, as suggested in other answers.