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:
- Start with the program from S7.2/124. i.e. The main program in Solution to Exercise 7-0 (Part 1 / 3).
- 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).
- We populate the map<string, int> counters as usual. Once it is fully populated, we use it to populate our wordsByFreq.
- 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