非变异算法
定义与作用
非变异算法(non-modifying algorithms)不修改容器中的元素,仅执行查找、计数、比较和遍历等只读操作。这些算法位于 <algorithm> 和 <numeric> 头文件中。
#include <algorithm>
#include <numeric>
std::vector<int> v{1, 3, 5, 7, 9};
auto it = std::find(v.begin(), v.end(), 5); // 查找
auto n = std::count(v.begin(), v.end(), 3); // 计数
核心原理
常用非变异算法分类
完整示例
示例一:飞翔科技招聘筛选系统
场景说明:白歌用非变异算法为飞翔科技筛选候选人简历。
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
struct Candidate {
std::string name;
int score;
int experience; // 经验年限
std::string skill;
};
void printCandidates(const std::string& title,
const std::vector<Candidate>& candidates) {
std::cout << title << ":\n";
for (const auto& c : candidates)
std::cout << " " << c.name << " | 分数:" << c.score
<< " | 经验:" << c.experience << "年"
<< " | 技能:" << c.skill << "\n";
}
int main() {
std::vector<Candidate> pool = {
{"大翔", 98, 8, "C++"},
{"白歌", 95, 10, "架构设计"},
{"小崔", 92, 5, "后端开发"},
{"黄俪", 90, 4, "前端开发"},
{"李眉", 88, 7, "运维"},
{"孔蓝", 87, 5, "产品"},
{"赵鸣", 85, 3, "运营"},
{"孙鹤", 82, 1, "产品助理"},
};
// 1. find:精确查找
auto it = std::find_if(pool.begin(), pool.end(),
[](const Candidate& c) { return c.name == "白歌"; });
if (it != pool.end())
std::cout << "[find] 找到: " << it->name << ", 分数: " << it->score << "\n";
// 2. count:统计
int senior = std::count_if(pool.begin(), pool.end(),
[](const Candidate& c) { return c.experience >= 5; });
std::cout << "[count] 高级人才(>=5年): " << senior << " 人\n";
// 3. search:子序列匹配
std::vector<std::string> targetSkills{"C++", "架构设计"};
// 查找连续两个候选人技能匹配 targetSkills
auto searchIt = std::search(pool.begin(), pool.end(),
targetSkills.begin(), targetSkills.end(),
[](const Candidate& c, const std::string& skill) {
return c.skill == skill;
});
if (searchIt != pool.end())
std::cout << "[search] 技能序列匹配起点: " << searchIt->name << "\n";
// 4. equal:比较两组数据
std::vector<int> expectedScores{98, 95, 92, 90};
std::vector<int> actualScores;
for (const auto& c : pool) actualScores.push_back(c.score);
bool scoresMatch = std::equal(expectedScores.begin(),
expectedScores.end(), actualScores.begin());
std::cout << "[equal] 分数匹配预期: " << std::boolalpha << scoresMatch << "\n";
// 5. all_of / any_of / none_of
bool allQualified = std::all_of(pool.begin(), pool.end(),
[](const Candidate& c) { return c.score >= 80; });
bool hasSenior = std::any_of(pool.begin(), pool.end(),
[](const Candidate& c) { return c.experience >= 10; });
std::cout << "[all_of] 全部 >= 80 分: " << allQualified << "\n";
std::cout << "[any_of] 有经验 >= 10 年: " << hasSenior << "\n";
// 6. minmax_element
auto [minIt, maxIt] = std::minmax_element(pool.begin(), pool.end(),
[](const Candidate& a, const Candidate& b) {
return a.score < b.score;
});
std::cout << "[minmax] 最低: " << minIt->name << "(" << minIt->score
<< "), 最高: " << maxIt->name << "(" << maxIt->score << ")\n";
}
预期输出:
[find] 找到: 白歌, 分数: 95
[count] 高级人才(>=5年): 4 人
[search] 技能序列匹配起点: 大翔
[equal] 分数匹配预期: true
[all_of] 全部 >= 80 分: true
[any_of] 有经验 >= 10 年: true
[minmax] 最低: 孙鹤(82), 最高: 大翔(98)
逐段分析:
find_if返回指向第一个满足谓词的元素,未找到返回end()count_if统计满足谓词的元素数量search在序列中查找子序列(支持自定义比较器)equal比较两段区间是否完全相等all_of/any_of/none_of(C++11)提供快捷的条件判断minmax_element(C++11)一次遍历同时获取最小和最大值
示例二:for_each 日志审计
场景说明:李眉用 for_each 对飞翔科技运维日志批量标记审计信息。
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
struct LogEntry {
std::string timestamp;
std::string level;
std::string message;
bool audited = false;
};
int main() {
std::vector<LogEntry> logs = {
{"2026-06-14 09:00", "INFO", "飞翔科技-服务启动"},
{"2026-06-14 09:05", "WARN", "飞翔科技-内存使用 85%"},
{"2026-06-14 09:10", "ERROR", "飞翔科技-数据库连接超时"},
{"2026-06-14 09:15", "INFO", "飞翔科技-用户登录: 孔蓝"},
{"2026-06-14 09:20", "ERROR", "飞翔科技-支付回调失败"},
};
int errorCount = 0;
// for_each:遍历并执行操作(不修改容器,但可修改元素属性)
std::for_each(logs.begin(), logs.end(),
[&errorCount](LogEntry& entry) {
entry.audited = true;
if (entry.level == "ERROR") {
++errorCount;
entry.message += " [需紧急处理]";
} else if (entry.level == "WARN") {
entry.message += " [关注]";
}
});
std::cout << "=== 飞翔科技日志审计 ===\n";
std::cout << "总共 " << logs.size() << " 条,ERROR " << errorCount << " 条\n\n";
for (const auto& log : logs) {
std::cout << log.timestamp << " [" << log.level << "] "
<< log.message;
std::cout << " (audited: " << log.audited << ")\n";
}
}
预期输出:
=== 飞翔科技日志审计 ===
总共 5 条,ERROR 2 条
2026-06-14 09:00 [INFO] 飞翔科技-服务启动 (audited: true)
2026-06-14 09:05 [WARN] 飞翔科技-内存使用 85% [关注] (audited: true)
2026-06-14 09:10 [ERROR] 飞翔科技-数据库连接超时 [需紧急处理] (audited: true)
2026-06-14 09:15 [INFO] 飞翔科技-用户登录: 孔蓝 (audited: true)
2026-06-14 09:20 [ERROR] 飞翔科技-支付回调失败 [需紧急处理] (audited: true)
逐段分析:
for_each对每个元素执行回调,可以修改元素属性(不修改容器结构)- Lambda 捕获
errorCount引用,在遍历中累积统计 - 相比原始 for 循环,
for_each语义更清晰——明确表达"对每个元素做某事"
易错场景与面试考点
易错场景
1. find 未找到时解引用
auto it = std::find(v.begin(), v.end(), 999);
// std::cout << *it; // ❌ 如果 it == end(),解引用是未定义行为
if (it != v.end()) std::cout << *it; // ✅
2. equal 第二区间必须至少和第一区间等长
std::vector<int> a{1, 2, 3, 4};
std::vector<int> b{1, 2};
// std::equal(a.begin(), a.end(), b.begin()); // ❌ b 不够长
3. minmax 参数类型一致
auto result = std::min(5, 3.14); // ❌ 编译错误!int vs double
auto result2 = std::min<double>(5, 3.14); // ✅ 显式指定类型
面试考点
| 考点 | 要点 |
|---|---|
| for_each vs range-for | for_each 可配合并行策略(C++17),语义明确 |
| find vs binary_search | find O(n),binary_search 需有序 O(log n) |
| search 复杂度 | O(n*m),最坏情况下的朴素匹配 |
| equal vs mismatch | equal 返回 bool,mismatch 返回差异位置 |
| minmax_element | C++11,一次遍历比分别调用两次高效 |
| all_of/any_of/none_of | C++11,空区间:all_of=true, any_of=false, none_of=true |