在map里找一个 key有人写成std::find_if(m.begin(), m.end(), ...)十万个元素就要跑十万次比较换成m.find(key)同样十万个元素只要几十次两者名字里都有find复杂度却差了一个数量级。这篇从这条落差讲起把查找族算法的语义、返回值约定和短路口诀一次讲清重点解释这个落差的根源STL 算法只拿得到迭代器看不见容器的内部结构。1. 引子一个把 O(log n) 写成 O(n) 的反例先看一段你在真实项目里大概率见过、甚至写过的代码// 反例不要这么写在有序关联容器上用通用算法做 key 查找 // 违反了「让容器用自己的内部结构」这一原则白白把 O(log n) 退化成 O(n) // std::mapint, std::string dict{{1, one}, {2, two}, {3, three}}; // // const auto it std::find_if(dict.begin(), dict.end(), // [](const auto kv) { return kv.first 3; }); // if (it ! dict.end()) { /* ... */ } // // 正确写法容器成员函数走红黑树 // const auto it2 dict.find(3); // O(log n)不用 std::advance这段代码能编译、能跑对、单元测试也过唯一的毛病是慢std::find_if从begin()开始一个节点一个节点地走直到撞上目标而dict.find(3)从树根开始每次比较砍掉一半候选。元素越多差距越大。为什么同样的语义一个能砍半、一个只能傻走因为std::find_if的函数签名里只有两个迭代器它根本不知道背后是map、是vector、还是别的什么东西。2. 查找族算法速查表先把这一族算法的语义和返回值摊开这些细节全靠一遍一遍查文档不如记一张表算法语义复杂度返回什么典型用途find(first, last, v)找第一个等于v的元素O(n)迭代器找不到返回last无序容器 /vector里的值查找find_if(first, last, p)找第一个使谓词p为真的元素O(n)迭代器找不到返回last按条件查找最常用find_if_not(first, last, p)找第一个使谓词p为假的元素O(n)迭代器找不到返回last找「第一个不满足条件」的分界点count(first, last, v)统计等于v的元素个数O(n)difference_type整数计数count_if(first, last, p)统计使谓词为真的元素个数O(n)difference_type整数条件计数any_of(first, last, p)是否存在一个满足pO(n)短路bool「有没有」判断命中即返回all_of(first, last, p)是否全部满足pO(n)短路bool校验、断言式检查none_of(first, last, p)是否全部不满足pO(n)短路bool排除性检查adjacent_find(first, last)找第一对相邻且相等的元素O(n)迭代器指向这一对的第一个已排序区间的判重search(first, last, s_first, s_last)在区间里找子序列O(n·m)迭代器指向子序列起点找连续片段min_element/max_element找最小 / 最大元素O(n)迭代器空区间返回last极值mismatch(first1, last1, first2)找第一处不同O(n)pair迭代器, 迭代器逐元素比较、找分歧点官方文档std::find / std::find_if / std::find_if_not、std::all_of / any_of / none_of、std::count / std::count_if有一列值得单独记住min_element/max_element在空区间上返回last也就是end()不会抛异常、也不会返回空指针。所以它也遵循「和end()比」这条统一规则。空区间返回end()这件事看起来无趣但它定义了这一族算法的统一契约返回值永远是一个合法迭代器。3. 返回值契约永远和end()比std::find不抛异常、不返回指针、也不返回bool。它只有一种失败表示法返回第二个参数对整段区间来说就是end()。std::find(v.begin(), v.end(), 42) v [ 7 ][ 13 ][ 42 ][ 42 ][ 88 ][ 5 ] ↑ ↑ begin() end() ← 这是「一个元素的后面」这个位置 不指向任何元素解引用它是 UB find 返回 含义 ─────────────────────────────────────────────────────────── 指向 index 2 的迭代器第一个 42 找到了 v.end() ────────────────┐ 没找到 对子区间调用时是 last─┘ ——注意不是 nullptr ─────────────────────────────────────────────────────────── 判空必须写成 if (it ! v.end()) ✓ 不要写成 if (it) ✗ 迭代器没有 operator bool 不要写成 if (it ! nullptr) ✗ 编译不过 更不要 printf(%d, *it); ✗ 可能是 *end()UB// 反例不要这么写不检查返回值就解引用没找到时是未定义行为 // auto it std::find(v.begin(), v.end(), 42); // std::printf(%d\n, *it); // 如果 42 不存在这里读的是 end() 位置这条契约配一个可以直接跑的例子顺便把「返回的迭代器怎么换算成下标」也演示掉// find_basics.cpp — 编译: g -stdc17 -Wall -O2 find_basics.cpp -o demo #include algorithm #include cstddef #include cstdio #include vector int main() { const std::vectorint v{4, 8, 15, 16, 23, 42}; // 找到了返回指向该元素的迭代器 const auto it std::find(v.begin(), v.end(), 16); std::printf(16 在下标 %td 处前面有 %td 个元素\n, it - v.begin(), std::distance(v.begin(), it)); // 没找到返回 end()必须拿 end() 来比 const auto missing std::find(v.begin(), v.end(), 99); if (missing v.end()) { std::printf(99 不在序列里返回的就是 end()\n); } // find_if谓词换成任意条件这里是找第一个偶数 const auto first_even std::find_if(v.begin(), v.end(), [](int x) { return x % 2 0; }); std::printf(第一个偶数是 %d\n, *first_even); // find_if_not找第一个「不是偶数」的也就是第一个奇数 const auto first_odd std::find_if_not(v.begin(), v.end(), [](int x) { return x % 2 0; }); std::printf(第一个奇数是 %d\n, *first_odd); // 反向查找找最后一个 2 const std::vectorint dup{1, 2, 3, 2, 1}; const auto last_two std::find(dup.rbegin(), dup.rend(), 2); // rbegin() 找到的迭代器 .base() 指向它右边一格所以下标要减 1 std::printf(最后一个 2 的下标 %td\n, std::distance(dup.begin(), last_two.base()) - 1); }16 在下标 3 处前面有 3 个元素 99 不在序列里返回的就是 end() 第一个偶数是 4 第一个奇数是 15 最后一个 2 的下标 34. 关键对比算法看不见容器的内部结构现在回到引子里的落差。STL 的核心设计哲学叫算法与容器解耦algorithms are decoupled from containers算法只接收迭代器区间容器只提供迭代器。这样std::find一份实现能作用于vector、deque、list、set、甚至裸数组。代价是算法彻底失去了关于数据组织方式的信息。同一个「在 100000 个元素里找一个 key」的任务三条搜索路径 ① std::vectorint std::find —— 只能一格一格地走 [ 0 ][ 2 ][ 4 ][ 6 ][ 8 ] .... [ 199998 ] 一块连续内存顺序访问 ↑ ↑ ↑ ↑ ↑ ↑ 1 2 3 4 5 .... 100000 次比较最坏情况 算法手里只有 begin 和 end 两个迭代器 它不知道这块内存背后还有没有别的索引 —— 所以只能线性扫。 ② std::mapint,int::find —— 沿红黑树下降每步砍掉一半 [ 100000 ] / \ [ 50000 ] [ 150000 ] / \ / \ ... ... ... ... 树高 ≈ 2*log2(N) ≈ 34 每个节点是独立分配的一小块内存节点之间靠指针连 —— 有「指针追逐」开销 但比较次数从 100000 降到几十次N 一大这笔账立刻划算。 ③ std::unordered_mapint,int::find —— 一次哈希跳到桶 key199998 ──hash──▶ bucket[199998 % 桶数] ──▶ 命中比较 1 次 平均 O(1)代价是内存占用更大、元素无序、最坏 O(n)哈希全撞一个桶。把这条路走一遍用计数版谓词 / 计数版比较器把「到底比较了几次」量出来// member_vs_algorithm.cpp — 编译: g -stdc17 -Wall -O2 member_vs_algorithm.cpp -o demo #include algorithm #include cstddef #include cstdio #include functional #include map #include unordered_map #include vector namespace { constexpr int kSize 100000; // 元素个数 constexpr int kStep 2; // key 是 0, 2, 4, ... // 计数版比较器红黑树每次比较 key 都会经过这里 struct CountingLess { std::size_t* counter{nullptr}; bool operator()(int lhs, int rhs) const { (*counter); return lhs rhs; } }; // 计数版相等判断哈希表每次比较 key 都会经过这里 struct CountingEqual { std::size_t* counter{nullptr}; bool operator()(int lhs, int rhs) const { (*counter); return lhs rhs; } }; } // namespace int main() { const int target (kSize - 1) * kStep; // 199998最后一个 key线性扫描最坏情况 // ① 连续内存 线性扫描 std::vectorint keys; keys.reserve(kSize); for (int i 0; i kSize; i) { keys.push_back(i * kStep); } std::size_t linear_cmp 0; const auto hit std::find_if(keys.begin(), keys.end(), [linear_cmp, target](int x) { linear_cmp; return x target; }); // ② 红黑树 std::size_t tree_cmp 0; std::mapint, int, CountingLess tree(CountingLess{tree_cmp}); for (int i 0; i kSize; i) { tree.emplace(i * kStep, i); } tree_cmp 0; // 只统计查找阶段的比较不把建树算进去 const auto tree_hit tree.find(target); // ③ 哈希表 std::size_t hash_cmp 0; std::unordered_mapint, int, std::hashint, CountingEqual hash( 16, std::hashint{}, CountingEqual{hash_cmp}); for (int i 0; i kSize; i) { hash.emplace(i * kStep, i); } hash_cmp 0; const auto hash_hit hash.find(target); std::printf(数据量 N %d查找 key %d\n, kSize, target); std::printf(std::find_if 线性扫描: %zu 次比较返回 %d\n, linear_cmp, *hit); std::printf(std::map::find: ~~ 次比较返回 %d\n, tree_hit-second); std::printf(std::unordered_map::find: ~~ 次相等比较返回 %d\n, hash_hit-second); }数据量 N 100000查找 key 199998 std::find_if 线性扫描: 100000 次比较返回 199998 std::map::find: ~~ 次比较返回 99999 std::unordered_map::find: ~~ 次相等比较返回 99999后两行的具体数字用~~占位因为红黑树的比较次数取决于实现细节标准只保证 O(log n)。实测这个版本是21 次std::map和1 次std::unordered_map。但量级关系是铁定的线性扫描 100000 次红黑树几十次≈ 2·log₂N哈希表 1 次。选型不能只看复杂度还要看常数因子和内存布局场景推荐复杂度为什么元素很少几十个以内数据在连续内存里std::find/find_if线性扫描O(n) 但常数极小顺序访问能整块命中 CPU 缓存没有指针追逐此时树反而更慢元素多、需要按 key 查找容器成员findmap/setO(log n)每次比较排除一半候选比较次数与 N 呈对数关系元素多、只判断相等、不在意顺序unordered_map::find/unordered_set::find平均 O(1)一次哈希直接定位桶代价是内存更大、最坏 O(n)只想知道「有没有」any_ofO(n)命中即停短路求值跟count(...) ! 0相比少扫后半段最后一行容易忽略判断「存不存在」用any_of而不是count。count必须扫完整段区间才能给出总数any_of找到一个就立刻返回。官方文档std::map::find、std::unordered_map::find还有一条边界要注意std::find作用在std::set/std::map上也能编译、也能跑对但复杂度退化成 O(n)。容器不会拦你编译器也不会警告这是那种「代码评审时才被发现」的性能坑。同理std::find作用在std::list上不会因为链表就变快它照样一个个走。5. any_of / all_of / none_of短路求值的价值这三个算法的共同点是一旦结论确定就立刻返回不会把区间走完。区别只在「什么时候算结论确定」算法什么时候可以提前返回最坏情况扫描量any_of遇到第一个使谓词为真的元素全部一个都没命中时all_of遇到第一个使谓词为假的元素全部全部命中时none_of遇到第一个使谓词为真的元素全部一个都没命中时谓词调用次数是最好的证据。在谓词里加个计数器就能看见短路// predicates.cpp — 编译: g -stdc17 -Wall -O2 predicates.cpp -o demo #include algorithm #include cstdio #include vector namespace { int g_predicate_calls 0; // 统计谓词被调用了多少次 bool isNegative(int x) { g_predicate_calls; return x 0; } } // namespace int main() { const std::vectorint v{3, 7, -1, -5, 9, 11}; // 共 6 个元素 g_predicate_calls 0; const bool has_neg std::any_of(v.begin(), v.end(), isNegative); std::printf(any_of(有负数) %s谓词调用 %d 次\n, has_neg ? true : false, g_predicate_calls); g_predicate_calls 0; const bool all_pos std::all_of(v.begin(), v.end(), [](int x) { g_predicate_calls; return x 0; }); std::printf(all_of(全为正) %s谓词调用 %d 次\n, all_pos ? true : false, g_predicate_calls); g_predicate_calls 0; const bool none_huge std::none_of(v.begin(), v.end(), [](int x) { g_predicate_calls; return x 100; }); std::printf(none_of(全都 100) %s谓词调用 %d 次\n, none_huge ? true : false, g_predicate_calls); }any_of(有负数) true谓词调用 3 次 all_of(全为正) false谓词调用 3 次 none_of(全都 100) true谓词调用 6 次三次调用次数正好对应三种结局any_of在第 3 个元素-1命中就停了all_of同样在第 3 个元素发现反例就停了none_of没有任何元素满足「大于 100」所以老老实实扫完 6 个。只有「扫完全场」的那一次是白费的。顺带一提这三个算法在 C17 前的等价写法是std::find_if(...) ! end()之类的组合能读但意图不明显。语义明确的写法值得优先因为读代码的人一眼就知道你想问什么。6. 完整示例日志查询把上面几节拼起来结构体上的find_if、两个维度的count_if、排序后adjacent_find判重、unique去重它也不改变size()见《C erase-remove 惯用法为什么 remove 不删元素》、以及max_element找最慢请求// log_query.cpp — 编译: g -stdc17 -Wall -O2 log_query.cpp -o demo #include algorithm #include cstddef #include cstdio #include string #include utility #include vector namespace { enum class Level : int { debug 0, info 1, warn 2, error 3 }; struct LogEntry { Level level{Level::info}; std::string tag; int latency_ms{}; }; constexpr int kSlowMs 100; // 超过这个延迟就算慢请求别写魔法数字 } // namespace int main() { const std::vectorLogEntry logs{ {Level::info, db, 12}, {Level::error, db, 340}, {Level::info, net, 8}, {Level::warn, db, 55}, {Level::error, net, 210}, {Level::info, db, 12}, {Level::warn, net, 140}, }; // ① 按条件查找第一条 ERROR 日志 const auto first_error std::find_if(logs.begin(), logs.end(), [](const LogEntry e) { return e.level Level::error; }); if (first_error ! logs.end()) { std::printf(首个 ERROR: tag%s latency%dms下标 %td\n, first_error-tag.c_str(), first_error-latency_ms, first_error - logs.begin()); } // ② 两个维度分别计数 const auto error_count std::count_if(logs.begin(), logs.end(), [](const LogEntry e) { return e.level Level::error; }); const auto slow_count std::count_if(logs.begin(), logs.end(), [](const LogEntry e) { return e.latency_ms kSlowMs; }); std::printf(ERROR 条数 %td慢请求( %dms) 条数 %td\n, error_count, kSlowMs, slow_count); // ③ 判重把 (level, latency) 当签名排序后扫相邻元素 —— O(n log n) std::vectorstd::pairLevel, int signatures; signatures.reserve(logs.size()); for (const auto entry : logs) { signatures.emplace_back(entry.level, entry.latency_ms); } std::sort(signatures.begin(), signatures.end()); const auto dup std::adjacent_find(signatures.begin(), signatures.end()); if (dup ! signatures.end()) { std::printf(存在重复记录: level%d latency%dms位置 %td\n, static_castint(dup-first), dup-second, dup - signatures.begin()); } else { std::printf(没有重复记录\n); } // ④ 去重unique 只把不重复的往前挪返回新的逻辑结尾size() 不变 const auto logical_end std::unique(signatures.begin(), signatures.end()); std::printf(去重后逻辑长度 %td容器的 size() 仍是 %zu\n, std::distance(signatures.begin(), logical_end), signatures.size()); // ⑤ 极值找最慢的那条 const auto slowest std::max_element(logs.begin(), logs.end(), [](const LogEntry lhs, const LogEntry rhs) { return lhs.latency_ms rhs.latency_ms; }); std::printf(最慢请求: tag%s latency%dms\n, slowest-tag.c_str(), slowest-latency_ms); }首个 ERROR: tagdb latency340ms下标 1 ERROR 条数 2慢请求( 100ms) 条数 3 存在重复记录: level1 latency12ms位置 1 去重后逻辑长度 6容器的 size() 仍是 7 最慢请求: tagdb latency340ms三个值得回看的细节判重走的是排序 adjacent_find而不是双重循环。双重循环是 O(n²)排序是 O(n log n)而且排序后的内存是连续访问的缓存友好。这也是「先排序再处理」这套套路在 STL 里反复出现的原因。unique那行的输出暴露了size()没变 ——它不是算法写错了而是 STL 算法本来就不知道容器是什么。第 7 节会专门拆这件事。max_element传了个只比较latency_ms的 lambda默认比较器要求LogEntry有operator而这里我们只想比一个字段用 lambda 表达「比什么」比给类型加一个语义可疑的operator更好。7. 延伸阅读std::find / find_if / find_if_not — cppreference注意页面上明确写着「返回[first, last)中第一个满足条件的元素或last」这就是这篇第 3 节那条契约的原文std::all_of / std::any_of / std::none_of — cppreferenceNotes 里有一句「实现会在结论确定时短路返回」这是第 5 节可以直接依赖的行为std::count / std::count_if — cppreference想确认「count不会短路、any_of会」时对照它俩的复杂度声明看std::adjacent_find — cppreference判重套路的主角配合sort使用std::map::find — cppreference / std::unordered_map::find两个成员函数的复杂度声明放在一起看O(log n) 与平均 O(1) 的差别C Core Guidelines — SL.con.1 / 标准库算法关于「优先用标准库算法而不是手写循环」的总纲这篇第 6 节就是照这个思路组织的本知识库内的相关篇目《C 二分查找lower_bound 与 upper_bound 的精确语义》 —— lower_bound 是「第一个 value 的位置」《C erase-remove 惯用法为什么 remove 不删元素》 —— std::remove 跑完之后容器 size() 一点没变 —— 这不是 bug《C 变换算法std::transform 与 for_each 的返回值》 —— std::for_each 的返回值几乎人人都在丢 —— 但它正是取回统计结果的唯一通道8. 一句话总结查找族算法的统一契约是「返回迭代器找不到返回last永远和end()比」any_of/all_of/none_of会短路判断「有没有」优先用它们而不是count算法只看得见迭代器、看不见容器所以在map/set/unordered_map上做 key 查找必须用容器成员函数std::find上去就是 O(n)元素很少且内存连续时线性扫描的缓存优势反而可能赢过树选型要看 N 而不是背复杂度。