Exercise 7-1

Extend the program from S7.2/124 to produce its output sorted by occurrence count. That is, the output should group all the words that occur once, followed by those that occur twice, and so on.

Solution

The strategy:

1. Start with the program from S7.2/124. i.e. The main program in Solution to Exercise 7-0 (Part 1 / 3).
2. Have a new (associative array) map<int, vector<string> > wordsByFreq to map int (word occurring frequency) to vector<string> (all the words at that occurring frequency). The key of this map is essentially the int frequency. In other words, this map is by default sort by the int frequency (as it is the key to this map).
3. We populate the map<string, int> counters as usual. Once it is fully populated, we use it to populate our wordsByFreq.
4. Once the wordsByFreq is fully populated, we use it to display all the words grouped by frequency.

The Program

The program is surprisingly easy to write / extend. As long as we know what a map is and how it works, this program should be fairly easy to understand.

#include <iostream>   // std::cin, std::cout, std::endl
#include <map>        // std::map
#include <string>     // std::string
#include <vector>     // std::vector

using std::cin;
using std::cout;
using std::endl;
using std::map;
using std::string;
using std::vector;

int main()
{
  string s;
  map<string, int> counters;                // Store each word and an
                                            // associated counter
  map<int, vector<string> > wordsByFreq;    // Store all the words for
                                            // each frequency

  // read the input, keeping track of each word and how often we see it
  while (cin >> s)
    ++counters[s];

  cout << "\nDisplay words and associating frequency." << endl;
  // write the words and associated counts
  for (map<string, int>::const_iterator i = counters.begin();
       i != counters.end(); ++i) {
    cout << i->first << "\t" << i->second << endl;

    // Obtain words by frequency
    wordsByFreq[i->second].push_back(i->first);
  }

  // Display words by frequency
  cout << "\nDisplay words grouped by frequency." << endl;
  for (map<int, vector<string> >::const_iterator i = wordsByFreq.begin();
       i != wordsByFreq.end(); ++i) {
    cout << "\nFrequency: " << i->first << endl;

    for (vector<string>::const_iterator j = i->second.begin();
         j != i->second.end(); ++j)
      cout << *j << endl;

  }

  return 0;
}

Test Program

I am going to submit the same set of test input as per the word counting program of Solution to Exercise 7-0 (Part 1 / 3). The result looks correct.

apple orange banana
orange orange
apple banana
mango
^Z

Display words and associating frequency.
apple   2
banana  2
mango   1
orange  3

Display words grouped by frequency.

Frequency: 1
mango

Frequency: 2
apple
banana

Frequency: 3
orange

Reference