Chapter 26: Search Algorithms
核心问题与阅读主线
非修改查询算法将元素定位、计数、布尔命题、子序列匹配与双区间比对统一为 [first, last) 上的只读迭代器扫描;选型关键在于先定返回形态,再核对短路边界、迭代器要求与谓词成本。
全章共用代码样本(下文各节持续拆解)
贯穿本章的样本是一段写入 std::vector<Event> 的事件序列:容器只管存储与生命周期,<algorithm> 算法仅通过 [first, last) 执行只读查询:
#include <algorithm>
#include <iostream>
#include <string>
#include <string_view>
#include <vector>
struct Event {
int user_id;
std::string action;
int latency_ms;
bool valid;
};
bool operator==(const Event& lhs, const Event& rhs) {
return lhs.user_id == rhs.user_id &&
lhs.action == rhs.action &&
lhs.latency_ms == rhs.latency_ms &&
lhs.valid == rhs.valid;
}
std::vector<Event> make_events() {
return {
{7, "login", 80, true},
{7, "view", 41, true},
{7, "pay", 330, true},
{7, "confirm", 54, true},
{7, "confirm", 51, true},
{7, "logout", 20, true}
};
}
下文围绕“找事件/子序列、数数量、判布尔命题与比对基准序列”梳理 find、count、all_of、search、adjacent_find、mismatch、equal 七组顺序接口。
26.1 equality search 与 predicate search
std::find、std::find_if、std::find_if_not 均在命中时立即返回首个匹配元素的迭代器,未命中返回 last(顺序版至多比较 N 次,见 std::find, std::find_if, std::find_if_not):
| 算法 | 匹配依据 | 典型用途 |
|---|---|---|
std::find | operator== | 全字段值相等查找 |
std::find_if | 一元谓词为 true | 局部字段、阈值与复合条件 |
std::find_if_not | 一元谓词为 false | 用正向不变量定位首条违规项 |
值类型已定义完整 operator== 时使用 std::find,命中后后续元素不再访问:
void equality_search_example() {
const auto events = make_events();
const Event target{7, "pay", 330, true};
auto it = std::find(events.begin(), events.end(), target);
if (it != events.end()) {
std::cout << "matched action: " << it->action << '\n';
}
}
按局部字段筛选时传入只读一元谓词(返回可转 bool 的值);find_if_not 可直接复用 event.valid 等正向约束定位第一处失效点:
void predicate_search_example() {
const auto events = make_events();
auto first_slow = std::find_if(events.begin(), events.end(),
[](const Event& event) {
return event.latency_ms > 300;
});
auto first_invalid = std::find_if_not(events.begin(), events.end(),
[](const Event& event) {
return event.valid;
});
if (first_slow != events.end()) {
std::cout << "slow action: " << first_slow->action << '\n';
}
if (first_invalid == events.end()) {
std::cout << "all checked events are valid\n";
}
}
边界与误区
- 哨兵解引用:
last不指向有效元素,解引用或切分后续区间前必须校验it != last。 - 只读谓词:一元谓词严禁修改被检查元素或容器状态。
26.2 counting 与 boolean queries
std::count / std::count_if 返回表达迭代器距离的有符号整数 difference_type(std::count, std::count_if),std::all_of / std::any_of / std::none_of 返回 bool(std::all_of, std::any_of, std::none_of):
| 算法 | 返回值 | 遍历次数(顺序) | 空区间结果 |
|---|---|---|---|
std::count / std::count_if | difference_type | 精确 N 次(无短路) | 0 |
std::all_of | bool | 至多 N 次(遇 false 止) | true |
std::any_of | bool | 至多 N 次(遇 true 止) | false |
std::none_of | bool | 至多 N 次(遇 true 止) | true |
计数算法必须扫完全部 N 个元素才能确定总数:
void counting_example() {
const auto events = make_events();
auto confirm_count = std::count_if(events.begin(), events.end(),
[](const Event& event) {
return event.action == "confirm";
});
auto slow_count = std::count_if(events.begin(), events.end(),
[](const Event& event) {
return event.latency_ms > 300;
});
std::cout << "confirm_count=" << confirm_count
<< ", slow_count=" << slow_count << '\n';
}
布尔命题在结果确定时立即短路返回:
void boolean_query_example() {
const auto events = make_events();
const bool all_valid = std::all_of(events.begin(), events.end(),
[](const Event& event) {
return event.valid;
});
const bool has_slow_event = std::any_of(events.begin(), events.end(),
[](const Event& event) {
return event.latency_ms > 300;
});
const bool has_no_failure = std::none_of(events.begin(), events.end(),
[](const Event& event) {
return event.action == std::string_view{"fail"};
});
std::cout << all_valid << has_slow_event << has_no_failure << '\n';
}
边界与误区
- 存在性勿用
count_if(...) > 0:计数强制走完N次调用;只查“有没有”用std::any_of,需位置用std::find_if。 - 空区间空真:空区间无反例,故
all_of、none_of返回true、any_of返回false;要求“至少一条且全有效”须写!events.empty() && std::all_of(...)。
26.3 sequence search 与 adjacent_find
连续模式匹配按长度在 std::adjacent_find(std::adjacent_find)与 std::search(std::search)间选型:
| 算法 | 匹配对象 | 返回位置 | 短区间与上界 |
|---|---|---|---|
std::adjacent_find | 相邻两元素(== 或二元谓词) | 命中对前项(未中返回 last) | 长度小于 2 返回 last;至多 N - 1 对 |
std::search | 子序列 [s_first, s_last) 首次出现 | 主区间起点(未中返回 last) | 朴素双层匹配上界 N * S 次(S 为模式长) |
std::search 外层枚举主区间起点,内层比对模式区间 [s_first, s_last):
void sequence_search_example() {
const std::vector<std::string_view> actions{
"login", "view", "pay", "confirm", "confirm", "logout"
};
const std::vector<std::string_view> pattern{"pay", "confirm"};
auto it = std::search(actions.begin(), actions.end(),
pattern.begin(), pattern.end());
if (it != actions.end()) {
std::cout << "pattern starts at index "
<< std::distance(actions.begin(), it) << '\n';
}
}
std::adjacent_find 仅观察相邻元素对,适合重复事件、单调断点与状态跳转检测:
void adjacent_find_example() {
const std::vector<std::string_view> actions{
"login", "view", "pay", "confirm", "confirm", "logout"
};
auto duplicated = std::adjacent_find(actions.begin(), actions.end());
if (duplicated != actions.end()) {
std::cout << "duplicated adjacent action: " << *duplicated << '\n';
}
auto suspicious_pair = std::adjacent_find(actions.begin(), actions.end(),
[](std::string_view left, std::string_view right) {
return left == "pay" && right == "logout";
});
if (suspicious_pair == actions.end()) {
std::cout << "no pay-to-logout jump\n";
}
}
核心判断
- 按长度分流:单元素用
find,相邻二元组用adjacent_find,长度大于2或独立模式区间用search(adjacent_find仅返回一对元素的起点)。 - 长文本重复检索:朴素
search最坏N * S次比较;长模式高频检索可评估 C++17std::boyer_moore_searcher等 searcher 重载,单独权衡迭代器、预处理与比较器条件。
26.4 mismatch、equal 与 range comparison
std::mismatch(std::mismatch)与 std::equal(std::equal)同步扫描两个区间做逐位比对:
| 算法 | 返回值 | 诊断价值与长度优化 |
|---|---|---|
std::mismatch | 指向双区间首处不等元素的一对迭代器 | 精准定位首个偏离点,用于日志回放、协议解析与测试断言诊断 |
std::equal | bool(整体是否逐位一致) | 随机访问迭代器四参数版先比 last - first,长度不等直接返回 false |
C++14 四迭代器重载把第二区间的 end() 写入调用点;下例差异落在 expected 的 "logout" 与 actual 第二个 "confirm":
void mismatch_example() {
const std::vector<std::string_view> expected{
"login", "view", "pay", "confirm", "logout"
};
const std::vector<std::string_view> actual{
"login", "view", "pay", "confirm", "confirm", "logout"
};
auto diff = std::mismatch(expected.begin(), expected.end(),
actual.begin(), actual.end());
if (diff.first != expected.end() && diff.second != actual.end()) {
std::cout << "expected " << *diff.first
<< ", actual " << *diff.second << '\n';
}
}
只需整体真假时改用 std::equal:
void equal_example() {
const std::vector<std::string_view> expected{
"login", "view", "pay", "confirm", "logout"
};
const std::vector<std::string_view> actual{
"login", "view", "pay", "confirm", "confirm", "logout"
};
const bool same = std::equal(expected.begin(), expected.end(),
actual.begin(), actual.end());
std::cout << "same sequence: " << same << '\n';
}
边界与误区
- 双端长度边界:两区间长度可能不等(外部输入、网络包字段)时,优先用 C++14 四迭代器重载防止越界。
- 无序容器顺序陷阱:无序哈希容器元素相同但迭代顺序可能不同,整体判等应调用容器
operator==,而非std::equal。 - 二元谓词:自定义比较谓词须保持只读,且能接收两侧解引用后的元素类型。
26.5 复杂度和 iterator 要求
算法成本取决于短路能力、单步观察元素数与迭代器跳转能力。下图仅覆盖本章顺序查询接口(不含二分、集合与哈希查找):
| 算法族 | 最低迭代器(顺序版) | 并行策略版要求 | 比较/谓词调用次数 |
|---|---|---|---|
find / find_if / find_if_not | InputIterator | ForwardIterator | 至多 N 次(短路) |
all_of / any_of / none_of | InputIterator | ForwardIterator | 至多 N 次(短路) |
count / count_if | InputIterator | ForwardIterator | 精确 N 次 |
adjacent_find | ForwardIterator | ForwardIterator | 至多 N - 1 对(短路) |
search | ForwardIterator | ForwardIterator | 朴素至多 N * S 次(短路) |
mismatch / equal | InputIterator | ForwardIterator | 至多 min(N1, N2) 次(短路) |
单遍扫描只需 InputIterator;search、adjacent_find 需保存并回退候选起点,execution policy 并发重载需拆分重访区间,因此都要求 ForwardIterator。
边界与误区
- 谓词成本放大:算法只约束调用次数,不压缩谓词内正则、外部状态访问或临时分配开销;昂贵字段应预处理或改用哈希/排序二分。
- 谓词内修改导致失效:查询本身不使迭代器失效,但谓词若捕获容器并增删扩容会破坏遍历;修改操作须在查询返回后按容器失效规则执行。
排查顺序
- 定返回形态(迭代器 / 计数 / 布尔),杜绝
count_if(...) > 0查存在性。 - 定匹配粒度与双端边界(双区间用四迭代器重载)。
- 核对
InputIterator/ForwardIterator门槛及谓词只读性。 - 按
N或N * S乘以单次谓词耗时评估瓶颈,按需预处理或换数据结构。 - 取回迭代器后再于算法外修改容器。
最小自检任务
按“查询目标 → 返回形态 → 输出值 → 遍历上界”判断五次 std::cout 的输出:
#include <algorithm>
#include <iostream>
#include <string_view>
#include <vector>
int main() {
const std::vector<std::string_view> actions{
"login", "view", "pay", "confirm", "confirm", "logout"
};
const std::vector<std::string_view> expected{
"login", "view", "pay", "confirm", "logout"
};
auto first_confirm = std::find(actions.begin(), actions.end(), std::string_view{"confirm"});
auto confirm_count = std::count(actions.begin(), actions.end(), std::string_view{"confirm"});
bool has_fail = std::any_of(actions.begin(), actions.end(),
[](std::string_view action) {
return action == std::string_view{"fail"};
});
auto duplicated = std::adjacent_find(actions.begin(), actions.end());
auto diff = std::mismatch(expected.begin(), expected.end(),
actions.begin(), actions.end());
std::cout << (first_confirm - actions.begin()) << '\n';
std::cout << confirm_count << '\n';
std::cout << has_fail << '\n';
std::cout << (duplicated - actions.begin()) << '\n';
std::cout << (diff.first - expected.begin()) << '\n';
}
本章知识点总结
- 哨兵边界
顺序查询通过
[first, last)只读扫描,迭代器结果必须先检验it != last再解引用。 - 单元素定位
std::find匹配operator==完整值,std::find_if/std::find_if_not以只读谓词定位首处满足或违规位置(至多N次)。 - 计数与布尔短路
std::count/std::count_if精确执行N次返回difference_type;存在性与全称判断用可短路的any_of、all_of、none_of(空区间all_of/none_of为true,any_of为false)。 - 模式与相邻对
adjacent_find查相邻对(长度小于2返回last,至多N - 1对);search查子序列(朴素上界N * S,长模式重复查可用 C++17std::boyer_moore_searcher)。 - 双区间比对
mismatch定位首处差异、equal判整体相等;优先 C++14 四迭代器重载声明双端边界,无序容器判等用容器operator==。 - 迭代器与修改隔离
单遍算法接受
InputIterator,search、adjacent_find及并行策略版要求ForwardIterator;谓词须控制单次开销且严禁修改容器。