How to find and count different duplicates in a container

[Leo Alves]

Hi guys. I've been reading about ways of finding duplicates in a container, but I still lost of how to solve my problem which is how can I count the different number of duplicates in a vector<int> container.

Let's imagine I have the following container: { 1, 1, 1, 3, 3, 3, 3, 8, 8 ... } How can I count and if possible, put the count result in a variable? for example a = 3 (because of three 1's), b = 4, c = 2.

Thank you for the help.

[MiiNiPaa]

What exactly you want to do? Maintaing a relation like "this sequence contains 3 1's, 4 3's and 2 8's"? Something else?
Is your sequence always sorted? Can you change your sequence?

[Leo Alves]

Yes, the sequence is always sorted. I need to know how many of each duplicates exist in a container, thats all, because I'll use this information (the quantity of each number) after. I don't need to change anything in the container.

[MiiNiPaa]

Using vectors and algorithms:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <utility>
#include <vector>

int main()
{
    std::vector<int> data {1, 1, 1, 3, 3, 3, 3, 8, 8};
    std::vector<int> unique;
    //http://en.cppreference.com/w/cpp/algorithm/unique_copy
    std::unique_copy(data.begin(), data.end(), std::back_inserter(unique));

    std::vector<std::pair<int, int>> frequency;
    for(int i: unique)
        //http://en.cppreference.com/w/cpp/algorithm/count
        frequency.emplace_back(i, std::count(data.begin(), data.end(), i));

    for(const auto& e: frequency)
        std::cout << "Element " << e.first << " encountered " << e.second << " times\n";
}

http://coliru.stacked-crooked.com/a/febe9e3fc832bd30

Using map:

#include <iostream>
#include <map>
#include <vector>

int main()
{
    std::vector<int> data {1, 1, 1, 3, 3, 3, 3, 8, 8};
    std::map<int, int> frequency;
    for(int i: data)
        ++frequency[i];
    for(const auto& e: frequency)
        std::cout << "Element " << e.first << " encountered " << e.second << " times\n";
}

http://coliru.stacked-crooked.com/a/c4153b0b631edde2

[Leo Alves]

First of all, thank you very much for this help. I understood almost everything on your code, except this part:

for(const auto& e: frequency)
        std::cout << "Element " << e.first << " encountered " << e.second << " times\n";

What if I have, 500 different ints? e.first and e.second will show all of then? or just two of then? And how can I access the information of how many times each number exists? (i.e.: Element 1 encounter 3 times)

[MiiNiPaa]

This is a range-for loop.
On each iteration e is assigned a value from container.
That value ib both cases is std::pair: a structure which contains two values named first and second.
In both cases this pair denotes a frequency entry: first member says which number and second says how many times it is encountered.

So, this loop will show all possible unique elements and their frequency.

[Leo Alves]

Oh, I get it now. Thank you. Just one more question, for-ranged loops are not allowed in C++98. Can I change this to:

for (int i = 0; int < frequency.size(); i++) 
                std::cout << "Element " << e.first << " encountered " << e.second << " times\n";

?

[MiiNiPaa]

YOu can for vector-based program, but you will need to properly address elements through index.

For map one, you will need to use iterator-based approach (I would recommend it for vector one too)

for (std::map<int, int>::const_iterator it = frequency.begin(); it != frequency.end(); ++it) 
    std::cout << "Element " << it->first << " encountered " << it->second << " times\n";

[keskiverto]

Do you mean the vector based or the map-based iteration?
http://www.cplusplus.com/reference/vector/vector/begin/
http://www.cplusplus.com/reference/map/map/begin/

Or the array dereferencing style with the vector?
http://www.cplusplus.com/reference/vector/vector/operator%5B%5D/

(The vector documentation examples do not have a vector of pairs, but mere vector of ints. Adapt.)

[Leo Alves]

I have a vector based vector. I created this vector using the .push_back() function. So, I have a 1D array vector (with ints), And I can use the array deference style to access its elements, right? Now, I need to know how many times each element is repeated.

[keskiverto]

MiiNiPaa's vector-based example has std::vector<std::pair<int, int>> frequency;
Therefore, printing the pairs:

for (std::vector<std::pair<int, int>>::const_iterator it = frequency.begin(); it != frequency.end(); ++it) 
    std::cout << "Element " << it->first << " encountered " << it->second << " times\n";

[Leo Alves]

But how can I assign values of a vector<int> to a vector<std::pair<int, int>> ?

[keskiverto]

Look again at MiiNiPaa's "Using vectors and algorithms" program.

It does use C++11 vector::emplace_back(), but you can use C++98 vector::push_back().
With both those methods I do recommend adding
frequency.reserve( unique.size() );
before the counting-loop. That avoids unnecessary reallocations.

[Leo Alves]

I get it now. Thank you MiiNiPaa and keskiverto for the help and for taking my doubts off.