13｜單字計數

還沒完成只限 C++CPU 時間上限 1 秒

題目說明

只限 C++｜CPU 時間上限 1 秒

題目

讀入一篇英文文章，統計每個單字出現了幾次，然後依照出現次數由多到少列出來；次數相同的，依照單字由小到大（字典順序）排列。

這裡的「單字」定義得很簡單：連續的英文字母（A–Z、a–z）就是一個單字，其他任何字元（空格、換行、數字、標點符號、撇號……）都是分隔。例如：

文字	拆出來的單字
`didn't`	`didn`、`t`
`R2D2`	`r`、`d`
`C-3PO`	`c`、`po`
`hello,world!`	`hello`、`world`

比較時不分大小寫：The、THE、the 都算同一個單字，輸出時一律用小寫。

這一題要練習 C++ 的 std::map（「單字 → 次數」的對照表）、把資料搬到 std::vector 再用 std::sort 搭配自己寫的 lambda 比較規則排序，以及用結構化綁定取出 pair 的兩個部分。用 C 做的話，光是「用字串找到對應的計數器」就要自己寫搜尋或雜湊表，排序也要另外寫一個 qsort 用的比較函式。

輸入

一篇文章，一直讀到輸入結束 (EOF)，總共最多 200 KB（204800 個字元）。
只會出現可印出的 ASCII 字元（英文、數字、符號、空格）、Tab 和換行。
檔案最後不一定有換行。也可能整篇文章裡一個英文字母都沒有。

輸出

每個不同的單字輸出一行，格式是 單字次數（中間一個空格），單字全部用小寫。

排列順序：

次數多的在前面。
次數相同時，單字依照字典順序由小到大（就是 std::string 的 <，例如 a < ab < abc < b）。

如果文章裡沒有任何單字，就什麼都不輸出。

範例

輸入：

The cat and the hat.
THE CAT sat; the hat didn't.
R2D2 and C-3PO

輸出：

the 4
and 2
cat 2
hat 2
c 1
d 1
didn 1
po 1
r 1
sat 1
t 1

The、the、THE 合計 4 次；and、cat、hat 都是 2 次，所以照字母順序排。didn't 拆成 didn 和 t，R2D2 拆成 r 和 d，C-3PO 拆成 c 和 po。

複習重點

C++：

std::map<std::string, int> count; 加上 ++count[w];：[] 遇到還沒有的 key 會自動新增一筆、值從 0 開始。map 裡的資料永遠依照 key 由小到大排好
（另一個選擇是 std::unordered_map，用雜湊表，通常比較快，但裡面的資料沒有順序）
std::vector<std::pair<std::string, int>> items(count.begin(), count.end());：用 map 的內容直接建立 vector
lambda：[](const auto& a, const auto& b) { return ...; } 是寫在呼叫處的小函式，傳給 std::sort 當比較規則，回傳「a 是否應該排在 b 前面」
結構化綁定 (C++17)：for (const auto& [w, n] : items)，直接把 pair 的 first、second 取名成 w、n
std::isalpha、std::tolower（在 <cctype>）：判斷英文字母、轉小寫。參數要先轉成 unsigned char

對照 C：

C 沒有內建的對照表，要自己寫「在字串陣列裡找這個單字，找不到就新增」，或自己實作雜湊表
比較字串要用 strcmp，複製字串要用 strcpy，還要自己確認陣列夠大；C++ 的 std::string 可以直接用 <、==、+=
qsort 的比較函式不能寫在呼叫的地方，要另外定義一個接收 const void* 的函式

提示 1：怎麼把文章拆成單字？

一個字元一個字元讀，用一個 std::string word 收集目前的單字：

讀到英文字母：轉成小寫，加到 word 後面
讀到其他字元：如果 word 不是空的，代表一個單字剛結束，把它記錄下來，然後清空 word

char c;
while (std::cin.get(c)) {   // get 會讀到空格和換行；cin >> c 會跳過它們
    // ...
}

注意：讀完之後 word 可能還留著最後一個單字（文章最後一個字元是字母時），別忘了也要記錄。

在終端機手動測試時，按 Ctrl+Z 再按 Enter 代表輸入結束。

提示 2：怎麼依照次數排序？

map 只能依照 key（單字）排序，沒辦法依照 value（次數）排。做法是把內容複製到 vector 裡，再用 std::sort 並給它一個比較規則：

std::vector<std::pair<std::string, int>> items(count.begin(), count.end());
std::sort(items.begin(), items.end(), [](const auto& a, const auto& b) {
    // a.first 是單字，a.second 是次數
    // 回傳 true 表示 a 應該排在 b 前面
});

提示 3：比較規則怎麼寫？

先比次數：次數不同時，次數大的排前面，所以回傳 a.second > b.second。次數相同時再比單字：回傳 a.first < b.first。

另一種想法：map 本來就已經依照單字排好了，所以只要用 std::stable_sort（排序時「相等的元素保持原本的先後順序」）只依照次數排，同次數的單字自然維持字母順序。