崙?zhàn)：從足球積分統(tǒng)計(jì)到通用聚合排序模式)
1. 從一道實(shí)訓(xùn)題看透映射與排序的組合拳這道題我第一次看到的時(shí)候腦子里蹦出來的不是足球而是“這不就是典型的統(tǒng)計(jì)聚合加排序輸出嗎”。題目背景是歐洲冠軍聯(lián)賽給出一堆比賽結(jié)果需要統(tǒng)計(jì)每支球隊(duì)的積分、凈勝球等數(shù)據(jù)最后按規(guī)則排出名次。核心操作就兩件事用映射結(jié)構(gòu)把球隊(duì)和它的統(tǒng)計(jì)數(shù)據(jù)關(guān)聯(lián)起來再把映射里的內(nèi)容轉(zhuǎn)存到順序容器里做排序。聽起來簡單但真動(dòng)手寫的時(shí)候坑比想象中多。為什么這道題值得單獨(dú)拿出來聊因?yàn)樗鼛缀醺采w了日常開發(fā)中最常見的一類需求按某個(gè)維度聚合數(shù)據(jù)再按另一個(gè)維度排序輸出。比如統(tǒng)計(jì)每個(gè)用戶的訂單總額然后按金額排名統(tǒng)計(jì)每個(gè)接口的調(diào)用次數(shù)然后按次數(shù)排序統(tǒng)計(jì)每個(gè)商品的銷量然后按銷量展示。這些場景的本質(zhì)和這道題一模一樣。你把這套“映射聚合加順序排序”的套路吃透了以后遇到類似需求基本就是換個(gè)字段名的事。這篇文章我會(huì)從設(shè)計(jì)思路、核心細(xì)節(jié)、完整實(shí)操、常見問題四個(gè)層面把它拆干凈。不管你是剛學(xué)容器的新手還是已經(jīng)寫過不少代碼但想看看別人怎么組織這類邏輯的老手應(yīng)該都能找到有用的東西。代碼我會(huì)用C寫因?yàn)檫@道題本身就是C實(shí)訓(xùn)題映射和向量也是C里最常用的兩個(gè)容器。但思路是通用的換成其他語言一樣成立。2. 整體設(shè)計(jì)與思路拆解2.1 為什么選映射而不是數(shù)組或哈希先想一個(gè)問題球隊(duì)名字是字符串不是數(shù)字。如果用數(shù)組來存你得先給每支球隊(duì)分配一個(gè)編號(hào)然后維護(hù)一張“名字到編號(hào)”的對(duì)照表。這多了一層間接代碼寫起來啰嗦讀起來也費(fèi)勁。映射結(jié)構(gòu)天然就是干這個(gè)的——它把“鍵”和“值”直接關(guān)聯(lián)起來鍵是球隊(duì)名值是這支球隊(duì)的統(tǒng)計(jì)數(shù)據(jù)。你拿到一個(gè)球隊(duì)名直接就能找到它的數(shù)據(jù)不需要任何中間轉(zhuǎn)換。那為什么不用無序映射呢?zé)o序映射的底層是哈希表查找效率理論上更高但它不保證順序。這道題最后要排序輸出順序反正要重新排用無序映射似乎也行。但實(shí)際寫的時(shí)候你會(huì)發(fā)現(xiàn)有序映射的鍵本身就是按字典序排列的在某些中間步驟里比如調(diào)試打印看起來更直觀。而且這道題的數(shù)據(jù)量很小有序映射的查找開銷完全可以忽略。所以選有序映射更多是出于代碼可讀性和調(diào)試便利性的考慮性能差異在這個(gè)場景下可以忽略不計(jì)。提示如果你在實(shí)際項(xiàng)目中處理的是海量數(shù)據(jù)且對(duì)查找性能有極致要求無序映射確實(shí)更合適。但一定要記住無序映射的鍵類型需要提供哈希函數(shù)自定義類型的話還得自己寫哈希和相等比較這是額外的成本。2.2 值類型的設(shè)計(jì)結(jié)構(gòu)體還是嵌套映射映射的值存什么有兩種常見做法。一種是把球隊(duì)的所有統(tǒng)計(jì)數(shù)據(jù)打包成一個(gè)結(jié)構(gòu)體映射的值就是這個(gè)結(jié)構(gòu)體。另一種是用嵌套映射比如外層映射的鍵是球隊(duì)名值又是一個(gè)映射里面存“積分”“凈勝球”這些字段。兩種做法都能跑通但我強(qiáng)烈建議用結(jié)構(gòu)體。原因很簡單結(jié)構(gòu)體的字段是編譯期確定的訪問速度快代碼提示友好寫起來也清晰。嵌套映射雖然靈活但每次訪問都要經(jīng)過兩次查找而且字段名是字符串寫錯(cuò)了編譯器不會(huì)報(bào)錯(cuò)運(yùn)行時(shí)才發(fā)現(xiàn)問題。這道題的統(tǒng)計(jì)字段是固定的——積分、凈勝球、進(jìn)球數(shù)——沒有任何理由用嵌套映射。結(jié)構(gòu)體定義清楚后面所有操作都圍繞這個(gè)結(jié)構(gòu)體展開邏輯一目了然。2.3 排序策略為什么必須轉(zhuǎn)存到順序容器映射本身是不支持按值排序的。它的排序規(guī)則只針對(duì)鍵而且是你插入時(shí)就定好的有序映射按字典序無序映射根本不保證順序。但題目要求按積分、凈勝球等字段排名這些都在值里面。所以你必須把映射里的元素“搬”到一個(gè)支持自定義排序的容器里也就是順序容器。轉(zhuǎn)存的過程很簡單遍歷映射把每個(gè)鍵值對(duì)塞進(jìn)順序容器。但這里有個(gè)細(xì)節(jié)——順序容器里存什么如果只存球隊(duì)名排序的時(shí)候還得回頭去映射里查數(shù)據(jù)多一次查找不說代碼也繞。更好的做法是把球隊(duì)名和統(tǒng)計(jì)數(shù)據(jù)一起打包存進(jìn)去排序時(shí)直接比較結(jié)構(gòu)體里的字段。這樣排序邏輯自包含不依賴外部映射既清晰又高效。轉(zhuǎn)存之后用排序算法配合自定義比較函數(shù)就能按任意規(guī)則排列了。比較函數(shù)的寫法是這道題的核心考點(diǎn)之一后面會(huì)詳細(xì)展開。3. 核心細(xì)節(jié)解析與實(shí)操要點(diǎn)3.1 統(tǒng)計(jì)數(shù)據(jù)的字段設(shè)計(jì)與計(jì)算邏輯先明確要統(tǒng)計(jì)哪些數(shù)據(jù)。足球比賽里一支球隊(duì)的排名依據(jù)通常是積分、凈勝球、進(jìn)球數(shù)。積分規(guī)則是勝一場得3分平一場得1分負(fù)一場得0分。凈勝球是總進(jìn)球數(shù)減去總失球數(shù)。這些字段需要在結(jié)構(gòu)體里定義清楚。struct TeamStats { string name; int points 0; // 積分 int goalsFor 0; // 進(jìn)球數(shù) int goalsAgainst 0; // 失球數(shù) int goalDiff 0; // 凈勝球 };注意我給每個(gè)字段都設(shè)了默認(rèn)值0。這是一個(gè)小習(xí)慣但能避免很多問題。如果不設(shè)默認(rèn)值結(jié)構(gòu)體成員就是未初始化的隨機(jī)值后面累加的時(shí)候結(jié)果就全錯(cuò)了。這種錯(cuò)誤特別隱蔽因?yàn)榫幾g器不會(huì)報(bào)錯(cuò)運(yùn)行時(shí)數(shù)據(jù)看起來也“像那么回事”但就是不對(duì)。我踩過這個(gè)坑排查了半天才發(fā)現(xiàn)是初始化的問題。計(jì)算邏輯很直接每讀入一場比賽拿到主隊(duì)名、客隊(duì)名、主隊(duì)進(jìn)球、客隊(duì)進(jìn)球。然后分別更新兩支球隊(duì)的數(shù)據(jù)。主隊(duì)進(jìn)球數(shù)加上主隊(duì)進(jìn)球失球數(shù)加上客隊(duì)進(jìn)球客隊(duì)反過來。積分根據(jù)勝負(fù)關(guān)系來加。凈勝球可以在所有比賽處理完之后統(tǒng)一算也可以每次更新。我傾向于最后統(tǒng)一算因?yàn)閮魟偾蚴沁M(jìn)球減失球每次更新反而多一次計(jì)算。3.2 映射的插入技巧下標(biāo)訪問與插入的區(qū)別往映射里添加球隊(duì)數(shù)據(jù)時(shí)有兩種寫法。一種是直接用下標(biāo)訪問比如teams[name].points 3。另一種是先用查找函數(shù)判斷是否存在不存在就插入存在就更新。兩種寫法都能用但行為有細(xì)微差別。下標(biāo)訪問的語義是如果鍵存在返回對(duì)應(yīng)的值如果不存在自動(dòng)創(chuàng)建一個(gè)默認(rèn)值并返回。這意味著你不需要手動(dòng)判斷球隊(duì)是否第一次出現(xiàn)直接下標(biāo)訪問就能自動(dòng)初始化。對(duì)于這道題來說這個(gè)特性非常方便因?yàn)槊恐蜿?duì)第一次出現(xiàn)時(shí)數(shù)據(jù)都是零正好是默認(rèn)值。但下標(biāo)訪問有個(gè)潛在問題它會(huì)無條件創(chuàng)建新元素。如果你只是想查詢而不想插入用下標(biāo)訪問就會(huì)意外地往映射里塞數(shù)據(jù)。這道題里不存在這個(gè)問題因?yàn)槊看蜗聵?biāo)訪問都是確實(shí)要更新數(shù)據(jù)。但在其他場景下要小心查詢用查找函數(shù)更新用下標(biāo)訪問分清楚。注意下標(biāo)訪問的鍵類型必須支持默認(rèn)構(gòu)造。對(duì)于字符串鍵來說這沒問題但如果鍵是自定義類型得確保它有默認(rèn)構(gòu)造函數(shù)否則編譯不過。3.3 轉(zhuǎn)存與排序比較函數(shù)的寫法與陷阱轉(zhuǎn)存就是遍歷映射把每個(gè)鍵值對(duì)推進(jìn)順序容器。代碼很簡單vectorTeamStats ranking; for (auto pair : teams) { ranking.push_back(pair.second); }注意這里我直接存了結(jié)構(gòu)體沒有存鍵值對(duì)。因?yàn)榻Y(jié)構(gòu)體里已經(jīng)有球隊(duì)名了不需要額外存鍵。如果你用的結(jié)構(gòu)體里沒有名字字段那就得存鍵值對(duì)排序時(shí)從鍵值對(duì)里取名字。兩種方式都行看你的結(jié)構(gòu)體設(shè)計(jì)。排序的比較函數(shù)是重點(diǎn)。題目要求的排序規(guī)則通常是先按積分降序積分相同按凈勝球降序凈勝球相同按進(jìn)球數(shù)降序。如果還相同可能按球隊(duì)名字典序升序。這個(gè)優(yōu)先級(jí)順序不能搞錯(cuò)否則排名就不對(duì)。sort(ranking.begin(), ranking.end(), [](const TeamStats a, const TeamStats b) { if (a.points ! b.points) return a.points b.points; if (a.goalDiff ! b.goalDiff) return a.goalDiff b.goalDiff; if (a.goalsFor ! b.goalsFor) return a.goalsFor b.goalsFor; return a.name b.name; });這個(gè)比較函數(shù)看起來直白但有兩個(gè)容易出錯(cuò)的地方。第一降序用大于號(hào)升序用小于號(hào)別搞反了。第二比較函數(shù)必須滿足嚴(yán)格弱序也就是說不能出現(xiàn)“a小于b且b小于a”的情況。上面這個(gè)寫法是鏈?zhǔn)降拿恳粚佣寂懦讼嗟鹊那闆r所以是安全的。但如果你寫成return a.points b.points那就破壞了嚴(yán)格弱序排序算法可能崩潰或者產(chǎn)生未定義行為。這個(gè)坑很多人踩過而且癥狀很詭異——有時(shí)候能跑有時(shí)候直接段錯(cuò)誤。3.4 輸入解析的細(xì)節(jié)如何處理比賽結(jié)果輸入格式通常是每行一場比賽包含主隊(duì)名、客隊(duì)名、主隊(duì)進(jìn)球、客隊(duì)進(jìn)球。用輸入流直接讀就行string home, away; int homeGoals, awayGoals; while (cin home away homeGoals awayGoals) { // 更新數(shù)據(jù) }但要注意有些題目的輸入可能包含額外的空格或換行用輸入流讀取會(huì)自動(dòng)跳過空白字符所以一般沒問題。如果輸入格式更復(fù)雜比如用冒號(hào)分隔比分那就得用字符串流或者手動(dòng)解析。這道題是實(shí)訓(xùn)題輸入格式通常很規(guī)整直接讀就行。更新數(shù)據(jù)的邏輯teams[home].name home; teams[home].goalsFor homeGoals; teams[home].goalsAgainst awayGoals; teams[away].name away; teams[away].goalsFor awayGoals; teams[away].goalsAgainst homeGoals; if (homeGoals awayGoals) { teams[home].points 3; } else if (homeGoals awayGoals) { teams[away].points 3; } else { teams[home].points 1; teams[away].points 1; }凈勝球在所有比賽處理完后統(tǒng)一計(jì)算for (auto pair : teams) { pair.second.goalDiff pair.second.goalsFor - pair.second.goalsAgainst; }這里用引用遍歷直接修改映射里的值。如果用值遍歷改的是副本原數(shù)據(jù)不變這是個(gè)常見錯(cuò)誤。4. 完整實(shí)操流程與代碼實(shí)現(xiàn)4.1 從零搭建代碼框架先把整體框架搭出來再往里填細(xì)節(jié)。這樣寫代碼不容易亂也方便調(diào)試。#include iostream #include map #include vector #include string #include algorithm using namespace std; struct TeamStats { string name; int points 0; int goalsFor 0; int goalsAgainst 0; int goalDiff 0; }; int main() { mapstring, TeamStats teams; string home, away; int homeGoals, awayGoals; // 讀取比賽數(shù)據(jù) while (cin home away homeGoals awayGoals) { // 更新主隊(duì)數(shù)據(jù) teams[home].name home; teams[home].goalsFor homeGoals; teams[home].goalsAgainst awayGoals; // 更新客隊(duì)數(shù)據(jù) teams[away].name away; teams[away].goalsFor awayGoals; teams[away].goalsAgainst homeGoals; // 更新積分 if (homeGoals awayGoals) { teams[home].points 3; } else if (homeGoals awayGoals) { teams[away].points 3; } else { teams[home].points 1; teams[away].points 1; } } // 計(jì)算凈勝球 for (auto pair : teams) { pair.second.goalDiff pair.second.goalsFor - pair.second.goalsAgainst; } // 轉(zhuǎn)存到向量 vectorTeamStats ranking; for (auto pair : teams) { ranking.push_back(pair.second); } // 排序 sort(ranking.begin(), ranking.end(), [](const TeamStats a, const TeamStats b) { if (a.points ! b.points) return a.points b.points; if (a.goalDiff ! b.goalDiff) return a.goalDiff b.goalDiff; if (a.goalsFor ! b.goalsFor) return a.goalsFor b.goalsFor; return a.name b.name; }); // 輸出 for (const auto team : ranking) { cout team.name team.points team.goalDiff team.goalsFor endl; } return 0; }這段代碼可以直接編譯運(yùn)行。輸入格式是每行四個(gè)值主隊(duì)名、客隊(duì)名、主隊(duì)進(jìn)球、客隊(duì)進(jìn)球。程序會(huì)持續(xù)讀取直到輸入結(jié)束然后輸出排名。4.2 關(guān)鍵步驟的參數(shù)選擇與計(jì)算過程排序規(guī)則里的優(yōu)先級(jí)順序不是隨便定的。積分排第一因?yàn)榉e分是勝負(fù)的直接體現(xiàn)最能反映球隊(duì)的整體表現(xiàn)。凈勝球排第二因?yàn)榉e分相同時(shí)凈勝球多的球隊(duì)通常進(jìn)攻更強(qiáng)或防守更好。進(jìn)球數(shù)排第三因?yàn)閮魟偾蛳嗤瑫r(shí)進(jìn)球多的球隊(duì)進(jìn)攻火力更猛。最后按名字字典序純粹是為了在極端情況下有一個(gè)確定的順序避免輸出不穩(wěn)定。這個(gè)優(yōu)先級(jí)順序和真實(shí)足球聯(lián)賽的排名規(guī)則基本一致。如果你在開發(fā)其他排名系統(tǒng)比如電商商品排序優(yōu)先級(jí)可能是銷量降序、評(píng)分降序、價(jià)格升序。邏輯是一樣的只是字段不同。比較函數(shù)里的每一層判斷都不能省。如果只寫積分比較積分相同的球隊(duì)順序就是隨機(jī)的每次運(yùn)行結(jié)果可能不一樣。這在調(diào)試時(shí)特別讓人抓狂因?yàn)槟銜?huì)以為代碼有問題其實(shí)是排序不穩(wěn)定導(dǎo)致的。加上完整的比較鏈之后輸出就是確定的方便驗(yàn)證。4.3 調(diào)試與驗(yàn)證方法寫完代碼別急著提交先自己造幾組數(shù)據(jù)驗(yàn)證。最簡單的測(cè)試是兩支球隊(duì)打一場主隊(duì)贏。預(yù)期結(jié)果是主隊(duì)3分排第一客隊(duì)0分排第二。然后測(cè)試平局兩隊(duì)各1分凈勝球都是0進(jìn)球數(shù)相同按名字排序。再測(cè)試多支球隊(duì)多場比賽手動(dòng)算一下預(yù)期結(jié)果和程序輸出對(duì)比。如果結(jié)果不對(duì)先檢查數(shù)據(jù)更新邏輯。最常見的錯(cuò)誤是主客隊(duì)數(shù)據(jù)搞反了比如把主隊(duì)的失球加到了客隊(duì)頭上。另一個(gè)常見錯(cuò)誤是積分規(guī)則記錯(cuò)了比如平局給了3分。這些錯(cuò)誤通過簡單的測(cè)試數(shù)據(jù)就能發(fā)現(xiàn)。調(diào)試的時(shí)候可以在關(guān)鍵步驟打印中間結(jié)果比如每場比賽后打印所有球隊(duì)的數(shù)據(jù)或者排序前打印向量里的內(nèi)容。這樣能快速定位問題出在哪個(gè)環(huán)節(jié)。不過記得提交前把調(diào)試輸出刪掉不然會(huì)影響判題。5. 常見問題與排查技巧實(shí)錄5.1 排序結(jié)果不穩(wěn)定或順序錯(cuò)亂這是最常見的問題通常有兩個(gè)原因。一是比較函數(shù)寫錯(cuò)了比如降序用了小于號(hào)或者比較鏈不完整。二是轉(zhuǎn)存的時(shí)候漏了數(shù)據(jù)比如遍歷映射時(shí)用了錯(cuò)誤的迭代方式。排查方法先檢查比較函數(shù)的每一層邏輯確認(rèn)降序用大于號(hào)、升序用小于號(hào)。然后檢查轉(zhuǎn)存循環(huán)確認(rèn)遍歷的是映射的全部元素?？梢栽谵D(zhuǎn)存后打印向量的大小和映射的大小對(duì)比看是否一致。還有一個(gè)隱蔽的問題如果比較函數(shù)里用了引用但沒加常量修飾某些編譯器可能會(huì)報(bào)錯(cuò)或者行為異常。建議比較函數(shù)的參數(shù)用常量引用既避免拷貝又保證安全。5.2 映射下標(biāo)訪問導(dǎo)致的意外插入前面提到過下標(biāo)訪問會(huì)自動(dòng)創(chuàng)建不存在的鍵。如果你在查詢時(shí)用了下標(biāo)訪問就會(huì)往映射里塞一堆空數(shù)據(jù)。這些空數(shù)據(jù)會(huì)參與后面的排序和輸出導(dǎo)致結(jié)果里出現(xiàn)莫名其妙的球隊(duì)。排查方法檢查所有映射訪問確認(rèn)查詢用查找函數(shù)更新用下標(biāo)訪問。如果發(fā)現(xiàn)映射的大小比預(yù)期大很可能就是這個(gè)問題。提示C17之后可以用插入或賦值的接口來避免意外插入但下標(biāo)訪問在更新場景下依然是最簡潔的寫法。關(guān)鍵是分清楚什么時(shí)候該用哪種。5.3 輸入讀取的死循環(huán)或提前結(jié)束輸入讀取的循環(huán)條件寫不對(duì)可能導(dǎo)致死循環(huán)或者提前退出。比如用while (!cin.eof())作為條件這是典型的錯(cuò)誤寫法。輸入流只有在嘗試讀取失敗后才會(huì)設(shè)置結(jié)束標(biāo)志所以循環(huán)會(huì)多執(zhí)行一次處理一份無效數(shù)據(jù)。正確的寫法是直接用輸入操作作為循環(huán)條件while (cin home away homeGoals awayGoals)。這樣每次讀取成功才進(jìn)入循環(huán)讀取失敗自動(dòng)退出干凈利落。如果輸入格式里有特殊分隔符比如比分用冒號(hào)分隔那就得先用字符串讀整行再用字符串流解析。這種情況下循環(huán)條件要改成讀取整行然后判斷行是否為空。5.4 常見問題速查表問題現(xiàn)象可能原因排查方法解決方案排序順序不對(duì)比較函數(shù)邏輯錯(cuò)誤檢查每層比較的方向和優(yōu)先級(jí)降序用大于號(hào)升序用小于號(hào)補(bǔ)全比較鏈輸出多出未知球隊(duì)下標(biāo)訪問意外插入打印映射大小與預(yù)期對(duì)比查詢用查找函數(shù)更新用下標(biāo)訪問程序死循環(huán)輸入循環(huán)條件錯(cuò)誤檢查循環(huán)條件是否依賴輸入操作用輸入操作本身作為循環(huán)條件數(shù)據(jù)累加結(jié)果錯(cuò)誤結(jié)構(gòu)體未初始化檢查結(jié)構(gòu)體成員是否有默認(rèn)值給所有數(shù)值成員設(shè)默認(rèn)值0凈勝球計(jì)算錯(cuò)誤主客隊(duì)數(shù)據(jù)搞反打印每場比賽后的中間數(shù)據(jù)確認(rèn)主隊(duì)進(jìn)球加到主隊(duì)失球加到客隊(duì)編譯報(bào)錯(cuò)找不到符號(hào)缺少頭文件檢查包含的頭文件補(bǔ)上映射、向量、算法、字符串頭文件5.5 獨(dú)家避坑經(jīng)驗(yàn)第一個(gè)經(jīng)驗(yàn)結(jié)構(gòu)體里的球隊(duì)名其實(shí)可以省掉因?yàn)橛成涞逆I就是球隊(duì)名。但轉(zhuǎn)存到向量之后鍵就丟了所以結(jié)構(gòu)體里必須存一份名字。如果你不想在結(jié)構(gòu)體里存名字那就得把鍵值對(duì)一起轉(zhuǎn)存排序時(shí)從鍵值對(duì)里取名字。兩種方式都行但結(jié)構(gòu)體存名字更直觀。第二個(gè)經(jīng)驗(yàn)凈勝球可以在讀入比賽時(shí)實(shí)時(shí)更新不必等到最后統(tǒng)一算。實(shí)時(shí)更新的寫法是主隊(duì)凈勝球加主隊(duì)進(jìn)球減客隊(duì)進(jìn)球客隊(duì)反過來。但這樣每次都要算一遍代碼稍微啰嗦。統(tǒng)一算的好處是邏輯集中不容易出錯(cuò)。我傾向于統(tǒng)一算。第三個(gè)經(jīng)驗(yàn)如果題目要求輸出格式很嚴(yán)格比如球隊(duì)名左對(duì)齊、數(shù)字右對(duì)齊那就得用輸出格式控制。C里可以用輸出流的格式標(biāo)志來設(shè)置對(duì)齊和寬度。但實(shí)訓(xùn)題通常不要求這么細(xì)直接空格分隔就行。如果判題系統(tǒng)對(duì)格式敏感那就得仔細(xì)讀題目的輸出要求。第四個(gè)經(jīng)驗(yàn)映射的鍵是字符串時(shí)字典序比較是按字符編碼逐位比較的。大寫字母在小寫字母前面所以如果球隊(duì)名有大寫有小寫排序結(jié)果可能和你預(yù)期的不一樣。這道題里球隊(duì)名通常是統(tǒng)一的格式不太會(huì)遇到這個(gè)問題。但如果遇到了可以在比較前統(tǒng)一轉(zhuǎn)成小寫或大寫。6. 從這道題延伸出的通用模式這道題表面上是足球排名實(shí)際上是一個(gè)通用的數(shù)據(jù)處理模式分組聚合、計(jì)算指標(biāo)、排序輸出。這個(gè)模式在開發(fā)中出現(xiàn)的頻率極高幾乎每個(gè)項(xiàng)目都會(huì)遇到。比如電商系統(tǒng)里統(tǒng)計(jì)每個(gè)品類的銷售額然后按銷售額排名展示。用戶行為分析里統(tǒng)計(jì)每個(gè)頁面的訪問量然后按訪問量排序。日志分析里統(tǒng)計(jì)每個(gè)接口的調(diào)用次數(shù)和平均耗時(shí)然后按耗時(shí)排序。這些場景的代碼結(jié)構(gòu)和這道題幾乎一模一樣只是字段名和計(jì)算邏輯不同。映射加向量的組合之所以這么常用是因?yàn)樗鉀Q了兩個(gè)核心問題映射負(fù)責(zé)按維度聚合向量負(fù)責(zé)按指標(biāo)排序。兩者各司其職組合起來就能覆蓋絕大多數(shù)統(tǒng)計(jì)排序需求。你把這套模式練熟了以后遇到類似需求基本就是套模板的事。如果要處理的數(shù)據(jù)量特別大比如上千萬條記錄那可能要考慮更高效的數(shù)據(jù)結(jié)構(gòu)或者并行處理。但對(duì)于絕大多數(shù)業(yè)務(wù)場景來說映射加向量的組合已經(jīng)足夠用了。性能瓶頸通常不在容器選擇上而在數(shù)據(jù)讀取和業(yè)務(wù)邏輯上。我在實(shí)際項(xiàng)目里用這套模式處理過日志統(tǒng)計(jì)、用戶排名、商品排序等多種需求代碼改動(dòng)量很小基本就是換個(gè)結(jié)構(gòu)體定義和比較函數(shù)。這也是為什么我覺得這道實(shí)訓(xùn)題值得認(rèn)真做——它練的不是足球排名而是一個(gè)能反復(fù)復(fù)用的編程套路。把這個(gè)套路吃透以后寫類似功能的時(shí)候你腦子里會(huì)有清晰的框架不用從頭摸索。 C++映射與排序?qū)崙?zhàn)：從足球積分統(tǒng)計(jì)到通用聚合排序模式
1. 從一道實(shí)訓(xùn)題看透映射與排序的組合拳這道題我第一次看到的時(shí)候腦子里蹦出來的不是足球而是“這不就是典型的統(tǒng)計(jì)聚合加排序輸出嗎”。題目背景是歐洲冠軍聯(lián)賽給出一堆比賽結(jié)果需要統(tǒng)計(jì)每支球隊(duì)的積分、凈勝球等數(shù)據(jù)最后按規(guī)則排出名次。核心操作就兩件事用映射結(jié)構(gòu)把球隊(duì)和它的統(tǒng)計(jì)數(shù)據(jù)關(guān)聯(lián)起來再把映射里的內(nèi)容轉(zhuǎn)存到順序容器里做排序。聽起來簡單但真動(dòng)手寫的時(shí)候坑比想象中多。為什么這道題值得單獨(dú)拿出來聊因?yàn)樗鼛缀醺采w了日常開發(fā)中最常見的一類需求按某個(gè)維度聚合數(shù)據(jù)再按另一個(gè)維度排序輸出。比如統(tǒng)計(jì)每個(gè)用戶的訂單總額然后按金額排名統(tǒng)計(jì)每個(gè)接口的調(diào)用次數(shù)然后按次數(shù)排序統(tǒng)計(jì)每個(gè)商品的銷量然后按銷量展示。這些場景的本質(zhì)和這道題一模一樣。你把這套“映射聚合加順序排序”的套路吃透了以后遇到類似需求基本就是換個(gè)字段名的事。這篇文章我會(huì)從設(shè)計(jì)思路、核心細(xì)節(jié)、完整實(shí)操、常見問題四個(gè)層面把它拆干凈。不管你是剛學(xué)容器的新手還是已經(jīng)寫過不少代碼但想看看別人怎么組織這類邏輯的老手應(yīng)該都能找到有用的東西。代碼我會(huì)用C寫因?yàn)檫@道題本身就是C實(shí)訓(xùn)題映射和向量也是C里最常用的兩個(gè)容器。但思路是通用的換成其他語言一樣成立。2. 整體設(shè)計(jì)與思路拆解2.1 為什么選映射而不是數(shù)組或哈希先想一個(gè)問題球隊(duì)名字是字符串不是數(shù)字。如果用數(shù)組來存你得先給每支球隊(duì)分配一個(gè)編號(hào)然后維護(hù)一張“名字到編號(hào)”的對(duì)照表。這多了一層間接代碼寫起來啰嗦讀起來也費(fèi)勁。映射結(jié)構(gòu)天然就是干這個(gè)的——它把“鍵”和“值”直接關(guān)聯(lián)起來鍵是球隊(duì)名值是這支球隊(duì)的統(tǒng)計(jì)數(shù)據(jù)。你拿到一個(gè)球隊(duì)名直接就能找到它的數(shù)據(jù)不需要任何中間轉(zhuǎn)換。那為什么不用無序映射呢?zé)o序映射的底層是哈希表查找效率理論上更高但它不保證順序。這道題最后要排序輸出順序反正要重新排用無序映射似乎也行。但實(shí)際寫的時(shí)候你會(huì)發(fā)現(xiàn)有序映射的鍵本身就是按字典序排列的在某些中間步驟里比如調(diào)試打印看起來更直觀。而且這道題的數(shù)據(jù)量很小有序映射的查找開銷完全可以忽略。所以選有序映射更多是出于代碼可讀性和調(diào)試便利性的考慮性能差異在這個(gè)場景下可以忽略不計(jì)。提示如果你在實(shí)際項(xiàng)目中處理的是海量數(shù)據(jù)且對(duì)查找性能有極致要求無序映射確實(shí)更合適。但一定要記住無序映射的鍵類型需要提供哈希函數(shù)自定義類型的話還得自己寫哈希和相等比較這是額外的成本。2.2 值類型的設(shè)計(jì)結(jié)構(gòu)體還是嵌套映射映射的值存什么有兩種常見做法。一種是把球隊(duì)的所有統(tǒng)計(jì)數(shù)據(jù)打包成一個(gè)結(jié)構(gòu)體映射的值就是這個(gè)結(jié)構(gòu)體。另一種是用嵌套映射比如外層映射的鍵是球隊(duì)名值又是一個(gè)映射里面存“積分”“凈勝球”這些字段。兩種做法都能跑通但我強(qiáng)烈建議用結(jié)構(gòu)體。原因很簡單結(jié)構(gòu)體的字段是編譯期確定的訪問速度快代碼提示友好寫起來也清晰。嵌套映射雖然靈活但每次訪問都要經(jīng)過兩次查找而且字段名是字符串寫錯(cuò)了編譯器不會(huì)報(bào)錯(cuò)運(yùn)行時(shí)才發(fā)現(xiàn)問題。這道題的統(tǒng)計(jì)字段是固定的——積分、凈勝球、進(jìn)球數(shù)——沒有任何理由用嵌套映射。結(jié)構(gòu)體定義清楚后面所有操作都圍繞這個(gè)結(jié)構(gòu)體展開邏輯一目了然。2.3 排序策略為什么必須轉(zhuǎn)存到順序容器映射本身是不支持按值排序的。它的排序規(guī)則只針對(duì)鍵而且是你插入時(shí)就定好的有序映射按字典序無序映射根本不保證順序。但題目要求按積分、凈勝球等字段排名這些都在值里面。所以你必須把映射里的元素“搬”到一個(gè)支持自定義排序的容器里也就是順序容器。轉(zhuǎn)存的過程很簡單遍歷映射把每個(gè)鍵值對(duì)塞進(jìn)順序容器。但這里有個(gè)細(xì)節(jié)——順序容器里存什么如果只存球隊(duì)名排序的時(shí)候還得回頭去映射里查數(shù)據(jù)多一次查找不說代碼也繞。更好的做法是把球隊(duì)名和統(tǒng)計(jì)數(shù)據(jù)一起打包存進(jìn)去排序時(shí)直接比較結(jié)構(gòu)體里的字段。這樣排序邏輯自包含不依賴外部映射既清晰又高效。轉(zhuǎn)存之后用排序算法配合自定義比較函數(shù)就能按任意規(guī)則排列了。比較函數(shù)的寫法是這道題的核心考點(diǎn)之一后面會(huì)詳細(xì)展開。3. 核心細(xì)節(jié)解析與實(shí)操要點(diǎn)3.1 統(tǒng)計(jì)數(shù)據(jù)的字段設(shè)計(jì)與計(jì)算邏輯先明確要統(tǒng)計(jì)哪些數(shù)據(jù)。足球比賽里一支球隊(duì)的排名依據(jù)通常是積分、凈勝球、進(jìn)球數(shù)。積分規(guī)則是勝一場得3分平一場得1分負(fù)一場得0分。凈勝球是總進(jìn)球數(shù)減去總失球數(shù)。這些字段需要在結(jié)構(gòu)體里定義清楚。struct TeamStats { string name; int points 0; // 積分 int goalsFor 0; // 進(jìn)球數(shù) int goalsAgainst 0; // 失球數(shù) int goalDiff 0; // 凈勝球 };注意我給每個(gè)字段都設(shè)了默認(rèn)值0。這是一個(gè)小習(xí)慣但能避免很多問題。如果不設(shè)默認(rèn)值結(jié)構(gòu)體成員就是未初始化的隨機(jī)值后面累加的時(shí)候結(jié)果就全錯(cuò)了。這種錯(cuò)誤特別隱蔽因?yàn)榫幾g器不會(huì)報(bào)錯(cuò)運(yùn)行時(shí)數(shù)據(jù)看起來也“像那么回事”但就是不對(duì)。我踩過這個(gè)坑排查了半天才發(fā)現(xiàn)是初始化的問題。計(jì)算邏輯很直接每讀入一場比賽拿到主隊(duì)名、客隊(duì)名、主隊(duì)進(jìn)球、客隊(duì)進(jìn)球。然后分別更新兩支球隊(duì)的數(shù)據(jù)。主隊(duì)進(jìn)球數(shù)加上主隊(duì)進(jìn)球失球數(shù)加上客隊(duì)進(jìn)球客隊(duì)反過來。積分根據(jù)勝負(fù)關(guān)系來加。凈勝球可以在所有比賽處理完之后統(tǒng)一算也可以每次更新。我傾向于最后統(tǒng)一算因?yàn)閮魟偾蚴沁M(jìn)球減失球每次更新反而多一次計(jì)算。3.2 映射的插入技巧下標(biāo)訪問與插入的區(qū)別往映射里添加球隊(duì)數(shù)據(jù)時(shí)有兩種寫法。一種是直接用下標(biāo)訪問比如teams[name].points 3。另一種是先用查找函數(shù)判斷是否存在不存在就插入存在就更新。兩種寫法都能用但行為有細(xì)微差別。下標(biāo)訪問的語義是如果鍵存在返回對(duì)應(yīng)的值如果不存在自動(dòng)創(chuàng)建一個(gè)默認(rèn)值并返回。這意味著你不需要手動(dòng)判斷球隊(duì)是否第一次出現(xiàn)直接下標(biāo)訪問就能自動(dòng)初始化。對(duì)于這道題來說這個(gè)特性非常方便因?yàn)槊恐蜿?duì)第一次出現(xiàn)時(shí)數(shù)據(jù)都是零正好是默認(rèn)值。但下標(biāo)訪問有個(gè)潛在問題它會(huì)無條件創(chuàng)建新元素。如果你只是想查詢而不想插入用下標(biāo)訪問就會(huì)意外地往映射里塞數(shù)據(jù)。這道題里不存在這個(gè)問題因?yàn)槊看蜗聵?biāo)訪問都是確實(shí)要更新數(shù)據(jù)。但在其他場景下要小心查詢用查找函數(shù)更新用下標(biāo)訪問分清楚。注意下標(biāo)訪問的鍵類型必須支持默認(rèn)構(gòu)造。對(duì)于字符串鍵來說這沒問題但如果鍵是自定義類型得確保它有默認(rèn)構(gòu)造函數(shù)否則編譯不過。3.3 轉(zhuǎn)存與排序比較函數(shù)的寫法與陷阱轉(zhuǎn)存就是遍歷映射把每個(gè)鍵值對(duì)推進(jìn)順序容器。代碼很簡單vectorTeamStats ranking; for (auto pair : teams) { ranking.push_back(pair.second); }注意這里我直接存了結(jié)構(gòu)體沒有存鍵值對(duì)。因?yàn)榻Y(jié)構(gòu)體里已經(jīng)有球隊(duì)名了不需要額外存鍵。如果你用的結(jié)構(gòu)體里沒有名字字段那就得存鍵值對(duì)排序時(shí)從鍵值對(duì)里取名字。兩種方式都行看你的結(jié)構(gòu)體設(shè)計(jì)。排序的比較函數(shù)是重點(diǎn)。題目要求的排序規(guī)則通常是先按積分降序積分相同按凈勝球降序凈勝球相同按進(jìn)球數(shù)降序。如果還相同可能按球隊(duì)名字典序升序。這個(gè)優(yōu)先級(jí)順序不能搞錯(cuò)否則排名就不對(duì)。sort(ranking.begin(), ranking.end(), [](const TeamStats a, const TeamStats b) { if (a.points ! b.points) return a.points b.points; if (a.goalDiff ! b.goalDiff) return a.goalDiff b.goalDiff; if (a.goalsFor ! b.goalsFor) return a.goalsFor b.goalsFor; return a.name b.name; });這個(gè)比較函數(shù)看起來直白但有兩個(gè)容易出錯(cuò)的地方。第一降序用大于號(hào)升序用小于號(hào)別搞反了。第二比較函數(shù)必須滿足嚴(yán)格弱序也就是說不能出現(xiàn)“a小于b且b小于a”的情況。上面這個(gè)寫法是鏈?zhǔn)降拿恳粚佣寂懦讼嗟鹊那闆r所以是安全的。但如果你寫成return a.points b.points那就破壞了嚴(yán)格弱序排序算法可能崩潰或者產(chǎn)生未定義行為。這個(gè)坑很多人踩過而且癥狀很詭異——有時(shí)候能跑有時(shí)候直接段錯(cuò)誤。3.4 輸入解析的細(xì)節(jié)如何處理比賽結(jié)果輸入格式通常是每行一場比賽包含主隊(duì)名、客隊(duì)名、主隊(duì)進(jìn)球、客隊(duì)進(jìn)球。用輸入流直接讀就行string home, away; int homeGoals, awayGoals; while (cin home away homeGoals awayGoals) { // 更新數(shù)據(jù) }但要注意有些題目的輸入可能包含額外的空格或換行用輸入流讀取會(huì)自動(dòng)跳過空白字符所以一般沒問題。如果輸入格式更復(fù)雜比如用冒號(hào)分隔比分那就得用字符串流或者手動(dòng)解析。這道題是實(shí)訓(xùn)題輸入格式通常很規(guī)整直接讀就行。更新數(shù)據(jù)的邏輯teams[home].name home; teams[home].goalsFor homeGoals; teams[home].goalsAgainst awayGoals; teams[away].name away; teams[away].goalsFor awayGoals; teams[away].goalsAgainst homeGoals; if (homeGoals awayGoals) { teams[home].points 3; } else if (homeGoals awayGoals) { teams[away].points 3; } else { teams[home].points 1; teams[away].points 1; }凈勝球在所有比賽處理完后統(tǒng)一計(jì)算for (auto pair : teams) { pair.second.goalDiff pair.second.goalsFor - pair.second.goalsAgainst; }這里用引用遍歷直接修改映射里的值。如果用值遍歷改的是副本原數(shù)據(jù)不變這是個(gè)常見錯(cuò)誤。4. 完整實(shí)操流程與代碼實(shí)現(xiàn)4.1 從零搭建代碼框架先把整體框架搭出來再往里填細(xì)節(jié)。這樣寫代碼不容易亂也方便調(diào)試。#include iostream #include map #include vector #include string #include algorithm using namespace std; struct TeamStats { string name; int points 0; int goalsFor 0; int goalsAgainst 0; int goalDiff 0; }; int main() { mapstring, TeamStats teams; string home, away; int homeGoals, awayGoals; // 讀取比賽數(shù)據(jù) while (cin home away homeGoals awayGoals) { // 更新主隊(duì)數(shù)據(jù) teams[home].name home; teams[home].goalsFor homeGoals; teams[home].goalsAgainst awayGoals; // 更新客隊(duì)數(shù)據(jù) teams[away].name away; teams[away].goalsFor awayGoals; teams[away].goalsAgainst homeGoals; // 更新積分 if (homeGoals awayGoals) { teams[home].points 3; } else if (homeGoals awayGoals) { teams[away].points 3; } else { teams[home].points 1; teams[away].points 1; } } // 計(jì)算凈勝球 for (auto pair : teams) { pair.second.goalDiff pair.second.goalsFor - pair.second.goalsAgainst; } // 轉(zhuǎn)存到向量 vectorTeamStats ranking; for (auto pair : teams) { ranking.push_back(pair.second); } // 排序 sort(ranking.begin(), ranking.end(), [](const TeamStats a, const TeamStats b) { if (a.points ! b.points) return a.points b.points; if (a.goalDiff ! b.goalDiff) return a.goalDiff b.goalDiff; if (a.goalsFor ! b.goalsFor) return a.goalsFor b.goalsFor; return a.name b.name; }); // 輸出 for (const auto team : ranking) { cout team.name team.points team.goalDiff team.goalsFor endl; } return 0; }這段代碼可以直接編譯運(yùn)行。輸入格式是每行四個(gè)值主隊(duì)名、客隊(duì)名、主隊(duì)進(jìn)球、客隊(duì)進(jìn)球。程序會(huì)持續(xù)讀取直到輸入結(jié)束然后輸出排名。4.2 關(guān)鍵步驟的參數(shù)選擇與計(jì)算過程排序規(guī)則里的優(yōu)先級(jí)順序不是隨便定的。積分排第一因?yàn)榉e分是勝負(fù)的直接體現(xiàn)最能反映球隊(duì)的整體表現(xiàn)。凈勝球排第二因?yàn)榉e分相同時(shí)凈勝球多的球隊(duì)通常進(jìn)攻更強(qiáng)或防守更好。進(jìn)球數(shù)排第三因?yàn)閮魟偾蛳嗤瑫r(shí)進(jìn)球多的球隊(duì)進(jìn)攻火力更猛。最后按名字字典序純粹是為了在極端情況下有一個(gè)確定的順序避免輸出不穩(wěn)定。這個(gè)優(yōu)先級(jí)順序和真實(shí)足球聯(lián)賽的排名規(guī)則基本一致。如果你在開發(fā)其他排名系統(tǒng)比如電商商品排序優(yōu)先級(jí)可能是銷量降序、評(píng)分降序、價(jià)格升序。邏輯是一樣的只是字段不同。比較函數(shù)里的每一層判斷都不能省。如果只寫積分比較積分相同的球隊(duì)順序就是隨機(jī)的每次運(yùn)行結(jié)果可能不一樣。這在調(diào)試時(shí)特別讓人抓狂因?yàn)槟銜?huì)以為代碼有問題其實(shí)是排序不穩(wěn)定導(dǎo)致的。加上完整的比較鏈之后輸出就是確定的方便驗(yàn)證。4.3 調(diào)試與驗(yàn)證方法寫完代碼別急著提交先自己造幾組數(shù)據(jù)驗(yàn)證。最簡單的測(cè)試是兩支球隊(duì)打一場主隊(duì)贏。預(yù)期結(jié)果是主隊(duì)3分排第一客隊(duì)0分排第二。然后測(cè)試平局兩隊(duì)各1分凈勝球都是0進(jìn)球數(shù)相同按名字排序。再測(cè)試多支球隊(duì)多場比賽手動(dòng)算一下預(yù)期結(jié)果和程序輸出對(duì)比。如果結(jié)果不對(duì)先檢查數(shù)據(jù)更新邏輯。最常見的錯(cuò)誤是主客隊(duì)數(shù)據(jù)搞反了比如把主隊(duì)的失球加到了客隊(duì)頭上。另一個(gè)常見錯(cuò)誤是積分規(guī)則記錯(cuò)了比如平局給了3分。這些錯(cuò)誤通過簡單的測(cè)試數(shù)據(jù)就能發(fā)現(xiàn)。調(diào)試的時(shí)候可以在關(guān)鍵步驟打印中間結(jié)果比如每場比賽后打印所有球隊(duì)的數(shù)據(jù)或者排序前打印向量里的內(nèi)容。這樣能快速定位問題出在哪個(gè)環(huán)節(jié)。不過記得提交前把調(diào)試輸出刪掉不然會(huì)影響判題。5. 常見問題與排查技巧實(shí)錄5.1 排序結(jié)果不穩(wěn)定或順序錯(cuò)亂這是最常見的問題通常有兩個(gè)原因。一是比較函數(shù)寫錯(cuò)了比如降序用了小于號(hào)或者比較鏈不完整。二是轉(zhuǎn)存的時(shí)候漏了數(shù)據(jù)比如遍歷映射時(shí)用了錯(cuò)誤的迭代方式。排查方法先檢查比較函數(shù)的每一層邏輯確認(rèn)降序用大于號(hào)、升序用小于號(hào)。然后檢查轉(zhuǎn)存循環(huán)確認(rèn)遍歷的是映射的全部元素?？梢栽谵D(zhuǎn)存后打印向量的大小和映射的大小對(duì)比看是否一致。還有一個(gè)隱蔽的問題如果比較函數(shù)里用了引用但沒加常量修飾某些編譯器可能會(huì)報(bào)錯(cuò)或者行為異常。建議比較函數(shù)的參數(shù)用常量引用既避免拷貝又保證安全。5.2 映射下標(biāo)訪問導(dǎo)致的意外插入前面提到過下標(biāo)訪問會(huì)自動(dòng)創(chuàng)建不存在的鍵。如果你在查詢時(shí)用了下標(biāo)訪問就會(huì)往映射里塞一堆空數(shù)據(jù)。這些空數(shù)據(jù)會(huì)參與后面的排序和輸出導(dǎo)致結(jié)果里出現(xiàn)莫名其妙的球隊(duì)。排查方法檢查所有映射訪問確認(rèn)查詢用查找函數(shù)更新用下標(biāo)訪問。如果發(fā)現(xiàn)映射的大小比預(yù)期大很可能就是這個(gè)問題。提示C17之后可以用插入或賦值的接口來避免意外插入但下標(biāo)訪問在更新場景下依然是最簡潔的寫法。關(guān)鍵是分清楚什么時(shí)候該用哪種。5.3 輸入讀取的死循環(huán)或提前結(jié)束輸入讀取的循環(huán)條件寫不對(duì)可能導(dǎo)致死循環(huán)或者提前退出。比如用while (!cin.eof())作為條件這是典型的錯(cuò)誤寫法。輸入流只有在嘗試讀取失敗后才會(huì)設(shè)置結(jié)束標(biāo)志所以循環(huán)會(huì)多執(zhí)行一次處理一份無效數(shù)據(jù)。正確的寫法是直接用輸入操作作為循環(huán)條件while (cin home away homeGoals awayGoals)。這樣每次讀取成功才進(jìn)入循環(huán)讀取失敗自動(dòng)退出干凈利落。如果輸入格式里有特殊分隔符比如比分用冒號(hào)分隔那就得先用字符串讀整行再用字符串流解析。這種情況下循環(huán)條件要改成讀取整行然后判斷行是否為空。5.4 常見問題速查表問題現(xiàn)象可能原因排查方法解決方案排序順序不對(duì)比較函數(shù)邏輯錯(cuò)誤檢查每層比較的方向和優(yōu)先級(jí)降序用大于號(hào)升序用小于號(hào)補(bǔ)全比較鏈輸出多出未知球隊(duì)下標(biāo)訪問意外插入打印映射大小與預(yù)期對(duì)比查詢用查找函數(shù)更新用下標(biāo)訪問程序死循環(huán)輸入循環(huán)條件錯(cuò)誤檢查循環(huán)條件是否依賴輸入操作用輸入操作本身作為循環(huán)條件數(shù)據(jù)累加結(jié)果錯(cuò)誤結(jié)構(gòu)體未初始化檢查結(jié)構(gòu)體成員是否有默認(rèn)值給所有數(shù)值成員設(shè)默認(rèn)值0凈勝球計(jì)算錯(cuò)誤主客隊(duì)數(shù)據(jù)搞反打印每場比賽后的中間數(shù)據(jù)確認(rèn)主隊(duì)進(jìn)球加到主隊(duì)失球加到客隊(duì)編譯報(bào)錯(cuò)找不到符號(hào)缺少頭文件檢查包含的頭文件補(bǔ)上映射、向量、算法、字符串頭文件5.5 獨(dú)家避坑經(jīng)驗(yàn)第一個(gè)經(jīng)驗(yàn)結(jié)構(gòu)體里的球隊(duì)名其實(shí)可以省掉因?yàn)橛成涞逆I就是球隊(duì)名。但轉(zhuǎn)存到向量之后鍵就丟了所以結(jié)構(gòu)體里必須存一份名字。如果你不想在結(jié)構(gòu)體里存名字那就得把鍵值對(duì)一起轉(zhuǎn)存排序時(shí)從鍵值對(duì)里取名字。兩種方式都行但結(jié)構(gòu)體存名字更直觀。第二個(gè)經(jīng)驗(yàn)凈勝球可以在讀入比賽時(shí)實(shí)時(shí)更新不必等到最后統(tǒng)一算。實(shí)時(shí)更新的寫法是主隊(duì)凈勝球加主隊(duì)進(jìn)球減客隊(duì)進(jìn)球客隊(duì)反過來。但這樣每次都要算一遍代碼稍微啰嗦。統(tǒng)一算的好處是邏輯集中不容易出錯(cuò)。我傾向于統(tǒng)一算。第三個(gè)經(jīng)驗(yàn)如果題目要求輸出格式很嚴(yán)格比如球隊(duì)名左對(duì)齊、數(shù)字右對(duì)齊那就得用輸出格式控制。C里可以用輸出流的格式標(biāo)志來設(shè)置對(duì)齊和寬度。但實(shí)訓(xùn)題通常不要求這么細(xì)直接空格分隔就行。如果判題系統(tǒng)對(duì)格式敏感那就得仔細(xì)讀題目的輸出要求。第四個(gè)經(jīng)驗(yàn)映射的鍵是字符串時(shí)字典序比較是按字符編碼逐位比較的。大寫字母在小寫字母前面所以如果球隊(duì)名有大寫有小寫排序結(jié)果可能和你預(yù)期的不一樣。這道題里球隊(duì)名通常是統(tǒng)一的格式不太會(huì)遇到這個(gè)問題。但如果遇到了可以在比較前統(tǒng)一轉(zhuǎn)成小寫或大寫。6. 從這道題延伸出的通用模式這道題表面上是足球排名實(shí)際上是一個(gè)通用的數(shù)據(jù)處理模式分組聚合、計(jì)算指標(biāo)、排序輸出。這個(gè)模式在開發(fā)中出現(xiàn)的頻率極高幾乎每個(gè)項(xiàng)目都會(huì)遇到。比如電商系統(tǒng)里統(tǒng)計(jì)每個(gè)品類的銷售額然后按銷售額排名展示。用戶行為分析里統(tǒng)計(jì)每個(gè)頁面的訪問量然后按訪問量排序。日志分析里統(tǒng)計(jì)每個(gè)接口的調(diào)用次數(shù)和平均耗時(shí)然后按耗時(shí)排序。這些場景的代碼結(jié)構(gòu)和這道題幾乎一模一樣只是字段名和計(jì)算邏輯不同。映射加向量的組合之所以這么常用是因?yàn)樗鉀Q了兩個(gè)核心問題映射負(fù)責(zé)按維度聚合向量負(fù)責(zé)按指標(biāo)排序。兩者各司其職組合起來就能覆蓋絕大多數(shù)統(tǒng)計(jì)排序需求。你把這套模式練熟了以后遇到類似需求基本就是套模板的事。如果要處理的數(shù)據(jù)量特別大比如上千萬條記錄那可能要考慮更高效的數(shù)據(jù)結(jié)構(gòu)或者并行處理。但對(duì)于絕大多數(shù)業(yè)務(wù)場景來說映射加向量的組合已經(jīng)足夠用了。性能瓶頸通常不在容器選擇上而在數(shù)據(jù)讀取和業(yè)務(wù)邏輯上。我在實(shí)際項(xiàng)目里用這套模式處理過日志統(tǒng)計(jì)、用戶排名、商品排序等多種需求代碼改動(dòng)量很小基本就是換個(gè)結(jié)構(gòu)體定義和比較函數(shù)。這也是為什么我覺得這道實(shí)訓(xùn)題值得認(rèn)真做——它練的不是足球排名而是一個(gè)能反復(fù)復(fù)用的編程套路。把這個(gè)套路吃透以后寫類似功能的時(shí)候你腦子里會(huì)有清晰的框架不用從頭摸索。