Counting occurences in a vector

Question

This program reads strings of numbers from a txt file, converts them to integers, stores them in a vector, and then tries to output them in an organized fashion like so....

If txt file says:

7 5 5 7 3 117 5

The program outputs:

3
5   3
7   2
117

so if the number occurs more than once it outputs how many times that happens. Here is the code so far.

Solved: Final code:

#include "std_lib_facilities.h"

void print_numbers(const vector<int>& num)
{
 int counter = 1;
 for(int i = 0; i < num.size(); ++i)
 {
   if(i<num.size()-1 && num[i] == num[i+1]) ++counter;

   else if(i<num.size()-1 && num[i]!=num[i+1])
   {
        if(counter > 1)
        {
          cout << num[i] << '\t' << counter << endl;
          counter = 1;
        }
        else cout << num[i] << endl;
   }

   else if(i == num.size()-1)
   {
        if(counter >1) cout << num[i] << '\t' << counter << endl;
        else cout << num[i] << endl;
   }
  }
}



int str_to_int(string& s)
{
    stringstream ss(s);
    int num;
    ss >> num;
    return num;
}

int main()
{
    cout << "Enter file name.\n";
    string file;
    cin >> file;
    ifstream f(file.c_str(), ios::in);

    string num;
    vector<int> numbers;
    while(f>>num)
    {
        int number = str_to_int(num);
        numbers.push_back(number);
    }

    sort(numbers.begin(), numbers.end());
    print_numbers(numbers);

    keep_window_open();
}

Answer 1

How about using a map, where the key is the number you're tracking and the value is the number of occurrences?

If you must use a vector, you've already got it sorted. So just keep track of the number you previously saw. If it is the same as the current number, increment the counter. Every time the number changes: print out the current number and the count, reset the count, set the last_seen number to the new number.

Answer 2

This program reads strings of numbers from a txt file, converts them to integers, stores them in a vector, and then tries to output them in an organized fashion like so....(emphasis added)

What is the point of this storage step? If you are reading the numbers from a file, then you already have them in order, ready to be processed (counted) one at time, as you encounter them.

However, I would need a way for it to know when it sees a new number.

I advise you to have a look at std::set or std::map. I expect either of these containers would do what you're looking for.

Answer 3

You could use a map of numbers to counters:

typedef map<int,unsigned int> CounterMap;
CounterMap counts;
for (int i = 0; i < numbers.size(); ++i)
{
   CounterMap::iterator i(counts.find(numbers[i]));
   if (i != counts.end()){
      i->second++;
   } else {
      counts[numbers[i]] = 1;
   }
}

... then iterate over the map to print results.

EDIT: As suggested by lazypython: if you have the TR1 extensions [wikipedia.org] available, unordered_map should have better performance...

typedef std::tr1::unordered_map<int,unsigned int> CounterMap;
CounterMap counts;
for (int i = 0; i < numbers.size(); ++i)
{
   CounterMap::iterator i(counts.find(numbers[i]));
   if (i != counts.end()){
      i->second++;
   } else {
      counts[numbers[i]] = 1;
   }
}

Answer 4

Std::count() fits the bill nicely.

std::vector<int>::const_iterator cur = numbers.begin();
std::vector<int>::const_iterator last = numbers.end();
while (cur != last) {
    unsigned cnt = std::count(cur, last, *cur);
    std::cout << *cur;
    if (cnt != 1) {
        std::cout << " " << c;
    }
    std::cout << std::endl;
    int saved = *cur;
    while (*cur == saved) {
        ++cur;
    }
}

Of course there are a bunch of other algorithms out there that will do the same job. Play with things like std::equal_range() in conjunction with std::distance() will do the job just as nicely.

Answer 5

Using a map is the practical solution. What you should do is to solve this problem :)

This is called frequency counter. So, you have a sorted vector and all what you have to do is to count successive equal numbers. In other words, you have to check each number with its successor.

for(size_t i = 0; i < numbers.size(); i++)
{
    size_t count = 1;

    size_t limit = numbers.size() - 1;
    while(i < limit  && numbers[i] == numbers[i+1])
    {
     count++;
     i++;
    }

    std::cout << numbers[i] << "\t" << count << std::endl;
}

Answer 6

That was fun:

#include <map>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iterator>

struct IncrementMap
{
    IncrementMap(std::map<int,int>& m): m_map(m)    {}
        void operator()(int val) const
    {
        ++m_map[val];
    }
    std::map<int,int>& m_map;
};
struct SpecialPrint
{
    SpecialPrint(std::ostream& s):  m_str(s)    {}
    void operator()(std::map<int,int>::value_type const& value) const
    {
        m_str << value.first;
        if (value.second != 1)
        {
            m_str << "\t" << value.second;
        }
        m_str << "\n";
    }
    std::ostream&   m_str;
};
int main()
{
    std::fstream        x("Plop");
    std::map<int,int>   data;

    std::for_each(  std::istream_iterator<int>(x),
                     std::istream_iterator<int>(),
                     IncrementMap(data)
                );
    std::for_each(  data.begin(),
                    data.end(),
                    SpecialPrint(std::cout)
                );
}