1. 從一次數(shù)據(jù)展示的尷尬說(shuō)起為什么結(jié)構(gòu)體排序是基本功最近在幫一個(gè)做嵌入式設(shè)備日志分析的朋友看代碼他遇到了一個(gè)挺典型的問(wèn)題。設(shè)備上報(bào)的日志數(shù)據(jù)包是一個(gè)結(jié)構(gòu)體數(shù)組每個(gè)結(jié)構(gòu)體包含了時(shí)間戳、設(shè)備ID、錯(cuò)誤碼和描述信息。他的需求很簡(jiǎn)單就是要把這些日志按時(shí)間先后在界面上列出來(lái)。他吭哧吭哧寫(xiě)了個(gè)冒泡排序?qū)χ磺Ф鄺l數(shù)據(jù)跑界面卡了好幾秒。更麻煩的是后來(lái)產(chǎn)品經(jīng)理說(shuō)能不能先按錯(cuò)誤碼嚴(yán)重程度排相同嚴(yán)重程度的再按時(shí)間排他當(dāng)時(shí)就有點(diǎn)懵覺(jué)得又要重寫(xiě)排序邏輯。這個(gè)場(chǎng)景我相信很多開(kāi)發(fā)者都遇到過(guò)無(wú)論是處理學(xué)生成績(jī)表、商品列表還是像他這樣的日志數(shù)據(jù)。當(dāng)我們的數(shù)據(jù)不再是簡(jiǎn)單的整數(shù)或字符串而是一個(gè)包含多個(gè)字段的復(fù)合體也就是結(jié)構(gòu)體時(shí)如何根據(jù)某一個(gè)或某幾個(gè)字段進(jìn)行快速、靈活的排序就成了必須掌握的基本功。在C中這不僅僅是調(diào)用一個(gè)sort那么簡(jiǎn)單它背后涉及到對(duì)數(shù)據(jù)封裝、比較規(guī)則定義和STL算法理解的綜合考察。很多人學(xué)了sort函數(shù)知道它能排vectorint但一到自己定義的結(jié)構(gòu)體就無(wú)從下手。其實(shí)解決結(jié)構(gòu)體排序核心就在于如何明確地告訴sort函數(shù)“兩個(gè)結(jié)構(gòu)體對(duì)象到底怎樣才算‘小于’對(duì)方”圍繞這個(gè)核心問(wèn)題實(shí)踐中沉淀出了三種主流且優(yōu)雅的實(shí)現(xiàn)方式重載小于運(yùn)算符、定義自定義比較函數(shù)、使用Lambda表達(dá)式。這三種方式并非簡(jiǎn)單的并列關(guān)系它們各有最佳的應(yīng)用場(chǎng)景和細(xì)微的取舍。接下來(lái)我就結(jié)合大量實(shí)際編碼和調(diào)試的經(jīng)驗(yàn)把這三種方式的里里外外、坑坑洼洼都給你講明白。2. 基石理解STL sort的排序規(guī)則與比較器在深入三種方式之前我們必須先統(tǒng)一思想理解std::sort以及很多其他STL算法是如何工作的。這能幫你從根本上明白為什么需要這些方式而不是死記硬背語(yǔ)法。std::sort的典型函數(shù)簽名是這樣的template class RandomIt void sort( RandomIt first, RandomIt last ); template class RandomIt, class Compare void sort( RandomIt first, RandomIt last, Compare comp );第一種形式要求迭代器范圍[first, last)內(nèi)的元素類(lèi)型必須支持嚴(yán)格弱序的比較特別是operator。對(duì)于內(nèi)置類(lèi)型如int,double或std::string它們已經(jīng)內(nèi)置了的比較邏輯。但對(duì)于我們自定義的struct或class編譯器并不知道如何比較因此直接使用第一種形式會(huì)編譯報(bào)錯(cuò)。第二種形式是通用的它接受一個(gè)額外的參數(shù)comp即比較器。這個(gè)comp可以是函數(shù)指針、函數(shù)對(duì)象或者我們后面會(huì)重點(diǎn)講的Lambda表達(dá)式。sort算法在內(nèi)部會(huì)對(duì)元素進(jìn)行兩兩比較它并不關(guān)心元素具體是什么它只關(guān)心給定兩個(gè)元素a和bcomp(a, b)的返回值是什么。這里有一個(gè)至關(guān)重要的約定也是新手最容易踩坑的地方如果comp(a, b)返回true那么算法就認(rèn)為a應(yīng)該排在b的前面。這個(gè)comp本質(zhì)上定義了一個(gè)“小于”關(guān)系。你可以把它理解為“當(dāng)a小于b時(shí)返回真”。注意這個(gè)“小于”是廣義的完全由你定義。你可以讓它表示“價(jià)格更低”、“年齡更大”、“名字的字典序更靠前”。sort會(huì)根據(jù)這個(gè)你定義的“小于”關(guān)系將序列排列成升序。如果你想降序只需要在比較器里定義相反的規(guī)則即可例如return a.price b.price;。所以結(jié)構(gòu)體排序的所有問(wèn)題最終都?xì)w結(jié)為如何提供一個(gè)正確、高效、符合嚴(yán)格弱序規(guī)則的比較器。嚴(yán)格弱序要求比較規(guī)則滿足非自反性comp(a, a)必須為false。不對(duì)稱性如果comp(a, b)為true則comp(b, a)必須為false。傳遞性如果comp(a, b)為true且comp(b, c)為true那么comp(a, c)必須為true。等價(jià)傳遞性如果!comp(a, b) !comp(b, a)即a和b“等價(jià)”并且b和c也“等價(jià)”那么a和c也必須“等價(jià)”。在實(shí)現(xiàn)比較邏輯時(shí)尤其是多字段排序時(shí)必須時(shí)刻注意這些規(guī)則否則可能導(dǎo)致未定義行為或排序結(jié)果異常。3. 方式一重載小于運(yùn)算符 —— 定義類(lèi)型的固有順序這是最“面向?qū)ο蟆钡囊环N方式。其核心思想是將“如何比較兩個(gè)此類(lèi)型對(duì)象”的邏輯作為該類(lèi)型本身的一部分。通過(guò)為你的結(jié)構(gòu)體重載operator你實(shí)際上是在告訴所有使用這個(gè)類(lèi)型的代碼包括std::sort“我的對(duì)象之間有一種默認(rèn)的、自然的比較方式。”3.1 基礎(chǔ)語(yǔ)法與單字段排序假設(shè)我們有一個(gè)Student結(jié)構(gòu)體struct Student { int id; std::string name; double score; };如果我們想默認(rèn)按照score從高到低排序降序可以這樣重載struct Student { int id; std::string name; double score; // 重載小于運(yùn)算符 bool operator(const Student other) const { // 注意這里定義的是“小于”。我們希望分?jǐn)?shù)高的排前面所以“分?jǐn)?shù)高”意味著“更小”。 return score other.score; // 降序規(guī)則 } };使用起來(lái)非常簡(jiǎn)單直接std::vectorStudent students {...}; std::sort(students.begin(), students.end()); // 無(wú)需傳入第三個(gè)參數(shù)因?yàn)镾tudent現(xiàn)在有了自己的operatorsort的第一種形式就可以工作了。3.2 多字段排序的經(jīng)典模式實(shí)際需求往往更復(fù)雜。比如先按score降序分?jǐn)?shù)相同的再按name升序字典序。這時(shí)重載operator的邏輯就需要精心編排bool operator(const Student other) const { if (score ! other.score) { return score other.score; // 第一優(yōu)先級(jí)分?jǐn)?shù)降序 } // 分?jǐn)?shù)相同比較名字 return name other.name; // 第二優(yōu)先級(jí)名字升序 }這是一個(gè)非常經(jīng)典的模式使用if語(yǔ)句鏈按優(yōu)先級(jí)依次比較各個(gè)字段。這種寫(xiě)法清晰表達(dá)了字段的優(yōu)先級(jí)關(guān)系。3.3 適用場(chǎng)景與核心優(yōu)劣分析優(yōu)點(diǎn)語(yǔ)義清晰operator成為類(lèi)型接口的一部分任何使用該類(lèi)型的代碼都能以統(tǒng)一的方式比較對(duì)象符合封裝思想。使用簡(jiǎn)潔在排序時(shí)無(wú)需額外指定比較器代碼非常干凈sort(students.begin(), students.end())一目了然。與其他組件兼容許多STL容器如std::set,std::map和算法如std::lower_bound也依賴operator。重載后你的結(jié)構(gòu)體可以直接用作這些容器的鍵類(lèi)型。缺點(diǎn)與注意事項(xiàng)唯一性一個(gè)類(lèi)只能有一個(gè)operator。這意味著你只能定義一種“默認(rèn)”的排序規(guī)則。如果你需要在不同場(chǎng)景下按不同規(guī)則排序例如有時(shí)按分?jǐn)?shù)排有時(shí)按學(xué)號(hào)排這種方式就力不從心了。侵入性你修改了結(jié)構(gòu)體本身的定義。如果這個(gè)結(jié)構(gòu)體是第三方庫(kù)提供的或者被廣泛使用增加一個(gè)operator可能會(huì)產(chǎn)生意想不到的副作用比如影響了其他地方原本無(wú)需比較的邏輯。性能考量比較函數(shù)會(huì)被頻繁調(diào)用sort是O(n log n)次。如果結(jié)構(gòu)體很大按值傳遞const Student是必須的可以避免不必要的拷貝。同時(shí)字段比較的順序也可能影響性能通常將最可能產(chǎn)生差異的字段放在if鏈的最前面。個(gè)人經(jīng)驗(yàn)我通常只在一種情況下使用重載operator那就是這個(gè)結(jié)構(gòu)體確實(shí)存在一個(gè)明確的、公認(rèn)的、最主要的排序標(biāo)準(zhǔn)。例如一個(gè)表示“時(shí)間點(diǎn)”的Time結(jié)構(gòu)體按時(shí)間先后排序就是其固有屬性。對(duì)于大多數(shù)業(yè)務(wù)實(shí)體如Student,Product我更傾向于使用后面兩種非侵入式的方式因?yàn)樗鼈兲峁┝烁玫撵`活性。4. 方式二自定義比較函數(shù) —— 靈活的外部規(guī)則當(dāng)“一種排序規(guī)則走天下”行不通時(shí)我們就需要將比較邏輯從結(jié)構(gòu)體內(nèi)部剝離出來(lái)定義為外部的、獨(dú)立的函數(shù)。這就是自定義比較函數(shù)。4.1 函數(shù)形式的比較器我們繼續(xù)用Student例子但不重載operator?，F(xiàn)在我們定義一個(gè)獨(dú)立的函數(shù)來(lái)實(shí)現(xiàn)“按分?jǐn)?shù)降序”bool compareByScoreDesc(const Student a, const Student b) { return a.score b.score; }使用它進(jìn)行排序std::vectorStudent students {...}; std::sort(students.begin(), students.end(), compareByScoreDesc);這里compareByScoreDesc這個(gè)函數(shù)指針被傳遞給了sort。sort在內(nèi)部會(huì)調(diào)用這個(gè)函數(shù)來(lái)比較元素。4.2 函數(shù)對(duì)象仿函數(shù)帶來(lái)的狀態(tài)與效率單純函數(shù)指針功能有限。有時(shí)我們的比較規(guī)則需要依賴一些外部狀態(tài)或參數(shù)。例如我們想根據(jù)一個(gè)動(dòng)態(tài)提供的“科目權(quán)重表”來(lái)計(jì)算加權(quán)總分后再排序。這時(shí)函數(shù)對(duì)象就派上用場(chǎng)了。函數(shù)對(duì)象就是一個(gè)重載了operator()的類(lèi)或結(jié)構(gòu)體。它的對(duì)象可以像函數(shù)一樣被調(diào)用。class CompareByWeightedScore { private: std::mapstd::string, double subjectWeights; // 狀態(tài)科目權(quán)重 public: CompareByWeightedScore(const std::mapstd::string, double weights) : subjectWeights(weights) {} bool operator()(const Student a, const Student b) const { double scoreA calculateWeightedScore(a, subjectWeights); double scoreB calculateWeightedScore(b, subjectWeights); return scoreA scoreB; // 按加權(quán)分降序 } };使用方式std::mapstd::string, double weights {{math, 1.5}, {physics, 1.2}}; std::sort(students.begin(), students.end(), CompareByWeightedScore(weights));函數(shù)對(duì)象相比普通函數(shù)的巨大優(yōu)勢(shì)可攜帶狀態(tài)如上面的權(quán)重表可以在構(gòu)造時(shí)傳入并在每次比較時(shí)使用。編譯器優(yōu)化友好函數(shù)對(duì)象的operator()通常是內(nèi)聯(lián)的而函數(shù)指針的間接調(diào)用有時(shí)會(huì)阻礙優(yōu)化。在性能敏感的排序中這可能會(huì)帶來(lái)細(xì)微差異。類(lèi)型安全函數(shù)對(duì)象是一個(gè)具體的類(lèi)型模板在實(shí)例化時(shí)能獲得更多信息。4.3 適用場(chǎng)景與實(shí)戰(zhàn)技巧優(yōu)點(diǎn)高靈活性你可以為同一個(gè)結(jié)構(gòu)體定義無(wú)數(shù)個(gè)不同的比較函數(shù)分別用于不同場(chǎng)景compareByScore,compareById,compareByNameThenScore等。非侵入性無(wú)需修改結(jié)構(gòu)體源代碼尤其適合處理第三方庫(kù)或無(wú)法修改的結(jié)構(gòu)體。功能強(qiáng)大函數(shù)對(duì)象形式支持狀態(tài)注入可以實(shí)現(xiàn)非常復(fù)雜的、依賴運(yùn)行時(shí)參數(shù)的比較邏輯。缺點(diǎn)與坑點(diǎn)代碼分散比較邏輯脫離了結(jié)構(gòu)體定義當(dāng)比較函數(shù)很多時(shí)管理起來(lái)可能稍顯混亂。函數(shù)指針的開(kāi)銷(xiāo)雖然通常可忽略但在極端性能場(chǎng)景下函數(shù)指針的調(diào)用開(kāi)銷(xiāo)可能高于內(nèi)聯(lián)的函數(shù)對(duì)象或Lambda。謂詞要求比較函數(shù)必須是純函數(shù)即多次調(diào)用相同的輸入必須產(chǎn)生相同的輸出且不應(yīng)有副作用。修改全局變量或在比較函數(shù)中打印日志都是危險(xiǎn)行為可能破壞排序算法或?qū)е挛炊x結(jié)果。踩坑實(shí)錄我曾見(jiàn)過(guò)一個(gè)bug比較函數(shù)里為了調(diào)試使用std::cout打印比較信息。在Release模式下由于編譯器優(yōu)化和IO緩沖打印順序完全混亂干擾了調(diào)試更嚴(yán)重的是在某些平臺(tái)上這甚至輕微影響了比較結(jié)果的一致性導(dǎo)致排序結(jié)果偶爾異常。切記比較器只做比較這一件事。5. 方式三Lambda表達(dá)式 —— 現(xiàn)代C的優(yōu)雅之選C11引入的Lambda表達(dá)式可以說(shuō)是為STL算法量身定制的語(yǔ)法糖。它允許你在調(diào)用算法的地方就地、匿名地定義一個(gè)函數(shù)對(duì)象極大地提升了代碼的緊湊性和可讀性。5.1 Lambda的基本語(yǔ)法與排序應(yīng)用一個(gè)Lambda表達(dá)式的基本形式是[捕獲列表](參數(shù)列表) - 返回類(lèi)型 { 函數(shù)體 }。對(duì)于排序比較器通常這樣寫(xiě)std::sort(students.begin(), students.end(), [](const Student a, const Student b) - bool { return a.score b.score; } );很多時(shí)候返回類(lèi)型可以省略編譯器會(huì)自動(dòng)推導(dǎo)std::sort(students.begin(), students.end(), [](const Student a, const Student b) { return a.score b.score; } );5.2 捕獲列表連接外部世界的橋梁Lambda最強(qiáng)大的特性之一是捕獲。它允許Lambda函數(shù)體訪問(wèn)其所在作用域中的變量。[]不捕獲任何變量。[]以值的方式捕獲所有外部變量在Lambda創(chuàng)建時(shí)拷貝。[]以引用的方式捕獲所有外部變量。[var]以值的方式捕獲特定變量var。[var]以引用的方式捕獲特定變量var。[this]捕獲當(dāng)前類(lèi)對(duì)象的this指針在成員函數(shù)內(nèi)定義Lambda時(shí)使用。示例動(dòng)態(tài)排序基準(zhǔn)假設(shè)我們不想總是按分?jǐn)?shù)排序而是允許用戶選擇一個(gè)字段進(jìn)行排序。enum class SortField { ID, NAME, SCORE }; SortField currentField SortField::SCORE; std::sort(students.begin(), students.end(), [currentField](const Student a, const Student b) { switch (currentField) { case SortField::ID: return a.id b.id; case SortField::NAME: return a.name b.name; case SortField::SCORE: return a.score b.score; default: return false; } } );這里L(fēng)ambda以值拷貝的方式捕獲了currentField使得排序邏輯可以依賴運(yùn)行時(shí)狀態(tài)。5.3 Lambda與函數(shù)對(duì)象的等價(jià)關(guān)系及性能需要理解的是每個(gè)Lambda表達(dá)式在編譯器看來(lái)都會(huì)生成一個(gè)獨(dú)一無(wú)二的、匿名的函數(shù)對(duì)象類(lèi)。上面按字段排序的Lambda大致等價(jià)于編譯器生成這樣一個(gè)類(lèi)class __SomeAnonymousLambdaType { private: SortField __captured_currentField; public: __SomeAnonymousLambdaType(SortField field) : __captured_currentField(field) {} bool operator()(const Student a, const Student b) const { switch (__captured_currentField) { // ... 同樣的比較邏輯 } } };因此Lambda擁有函數(shù)對(duì)象的所有優(yōu)點(diǎn)可內(nèi)聯(lián)、可攜帶狀態(tài)同時(shí)寫(xiě)法上極其簡(jiǎn)潔。在性能上一個(gè)正確編寫(xiě)的Lambda避免不必要的捕獲、使用引用捕獲大對(duì)象通常與手寫(xiě)的函數(shù)對(duì)象一樣高效甚至因?yàn)槎x在使用處更利于編譯器進(jìn)行上下文優(yōu)化。5.4 適用場(chǎng)景與現(xiàn)代C實(shí)踐優(yōu)點(diǎn)極致簡(jiǎn)潔與局部性比較邏輯直接寫(xiě)在調(diào)用sort的地方讀者無(wú)需跳轉(zhuǎn)到文件其他部分去尋找函數(shù)定義代碼意圖一目了然。這對(duì)于簡(jiǎn)單的、一次性使用的排序規(guī)則來(lái)說(shuō)是完美的。強(qiáng)大的靈活性通過(guò)捕獲列表可以輕松引入外部狀態(tài)實(shí)現(xiàn)復(fù)雜邏輯?，F(xiàn)代C風(fēng)格是鼓勵(lì)使用的現(xiàn)代C idiom能使代碼更干凈、更易維護(hù)。缺點(diǎn)與注意事項(xiàng)復(fù)雜邏輯可讀性如果比較邏輯非常復(fù)雜例如超過(guò)10行或者有多個(gè)嵌套的條件判斷強(qiáng)行塞進(jìn)一個(gè)Lambda里會(huì)降低可讀性。這時(shí)提取成一個(gè)命名函數(shù)或函數(shù)對(duì)象是更好的選擇。捕獲陷阱懸空引用如果以引用方式[]捕獲了局部變量而Lambda的生命周期超過(guò)了該局部變量例如將Lambda存入一個(gè)函數(shù)返回的std::function中那么后續(xù)調(diào)用Lambda時(shí)引用將指向一個(gè)已被銷(xiāo)毀的對(duì)象導(dǎo)致未定義行為。不必要的拷貝如果以值方式[]捕獲了一個(gè)大型對(duì)象如std::vector會(huì)產(chǎn)生一次拷貝可能影響性能。應(yīng)使用[]或顯式指定[bigObj]來(lái)捕獲引用。調(diào)試難度匿名Lambda在調(diào)試時(shí)調(diào)用棧顯示的名字可能是編譯器生成的晦澀名稱不如命名函數(shù)直觀。最佳實(shí)踐建議我個(gè)人的習(xí)慣是對(duì)于簡(jiǎn)單明了的比較規(guī)則如一兩個(gè)字段的比較優(yōu)先使用Lambda寫(xiě)在sort調(diào)用旁邊。對(duì)于復(fù)雜的、復(fù)用的、或需要清晰命名來(lái)體現(xiàn)代碼意圖的比較規(guī)則則使用命名函數(shù)或函數(shù)對(duì)象。對(duì)于需要攜帶復(fù)雜狀態(tài)的比較使用函數(shù)對(duì)象。6. 三種方式的綜合對(duì)比與選型指南為了更直觀地對(duì)比我將三種方式的核心特性總結(jié)如下特性維度重載運(yùn)算符自定義比較函數(shù)Lambda 表達(dá)式語(yǔ)法/定義位置結(jié)構(gòu)體/類(lèi)內(nèi)部獨(dú)立的函數(shù)或函數(shù)對(duì)象類(lèi)sort調(diào)用處就地定義排序調(diào)用sort(begin, end)sort(begin, end, func)sort(begin, end, lambda)規(guī)則數(shù)量唯一一種默認(rèn)規(guī)則無(wú)限多無(wú)限多侵入性強(qiáng)需修改類(lèi)型定義無(wú)無(wú)攜帶狀態(tài)能力弱只能訪問(wèn)成員函數(shù)對(duì)象形式強(qiáng)強(qiáng)通過(guò)捕獲列表代碼可讀性調(diào)用處極簡(jiǎn)但規(guī)則定義分散規(guī)則有名稱意圖明確規(guī)則與使用處緊鄰直觀適用場(chǎng)景類(lèi)型存在固有、唯一排序規(guī)則規(guī)則復(fù)雜、需復(fù)用、或需清晰命名規(guī)則簡(jiǎn)單、臨時(shí)使用、或需捕獲上下文如何選擇一個(gè)簡(jiǎn)單的決策流這個(gè)結(jié)構(gòu)體有沒(méi)有一個(gè)絕對(duì)的、在任何上下文中都最常用的排序標(biāo)準(zhǔn)是- 考慮重載operator。例如Point按距離原點(diǎn)排序不一定。Timestamp按時(shí)間先后排序是的。排序邏輯是否非常簡(jiǎn)單比如只比較一個(gè)字段并且就在這個(gè)局部使用是- 使用Lambda表達(dá)式。代碼最緊湊。排序邏輯是否比較復(fù)雜或者需要在多個(gè)地方復(fù)用或者需要一個(gè)描述性的名字是- 使用命名函數(shù)或函數(shù)對(duì)象。排序邏輯是否需要依賴運(yùn)行時(shí)才能確定的參數(shù)或狀態(tài)是-函數(shù)對(duì)象或捕獲了狀態(tài)的Lambda是唯一選擇。在實(shí)際項(xiàng)目中Lambda表達(dá)式因其無(wú)與倫比的便利性已成為最常用、最推薦的方式。自定義比較函數(shù)特別是函數(shù)對(duì)象在實(shí)現(xiàn)復(fù)雜、可復(fù)用的比較策略時(shí)不可或缺。而重載operator則需謹(jǐn)慎使用確保你確實(shí)在定義該類(lèi)型的本質(zhì)序關(guān)系。7. 進(jìn)階話題與性能優(yōu)化陷阱掌握了基本方法后我們來(lái)看看一些更深入的問(wèn)題和實(shí)踐中容易踩的坑。7.1 嚴(yán)格弱序違反導(dǎo)致崩潰的隱形殺手這是結(jié)構(gòu)體排序中最嚴(yán)重、也最隱蔽的錯(cuò)誤。前面提到sort要求的比較器必須滿足嚴(yán)格弱序。違反這個(gè)規(guī)則sort可能會(huì)陷入無(wú)限循環(huán)、訪問(wèn)非法內(nèi)存導(dǎo)致程序崩潰。典型反例// 錯(cuò)誤試圖實(shí)現(xiàn)“按分?jǐn)?shù)降序但分?jǐn)?shù)相同時(shí)認(rèn)為兩者相等” bool badCompare(const Student a, const Student b) { return a.score b.score; // 違反了“非自反性”(aa為真)和“不對(duì)稱性” }這個(gè)函數(shù)在a.score b.score時(shí)返回true那么badCompare(a, a)也為true違反了非自反性。同時(shí)badCompare(a,b)和badCompare(b,a)在分?jǐn)?shù)相等時(shí)都為true違反了不對(duì)稱性。使用這個(gè)比較器調(diào)用sort是未定義行為。多字段排序的正確寫(xiě)法必須使用清晰的if-else if鏈或std::tie來(lái)確保邏輯完備。// 正確寫(xiě)法1if-else鏈 bool correctCompare(const Student a, const Student b) { if (a.score ! b.score) { return a.score b.score; } // 分?jǐn)?shù)不同決策結(jié)束 if (a.name ! b.name) { return a.name b.name; } // 分?jǐn)?shù)同名字不同決策結(jié)束 return a.id b.id; // 分?jǐn)?shù)、名字都相同按id升序 } // 正確寫(xiě)法2使用std::tie (C11) bool correctCompareWithTie(const Student a, const Student b) { // 注意tie創(chuàng)建的是tuple的引用比較是字典序 // 這里先比較score降序需取反再比較name最后比較id return std::tie(b.score, a.name, a.id) std::tie(a.score, b.name, b.id); // 更直觀的寫(xiě)法C11后 // return std::make_tuple(-a.score, a.name, a.id) std::make_tuple(-b.score, b.name, b.id); }std::tie將多個(gè)字段打包成std::tuple然后利用tuple已定義好的字典序比較代碼更簡(jiǎn)潔且不易出錯(cuò)。對(duì)于降序字段可以通過(guò)取負(fù)值僅限數(shù)值類(lèi)型或使用std::greater適配器來(lái)處理。7.2 性能優(yōu)化比較成本與移動(dòng)語(yǔ)義排序算法會(huì)進(jìn)行大量比較操作。如果比較操作本身很昂貴就會(huì)成為性能瓶頸。場(chǎng)景結(jié)構(gòu)體中包含一個(gè)很長(zhǎng)的字符串std::string description而比較規(guī)則需要先比較這個(gè)字符串。bool compareByDescription(const Data a, const Data b) { // 如果description很長(zhǎng)且經(jīng)常在開(kāi)頭字符就不同這個(gè)比較開(kāi)銷(xiāo)很大 return a.description b.description; }優(yōu)化思路預(yù)計(jì)算比較鍵如果排序是批處理操作可以事先提取出比較所需的鍵如description的哈希值或前綴存儲(chǔ)在一個(gè)輔助結(jié)構(gòu)里對(duì)輔助結(jié)構(gòu)排序再根據(jù)排序結(jié)果調(diào)整原數(shù)據(jù)。這屬于“Schwartzian transform”模式。使用引用避免拷貝確保比較器參數(shù)是const Data而不是Data。考慮數(shù)據(jù)布局如果頻繁排序的字段如score在結(jié)構(gòu)體中聲明順序靠后而結(jié)構(gòu)體很大可能會(huì)導(dǎo)致緩存不友好?？梢詫⒏哳l訪問(wèn)的字段放在結(jié)構(gòu)體開(kāi)頭。C11后的移動(dòng)語(yǔ)義助力在排序過(guò)程中sort可能會(huì)交換元素。如果結(jié)構(gòu)體持有資源如std::string,std::vector確保其移動(dòng)構(gòu)造函數(shù)和移動(dòng)賦值運(yùn)算符是高效且noexcept的通常編譯器生成的即可這能使sort在交換元素時(shí)使用移動(dòng)而非拷貝極大提升性能。struct Student { std::string name; // 具有高效的移動(dòng)語(yǔ)義 // ... 其他成員 // 編譯器生成的移動(dòng)操作通常就很好 };7.3 與STL容器及算法的協(xié)同你為結(jié)構(gòu)體定義的比較邏輯不僅可用于sort還能無(wú)縫用于其他STL組件std::set,std::map這些有序容器默認(rèn)使用std::lessKey即依賴operator。如果你重載了operator你的結(jié)構(gòu)體可以直接作為鍵。否則你需要為容器模板提供自定義的比較器類(lèi)型。// 使用自定義函數(shù)對(duì)象作為map的比較器 struct CompareStudentById { bool operator()(const Student a, const Student b) const { return a.id b.id; } }; std::mapStudent, int, CompareStudentById studentMap;std::lower_bound,std::upper_bound,std::equal_range這些二分查找算法同樣需要相同的比較規(guī)則。確保你傳遞給它們的比較器與容器或排序所使用的規(guī)則一致。std::priority_queue默認(rèn)構(gòu)造最大堆使用std::less這意味著它同樣依賴operator來(lái)定義“優(yōu)先級(jí)低”。如果你想按分?jǐn)?shù)最大值優(yōu)先而你的operator定義的是分?jǐn)?shù)升序那么直接使用std::priority_queueStudent就會(huì)得到最小堆。你需要仔細(xì)調(diào)整比較邏輯。理解并統(tǒng)一這些比較規(guī)則是寫(xiě)出正確、高效STL代碼的關(guān)鍵。結(jié)構(gòu)體排序不是孤立的技巧它是你駕馭C標(biāo)準(zhǔn)庫(kù)數(shù)據(jù)管理能力的一塊重要拼圖。從定義一個(gè)清晰的比較規(guī)則開(kāi)始你的數(shù)據(jù)就能在各種算法和容器中游刃有余。