企业官网建设流程全解析

【C++ 面试真题】聊聊 C++ 的标准库常用算法

“介绍一下标准库的算法"是标准库篇的经典开场题。背得出"sort 排序、find 查找"只是及格，真考你的是"心里有没有分类地图、sort 的时间复杂度和内部实现、自己的类型怎么交给 std::sort、比较器写错会怎样、accumulate 的初值藏着什么坑、copy 到空容器为什么崩”。本文先总览分类，再从排序开始一路深入。

一、开场：标准库的算法有哪些？

❓ 介绍一下标准库的算法？

✅ 就两个头文件：<algorithm>为主，<numeric>补数值族，共十个分类。按常用程度从高到低报——排序最常用放首位，冷门的集合、堆、排列垫后：

回答思路：先报分类、每类点两三个代表——面试官立刻知道你心里有地图；他多半会挑一类深入，最常挑的是排序。

这些算法共享同一个设计：只认迭代器区间[first, last)，不认容器——sort(v.begin(), v.end())和sort(a, a + n)通吃；反过来，迭代器类别不够就用不了：list 只有双向迭代器，std::sort直接编译报错，得用成员l.sort()。

二、从排序深入：复杂度与内部实现

❓ std::sort 的时间复杂度是多少？

✅平均、最坏都是 O(n log n)。内部不是纯快排，是内省排序（introsort）：

• 快排打底——平均最快；
• 递归太深（快排退化成 O(n²) 的风险）→ 切堆排序——最坏情况有保障；
• 区间小到一定程度 → 改插入排序——小区间常数开销最小。

三个算法各取所长，就是"内省"的含义。注意 sort不稳定——相等元素可能换相对位置；要保序用stable_sort（归并实现）。

同族还有两个场景特化：

三、自定义类型怎么用 std::sort？

❓ 我自己写的 struct 想排序，怎么写？

✅ 三种方式，按需选：

方式一：给类型重载operator<——定义"天然顺序"：

structP{string name;intscore;booloperator<(constP&o)const{returnscore<o.score;}};sort(v.begin(),v.end());// 直接排

方式二：调用时传比较器（lambda）——不动类型，最灵活：

sort(v.begin(),v.end(),[](constP&a,constP&b){returna.score>b.score;});

方式三：现成仿函数——简单场景一个词搞定：

sort(v.begin(),v.end(),greater<int>{});// 降序

多字段排序就是 if 链——先比第一关键字，相等再比下一个：

[](constP&a,constP&b){if(a.score!=b.score)returna.score>b.score;returna.name<b.name;}

⚠️比较器必须严格弱序——只能写<，写<=（相等时也返回 true）会让 sort 越界崩溃，未定义行为。这是自定义排序最高频的翻车点。

💡 方式一和方式二怎么选：operator<表达"这个类型默认怎么排"（语义上唯一、天然的顺序）；lambda 表达"这一次想怎么排"的临时顺序。业务顺序常变的场景，别把每种顺序都塞进 operator<。

四、查找族：find 与 binary_search

❓ std::find 是什么复杂度？什么时候不该用它？

✅find是线性 O(n)——从头到尾逐个==。数据无序时它就是唯一选择，但有序数据用它纯属浪费：

• 有序 + 随机访问→binary_search（存在性，bool）/lower_bound（找位置），O(log n)；
• 条件查找→find_if配谓词，配any_of/all_of/none_of/count_if一家人。

⚠️最贵的事故：对关联容器用 std::find。std::find把红黑树当线性表扫，O(n) 直接干掉人家 O(log n) 的优势：

map<string,int>m;autoit=m.find("k");// ✅ 成员：红黑树 O(log n)// std::find(m.begin(),// m.end(), "k");// ❌ 自由：线性 O(n)

💡 规则：有成员版本的容器，永远优先成员版本（map/set/unordered/string 的 find、sort 等），自由算法留给序列容器。

五、搬运与整理：copy / transform / remove / unique

❓ copy 到空容器为什么崩？

✅ 因为copy假设目标区间已有足够空间，它只管往目标迭代器指的位置赋值——空容器一赋值就越界：

vector<int>src{1,2,3},dst;// copy(src.begin(), src.end(),// dst.begin()); // ❌ 崩copy(src.begin(),src.end(),back_inserter(dst));// ✅

back_inserter是插入迭代器：把"赋值"翻译成push_back，边构造边长。目标大小不确定时一律用它。

