Grade 12 · Data structures and the STLCitește în română

set and map: word frequency

Original: set și map — frecvența cuvintelor

O(n log n)C++1746 lines1 example

The idea

We read words (lowercase letters) until the end of the input. A set<string> keeps every word once, in alphabetical order, so size() gives the number of distinct words. A map<string, int> associates a counter with every word: frecventa[cuvant]++ creates the entry with 0 if it did not exist and then increments it. Both are balanced trees: insertion and lookup cost O(log n) string comparisons, and iteration returns them in increasing order of the keys.

Original description (Romanian)

Citim cuvinte (litere mici) până la sfârșitul datelor. Un set<string> păstrează fiecare cuvânt o singură dată, în ordine alfabetică, deci size() dă numărul de cuvinte distincte. Un map<string, int> asociază fiecărui cuvânt un contor: frecventa[cuvant]++ creează intrarea cu 0 dacă nu exista și apoi o crește. Ambele sunt arbori echilibrați: inserarea și căutarea costă O(log n) comparații de șiruri, iar parcurgerea le dă în ordine crescătoare a cheilor.

Complexity
O(n log n) word comparisons, n = the number of words
Grade
Grade 12 (Clasa a XII-a)

Examples

Example 1

Input

ana are mere ana are pere
mere ana

Expected output

4
ana 3
are 2
mere 2
pere 1

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

set-si-map-frecventa-cuvintelor.cpp
/*
 * Titlu: set și map — frecvența cuvintelor
 * Clasa: 12
 * Capitol: Structuri de date și STL
 * Descriere: Citim cuvinte (litere mici) până la sfârșitul datelor. Un set<string>
 *            păstrează fiecare cuvânt o singură dată, în ordine alfabetică, deci
 *            size() dă numărul de cuvinte distincte. Un map<string, int> asociază
 *            fiecărui cuvânt un contor: frecventa[cuvant]++ creează intrarea cu 0
 *            dacă nu exista și apoi o crește. Ambele sunt arbori echilibrați:
 *            inserarea și căutarea costă O(log n) comparații de șiruri, iar
 *            parcurgerea le dă în ordine crescătoare a cheilor.
 * Complexitate: O(n log n) comparații de cuvinte, n = numărul de cuvinte
 *
 * Exemplu
 * Intrare:
 * ana are mere ana are pere
 * mere ana
 * Ieșire:
 * 4
 * ana 3
 * are 2
 * mere 2
 * pere 1
 */
#include <iostream>
#include <map>
#include <set>
#include <string>
using namespace std;

int main()
{
    set<string> distincte;
    map<string, int> frecventa;
    string cuvant;
    while (cin >> cuvant)
    {
        distincte.insert(cuvant);
        frecventa[cuvant]++;
    }
    cout << distincte.size() << '\n';
    for (auto &p : frecventa)
        cout << p.first << ' ' << p.second << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.