Чтобы посчитать слова, можно использовать unordered_map
, которая более эффективна чем map
, если кол-во слов большое (O(1)
(амортизовано) против O(log n)
для каждого слова).
Если каждая строка содержит ровно одно слово, то подсчитать слова совсем просто:
unordered_map<string, size_t> counter;
string line;
getline(cin, line); // read n and ignore it
while(getline(cin, line)) // count words
++counter[line];
Чтобы напечатать в порядке убывания частоты слов (самые встречаемые слова сначала) можно скопировать частоты в вектор и отсортировать его по частоте:
vector<pair<string,size_t>> v(begin(counter), end(counter));
sort(begin(v), end(v), [](const auto& a, const auto& b) {
return a.second > b.second;
});
for (const auto& p : v)
cout << p.first << " " << p.second << endl;
5
One
Two
Three
One
One
Вывод
One 3
Three 1
Two 1
Если нужно вывести слова в "алфавитном" (лексикографическом) порядке и частота слов небольшая и/или производительность не важна, то можно использовать просто map
без unordered_map
+ sort
:
/** Count words.
One word per line.
Print words in lexicographical order.
To try:
$ g++ -std=c++11 count-words-map.cpp && ./a.out <input
One 3
Three 1
Two 1
*/
#include <iostream>
#include <map>
int main() {
using namespace std;
map<string, size_t> counter;
string line;
getline(cin, line); // read n and ignore it
while(getline(cin, line)) // count words
++counter[line];
if (!cin.eof())
return 1; // I/O error
// print words and their frequencies
for (const auto& p : counter)
cout << p.first << " " << p.second << endl;
}
В данном случае вывод (случайно) получается таким же как и для unordered_map
.