一、前言為什么STL算法是刷題開(kāi)發(fā)神器在前面我們徹底吃透了C語(yǔ)法、面向?qū)ο蟆⒅悄苤羔?、模板、STL所有容器。容器負(fù)責(zé)存數(shù)據(jù)算法負(fù)責(zé)處理數(shù)據(jù)二者結(jié)合才是完整的STL體系。在算法刷題和企業(yè)開(kāi)發(fā)中手寫排序、查找、去重、遍歷不僅代碼冗余、效率低下還極易出現(xiàn)邊界BUG。而STL算法庫(kù)是官方高度優(yōu)化、經(jīng)過(guò)千萬(wàn)項(xiàng)目驗(yàn)證、底層極致優(yōu)化的通用算法庫(kù)?？梢赃@么說(shuō)熟練掌握STL算法能讓你的刷題速度翻倍工程代碼量減半。很多開(kāi)發(fā)者只會(huì)簡(jiǎn)單sort排序不懂二分查找、unique去重、條件篩選、批量變換遇到復(fù)雜場(chǎng)景依舊手寫邏輯低效且易錯(cuò)。本篇文章一次性講透STL所有高頻算法包含底層原理、標(biāo)準(zhǔn)寫法、自定義規(guī)則、Lambda適配、全網(wǎng)踩坑點(diǎn)零基礎(chǔ)一站式通關(guān)徹底閉環(huán)STL所有知識(shí)點(diǎn)二、STL算法整體分類與核心特性2.1 算法五大分類1.遍歷算法批量處理容器所有元素for_each2.排序算法無(wú)序序列重排sort3.查找算法精準(zhǔn)查找、條件查找、二分查找4.修改算法去重、替換、反轉(zhuǎn)、拷貝、合并5.統(tǒng)計(jì)算法最值查找、元素計(jì)數(shù)、條件統(tǒng)計(jì)2.2 核心通用規(guī)則必考1. STL算法不依賴容器全部通過(guò)迭代器操作數(shù)據(jù)適配所有STL容器2. 算法左閉右開(kāi)[begin, end)包含起始迭代器不包含末尾迭代器3. 所有算法支持自定義規(guī)則函數(shù)指針、仿函數(shù)、Lambda表達(dá)式4. 算法不會(huì)改變?nèi)萜魅萘績(jī)H修改元素內(nèi)容或順序。三、遍歷算法for_each 萬(wàn)能遍歷for_each 是STL通用遍歷算法替代傳統(tǒng)for循環(huán)支持遍歷過(guò)程自定義操作適配所有容器。3.1 基礎(chǔ)語(yǔ)法for_each(起始迭代器, 末尾迭代器, 處理函數(shù));3.2 實(shí)戰(zhàn)代碼三種遍歷方式#include iostream #include vector #include algorithm using namespace std; // 普通函數(shù)遍歷 void print(int val) { cout val ; } int main() { vectorint v {1,2,3,4,5}; // 1. 普通函數(shù)遍歷 for_each(v.begin(), v.end(), print); cout endl; // 2. Lambda表達(dá)式遍歷工程最常用 for_each(v.begin(), v.end(), [](int val){ cout val * 2 ; }); return 0; }優(yōu)勢(shì)遍歷邏輯與業(yè)務(wù)解耦支持批量自定義處理代碼更簡(jiǎn)潔優(yōu)雅。四、排序算法sort底層原理與自定義排序sort是STL最核心、最高頻的算法也是面試必考底層原理。4.1 sort底層原理面試滿分答案STL sort并非單一排序算法是三者結(jié)合的混合排序1. 數(shù)據(jù)量較大快速排序分區(qū)排序效率最高2. 數(shù)據(jù)量較小小于16個(gè)元素插入排序小數(shù)組常數(shù)時(shí)間更優(yōu)3. 遞歸深度過(guò)深堆排序防止快排最壞情況棧溢出整體時(shí)間復(fù)雜度穩(wěn)定O(nlogn)是工業(yè)級(jí)最優(yōu)排序算法。4.2 默認(rèn)升序排序vectorint v {5,2,9,1,3}; sort(v.begin(), v.end()); // 默認(rèn)升序1 2 3 5 94.3 自定義降序 結(jié)構(gòu)體排序工程剛需#include iostream #include vector #include algorithm using namespace std; struct Person { string name; int age; }; int main() { vectorPerson vp {{張三,18},{李四,20},{王五,16}}; // 自定義規(guī)則按年齡降序 sort(vp.begin(), vp.end(), [](const Person p1, const Person p2){ return p1.age p2.age; }); for(auto p : vp) { cout p.name p.age endl; } return 0; }核心規(guī)則比較函數(shù)返回 true 表示「第一個(gè)元素應(yīng)該排在第二個(gè)元素前面」。五、查找算法find / find_if / binary_search5.1 find 精準(zhǔn)值查找用于普通容器遍歷查找時(shí)間復(fù)雜度 O(n)找到返回迭代器失敗返回 end()vectorint v {10,20,30,40}; auto it find(v.begin(), v.end(), 30); if(it ! v.end()) { cout 找到元素 *it endl; } vectorint v {10,20,30,40}; auto it find(v.begin(), v.end(), 30); if(it ! v.end()) { cout 找到元素 *it endl; }5.2 find_if 條件查找高階用法無(wú)需精準(zhǔn)匹配根據(jù)自定義條件查找極大提升靈活度// 查找第一個(gè)大于20的元素 auto it find_if(v.begin(), v.end(), [](int val){ return val 20; });5.3 binary_search 二分查找高效O(logn)硬性前提容器必須有序僅返回bool值判斷元素是否存在不返回迭代器效率遠(yuǎn)高于findsort(v.begin(), v.end()); bool flag binary_search(v.begin(), v.end(), 30);六、去重算法unique全網(wǎng)最標(biāo)準(zhǔn)寫法unique是刷題最高頻、坑最多的去重算法90%開(kāi)發(fā)者都會(huì)用錯(cuò)。6.1 unique核心原理1. unique不會(huì)直接刪除元素僅將重復(fù)元素后置2. 返回值是去重后有效區(qū)間的末尾迭代器3.必須先排序再去重否則只能去除相鄰重復(fù)元素。6.2 徹底去重標(biāo)準(zhǔn)代碼模板直接復(fù)用vectorint v {2,2,1,1,3,3,2}; // 1. 先排序 sort(v.begin(), v.end()); // 2. 去重移位獲取有效末尾 auto new_end unique(v.begin(), v.end()); // 3. 真正刪除冗余元素 v.erase(new_end, v.end()); // 結(jié)果1 2 3必考口訣先排序、再去重、最后erase刪除七、最值與計(jì)數(shù)算法7.1 最值查找 max_element / min_elementvectorint v {5,1,9,3,7}; int max_val *max_element(v.begin(), v.end()); int min_val *min_element(v.begin(), v.end());7.2 元素計(jì)數(shù) count / count_if// 統(tǒng)計(jì)元素2的個(gè)數(shù) int cnt1 count(v.begin(), v.end(), 2); // 統(tǒng)計(jì)大于5的元素個(gè)數(shù) int cnt2 count_if(v.begin(), v.end(), [](int val){return val 5;});八、常用變換算法反轉(zhuǎn)/替換/拷貝/合并8.1 reverse 反轉(zhuǎn)序列reverse(v.begin(), v.end()); // 整體反轉(zhuǎn)容器元素8.2 replace 元素替換replace(v.begin(), v.end(), 2, 99); // 所有2替換為998.3 copy 容器拷貝vectorint v2(10); copy(v.begin(), v.end(), v2.begin());8.4 merge 有序合并兩個(gè)有序序列合并為一個(gè)有序序列vectorint a {1,3,5}; vectorint b {2,4,6}; vectorint res(6); merge(a.begin(),a.end(),b.begin(),b.end(),res.begin());九、算法三大適配方式函數(shù)指針、仿函數(shù)、LambdaSTL算法的強(qiáng)大之處在于支持自定義規(guī)則三種適配方式全覆蓋9.1 函數(shù)指針簡(jiǎn)單場(chǎng)景9.2 仿函數(shù)復(fù)雜帶狀態(tài)場(chǎng)景9.3 Lambda表達(dá)式工程首選、最簡(jiǎn)C11后全部?jī)?yōu)先使用Lambda代碼內(nèi)聯(lián)、簡(jiǎn)潔、無(wú)需額外定義函數(shù)/類是目前工業(yè)界統(tǒng)一規(guī)范。十、全網(wǎng)高頻踩坑合集必看避坑坑1unique不去重?cái)?shù)據(jù)毫無(wú)變化忘記先排序unique只能去除相鄰重復(fù)無(wú)序序列必須先sort再去重。坑2binary_search無(wú)序數(shù)組查找二分查找依賴有序區(qū)間無(wú)序數(shù)組使用直接邏輯錯(cuò)誤查找結(jié)果錯(cuò)亂。坑3sort自定義比較函數(shù)寫反邏輯比較函數(shù)返回值邏輯顛倒導(dǎo)致升序變降序、排序錯(cuò)亂刷題高頻BUG。坑4忽略算法左閉右開(kāi)區(qū)間遍歷、查找、操作區(qū)間不包含end迭代器截取子序列極易越界。坑5find失敗后直接解引用未判斷迭代器是否為end就取值直接野指針崩潰。十一、大廠面試滿分標(biāo)準(zhǔn)答案Q1STL sort底層采用什么排序?yàn)槭裁葱阅軜O強(qiáng)STL sort是自適應(yīng)混合排序大數(shù)據(jù)量使用快速排序小數(shù)據(jù)量小于16使用插入排序遞歸過(guò)深觸發(fā)堆排序兜底。綜合三者優(yōu)勢(shì)規(guī)避了快排最壞情況、插入排序大數(shù)據(jù)低效的問(wèn)題整體時(shí)間復(fù)雜度穩(wěn)定O(nlogn)是工業(yè)級(jí)最優(yōu)排序?qū)崿F(xiàn)。Q2unique去重為什么必須先排序unique的去重邏輯僅掃描并移除相鄰重復(fù)元素?zé)o序容器中重復(fù)元素分散無(wú)法全部去除先排序可讓所有重復(fù)元素相鄰聚集配合unique移位erase刪除實(shí)現(xiàn)真正全局去重。Q3find和binary_search的區(qū)別find是線性查找O(n)復(fù)雜度適配所有容器返回元素迭代器binary_search是二分查找O(logn)復(fù)雜度僅適用于有序容器僅返回是否存在的布爾值查找效率遠(yuǎn)高于線性查找。Q4STL算法和手寫算法相比有什么優(yōu)勢(shì)STL算法經(jīng)過(guò)官方極致優(yōu)化、邊界完備、無(wú)BUG、通用性強(qiáng)、適配所有容器手寫算法容易出現(xiàn)邊界問(wèn)題、邏輯漏洞、性能低效且代碼冗余工程開(kāi)發(fā)與刷題優(yōu)先使用STL原生算法。Q5Lambda表達(dá)式在STL算法中的作用用于快速自定義算法規(guī)則替代傳統(tǒng)函數(shù)指針和仿函數(shù)代碼內(nèi)聯(lián)簡(jiǎn)潔、可讀性高、靈活度強(qiáng)是目前C工程開(kāi)發(fā)STL算法自定義規(guī)則的首選方式。十二、今日總結(jié)徹底通關(guān)C STL全套算法體系完成C基礎(chǔ)進(jìn)階STL全閉環(huán)? STL算法整體架構(gòu)、分類與通用迭代器規(guī)則? for_each萬(wàn)能遍歷、多方式自定義處理? sort混合排序底層原理、升降序結(jié)構(gòu)體自定義排序? 線性查找二分查找全套場(chǎng)景適配? unique去重底層邏輯、全網(wǎng)標(biāo)準(zhǔn)去重模板? 最值、計(jì)數(shù)、反轉(zhuǎn)、替換、合并高頻算法實(shí)戰(zhàn)? Lambda適配算法、工程最優(yōu)編碼規(guī)范? 高頻踩坑點(diǎn)與面試滿分答題思路至此C從零基礎(chǔ)語(yǔ)法到STL全套高階內(nèi)容全部學(xué)完具備完整的刷題、開(kāi)發(fā)、面試能力