CODEWITHSUNDEEP
c++vectorstl
Fabia Bushra Tamanna
Fabia Bushra Tamanna

Reputation: 11

C++ vector counting each element's occurance

I have a vector of type vector<unsigned> and I want to find out how many times each element occurred in this vector.

This vector could be pretty large, so looping through it wouldn't be a good idea I guess.

What would be the most efficient way to do that?

Upvotes: 1

Views: 7051

Answers (3)

Hon Wi Cong
Hon Wi Cong

Reputation: 141

In case you don't understand how map and unordered_map work. Here is my stupid method to do it. The benefit of this method is it allows us to sort the element ascendingly and descending by only changing the *min_element and *max_element.

#include <vector>
#include <iostream>
#include <algorithm>

int main(){
    int min, count;
    std::vector<int> numList = {1, 2, 2, 3, 1, 2, 3, 3, 4, 5, 6, 6};

    while (!(numList.empty())){
        min = *min_element(numList.begin(), numList.end());
        count = std::count(numList.begin(), numList.end(), min);
        std::cout << min << " has occurred " << count << " times" << std::endl;
        numList.erase(std::remove(numList.begin(), numList.end(), min), numList.end());
    }
}

Here is the output:

1 has occurred 2 times
2 has occurred 3 times
3 has occurred 3 times
4 has occurred 1 times
5 has occurred 1 times
6 has occurred 2 times

Upvotes: 1

vital teresa
vital teresa

Reputation: 1

You could use std::count.

Simple to use:

std::count(vect.begin(), vect.end(), 3);

Upvotes: 0

Jerry Coffin
Jerry Coffin

Reputation: 490108

Unless the vector is already sorted (or at least grouped so identical elements are all together), looking at every item in the vector is unavoidable (and even if it is sorted, unless you expect a lot of duplicates, chances are pretty good that looking at every item will be the preferred method anyway)1.

One obvious method would be to walk through the vector, and count element with a std::unordered_map:

std::unordered_map<unsigned, size_t> counts;
for (auto v : your_vector)
    ++counts[v];

Then you can (for example) print out the values:

for (auto const &p : counts)
    std::cout << "The value: " << p.first << " occurred " << p.second << "times\n";
  1. If you do (expect to) have lots of duplicates, and the items are ordered, you can use a binary search to find the end of the run of the current value. The theoretical break-even point for this is if the average number of duplicates of a given value is equal to the base 2 logarithm of the overall size, so if the number of duplicates is greater than that, a binary search will require fewer comparisons. A modern CPU gains enough from a predictable, linear access pattern that you'd probably need substantially more duplicates of each value (on average) for a binary search to be a win though.

Upvotes: 6

Related Questions