Skip to main content

Chapter 26: Search Algorithms

核心问题与阅读主线

本章导读5 个核心小节 · 附自检与总结

非修改查询算法将元素定位、计数、布尔命题、子序列匹配与双区间比对统一为 [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::findoperator==全字段值相等查找
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_ifdifference_type精确 N 次(无短路)0
std::all_ofbool至多 N 次(遇 false 止)true
std::any_ofbool至多 N 次(遇 true 止)false
std::none_ofbool至多 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++17 std::boyer_moore_searcher 等 searcher 重载,单独权衡迭代器、预处理与比较器条件。

26.4 mismatch、equal 与 range comparison​

std::mismatch(std::mismatch)与 std::equal(std::equal)同步扫描两个区间做逐位比对:

算法返回值诊断价值与长度优化
std::mismatch指向双区间首处不等元素的一对迭代器精准定位首个偏离点,用于日志回放、协议解析与测试断言诊断
std::equalbool(整体是否逐位一致)随机访问迭代器四参数版先比 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_notInputIteratorForwardIterator至多 N 次(短路)
all_of / any_of / none_ofInputIteratorForwardIterator至多 N 次(短路)
count / count_ifInputIteratorForwardIterator精确 N 次
adjacent_findForwardIteratorForwardIterator至多 N - 1 对(短路)
searchForwardIteratorForwardIterator朴素至多 N * S 次(短路)
mismatch / equalInputIteratorForwardIterator至多 min(N1, N2) 次(短路)

单遍扫描只需 InputIterator;search、adjacent_find 需保存并回退候选起点,execution policy 并发重载需拆分重访区间,因此都要求 ForwardIterator。

边界与误区

注意
  • 谓词成本放大:算法只约束调用次数,不压缩谓词内正则、外部状态访问或临时分配开销;昂贵字段应预处理或改用哈希/排序二分。
  • 谓词内修改导致失效:查询本身不使迭代器失效,但谓词若捕获容器并增删扩容会破坏遍历;修改操作须在查询返回后按容器失效规则执行。

排查顺序

  1. 定返回形态(迭代器 / 计数 / 布尔),杜绝 count_if(...) > 0 查存在性。
  2. 定匹配粒度与双端边界(双区间用四迭代器重载)。
  3. 核对 InputIterator / ForwardIterator 门槛及谓词只读性。
  4. 按 N 或 N * S 乘以单次谓词耗时评估瓶颈,按需预处理或换数据结构。
  5. 取回迭代器后再于算法外修改容器。

最小自检任务​

动手自检先独立判断

按“查询目标 → 返回形态 → 输出值 → 遍历上界”判断五次 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++17 std::boyer_moore_searcher)。

  • 双区间比对

    mismatch 定位首处差异、equal 判整体相等;优先 C++14 四迭代器重载声明双端边界,无序容器判等用容器 operator==。

  • 迭代器与修改隔离

    单遍算法接受 InputIterator,search、adjacent_find 及并行策略版要求 ForwardIterator;谓词须控制单次开销且严禁修改容器。