transform是"带变换的 copy"，原地翻倍或搬运皆可：

transform(v.begin(),v.end(),v.begin(),[](intx){returnx*2;});

copy 的移动版：元素大、源容器不再需要时，把 copy 换成move算法——逐元素走移动赋值，偷指针不复制内容：

vector<string>src{/* 很大 */};vector<string>dst(src.size());move(src.begin(),src.end(),dst.begin());// src 元素已变空壳

remove / unique 家族只搬不删（算法够不着容器的 size，真正删除要靠 erase 配合）：

// 排序 + 去重三件套sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());// unique 只合并"相邻"重复// 所以必须先 sort

六、数值族：accumulate / iota / reduce

❓ accumulate 有什么坑？

✅accumulate在<numeric>（不在<algorithm>），核心规则一句话：初值决定累加类型。

vector<int>v{1,2,3};ints1=accumulate(v.begin(),v.end(),0);// int// ⚠️ 初值 0 是 int：// 大数求和会溢出longlongs2=accumulate(v.begin(),v.end(),0LL);// ✅doubleavg=accumulate(v.begin(),v.end(),0.0)/v.size();// ✅

它还能做"通用折叠"——换个运算就是连乘、拼串：

string joined=accumulate(words.begin(),words.end(),string{},[](a,b){returna+b;});

同族：iota[C++11]填充 0,1,2,…；reduce[C++17]可并行版，不保证求和顺序——浮点加法不满足结合律，对精度敏感就老实用 accumulate。

找最大最小也别手写循环：标量比较用max/min；区间找用max_element/minmax_element——一次遍历同时拿最大和最小，返回的是迭代器（位置），要解引用取值：

autoit=max_element(v.begin(),v.end());intbest=*it;// 解引用取值auto[lo,hi]=minmax_element(v.begin(),v.end());

七、面试高频追问

❓ Q1：stable_sort 和 sort 怎么选？

✅ 看相等元素要不要保持原相对顺序。先按 A 字段排、再按 B 字段排想让同 B 的保持 A 序，第二次必须 stable_sort；单次排序不关心相等元素的位次，用更快的 sort。

❓ Q2：partial_sort 和 nth_element 都能做 Top-K，怎么选？

✅ 要前 k 名排好序用 partial_sort（O(n log k)）；只要"第 k 大是多少"、不要求前 k 内部有序，nth_element 更快（平均 O(n)）。

❓ Q3：为什么 remove 不真正删除元素？

✅ 算法手里只有迭代器，够不着容器的 size——缩短容器只能由容器自己（erase）完成。remove 只把要留的元素前移、返回新逻辑终点，删除交给 erase-remove 惯用法。

❓ Q4：for_each 和 range-for 怎么选？

✅ 单纯遍历用 range-for，意图直白；需要把"遍历逻辑"封装成可复用的一等公民（命名仿函数、多处复用、作为参数传递）时用 for_each。日常代码 range-for 占九成。

❓ Q5：算法能并行跑吗？

✅[C++17]起多数算法加了执行策略重载：sort(std::execution::par, first, last)由运行时多线程执行。代价是元素级并行——比较器、谓词必须是线程安全的纯函数。

❓ Q6：lower_bound 和 find 都能"找到位置"，用哪个？

✅ 看数据是否有序：有序用 lower_bound（O(log n)，返回第一个 ≥ 值的位置）；无序只能 find（O(n)）。给无序数据用 lower_bound 是逻辑错误——结果没有意义。

❓ Q7：max 和 max_element 有什么区别？

✅max比较两个值，返回较大者（值语义，还能max({a, b, c})比一串初始化列表）；max_element在区间里扫描，返回最大元素的迭代器，要解引用取值、判空区间。一个是比两数，一个是扫区间。

八、总结速查表

一句话回顾

回答"标准库算法有哪些"先亮分类地图（排序、查找、搬运、数值……每类点两个代表）；深入排序时记三条——内省排序最坏也有 O(n log n)、自定义类型靠 operator< 或 lambda、比较器必须严格弱序；再往下：关联容器用成员 find、copy 空容器配 back_inserter、accumulate 初值决定类型。

如果您觉得本篇内容对你有帮助，欢迎点赞 👍、收藏 ⭐、转发 📢。下期我们继续标准库篇，聊 std::function——它是怎么统一各种可调用物的，和 C 函数指针、虚函数回调相比强在哪，敬请关注 👋