Chapter 26: Search Algorithms

查询类算法的主问题是：给定一个或两个半开区间，如何把“找值、找条件、数数量、判断布尔命题、定位子序列、比较两个区间”转换成稳定的迭代器遍历。读完本章后，读者应能先判断查询目标，再选择返回形态，再估算遍历成本和失败边界。

本章的贯穿材料是一段业务事件序列。事件按时间进入 std::vector<Event>，算法只接收迭代器区间 [first, last)。容器负责存储和生命周期，算法负责读取元素、调用比较或谓词、返回迭代器、数量或布尔值。这个边界是理解 STL 查询算法的起点。

#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}
    };
}

这段代码里有三类可观察问题：某个事件是否出现、满足条件的事件有多少、当前事件序列和基准序列在哪个位置开始不同。STL search algorithms 属于非成员算法，它们通过迭代器把这些问题统一成区间扫描。cppreference 把 find、count、all_of、search、adjacent_find、mismatch、equal 归入 <algorithm> 的非修改查询路径，本章使用这些接口建立工程判断，而不展开后续排序、二分和集合算法。

26.1 equality search 与 predicate search

std::find、std::find_if、std::find_if_not 共同回答“第一个位置在哪里”。它们返回迭代器，命中时指向第一个满足条件的元素，未命中时返回 last。这个返回形态使调用方可以继续读取元素、计算偏移、切出后续区间，或者把未命中作为分支边界。std::find 家族的基本语义和复杂度可在 std::find, std::find_if, std::find_if_not 中回溯。

equality search 的输入是目标值，元素和目标值通过 operator== 比较。这个判断适合值类型已经定义了完整相等语义的场景，例如事件结构体的全部字段都参与身份判断。下面的代码用完整 Event 值查找一次完全一致的事件：

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';
    }
}

这段代码的工程含义是：相等关系被集中到 operator==。算法不理解 Event 的业务字段，只负责从 begin 走到 end，对每个元素执行一次相等判断。命中后返回当前位置，后续元素保持未访问状态。对于顺序版本，比较次数至多为区间长度 N。

predicate search 的输入是一个一元谓词。谓词是能接收元素并返回可转换为 bool 的调用对象。它适合只按局部字段判断的场景，例如查找第一条慢请求、第一条无效事件、第一条来自指定用户的事件。谓词应只表达判断，不修改被检查元素。

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";
    }
}

find_if 把“等于某个值”的判断提升为“满足某个条件”。find_if_not 把“找第一个违反条件的位置”写成正向谓词。例如 event.valid 是稳定条件，find_if_not 返回第一条无效事件。这种写法比在调用处手写循环更能暴露查询意图，也让返回值保持标准迭代器语义。

三者的选择顺序很固定：完整值相等优先使用 find；字段条件、范围条件、复合业务条件使用 find_if；需要定位第一处条件失效使用 find_if_not。判断结束后先检查 it != last，再解引用迭代器。这个检查属于区间算法的基本安全边界，因为 last 是哨兵位置，不指向有效元素。

26.2 counting 与 boolean queries

std::count 和 std::count_if 回答“满足条件的元素有多少”。它们返回 difference_type，这是一种能表达迭代器距离的有符号整数类型。std::count 使用相等比较，std::count_if 使用谓词。cppreference 对 std::count, std::count_if 的说明给出一个关键区别：计数算法需要检查整个区间，所以比较或谓词调用次数正好是 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';
}

计数算法的输出是数量，所以它需要走完区间。即使命中第一条慢请求，count_if 仍要继续检查后续元素，因为后续元素可能继续增加计数。这个性质决定了它适合统计，不适合存在性判断。存在性判断应交给 find_if 或 any_of，这样结果确定后即可返回。

std::all_of、std::any_of、std::none_of 回答布尔命题。它们的共同输入是一元谓词，返回 bool。all_of 表达全部满足，any_of 表达至少一个满足，none_of 表达没有元素满足。三者的标准语义可在 std::all_of, std::any_of, std::none_of 中回溯。

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';
}

布尔查询的边界集中在空区间。空区间上，all_of 返回 true，any_of 返回 false，none_of 返回 true。这个结果来自逻辑命题在没有反例或没有证据时的定义。工程上使用这些算法时，应先确认空输入是否在业务上可接受。例如“所有事件都有效”在空日志上得到 true，调用方若需要“至少有一条事件且全部有效”，应把 !events.empty() 写入业务条件。

计数和布尔查询的选择顺序也很稳定：需要数量时使用 count 或 count_if；需要“有没有”时使用 any_of；需要“是否全部满足”时使用 all_of；需要“是否全部不满足某条件”时使用 none_of。用 count_if(...) > 0 表达存在性会强制完整遍历，用 any_of 能把意图和成本一起写清楚。

26.3 sequence search 与 adjacent_find

std::search 把查询对象从单个元素扩展为子序列。它在主区间 [first, last) 中查找模式区间 [s_first, s_last) 的第一次出现，返回主区间中的起始迭代器。未命中时返回 last。std::search 的基本语义、谓词重载和 C++17 searcher 重载可在 std::search 中回溯。

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';
    }
}

search 的核心约束是双层匹配。外层枚举主区间中的候选起点，内层比较模式区间。若主区间长度为 N，模式长度为 S，朴素顺序搜索的比较上界可以达到 N * S。这个上界说明 search 的成本由两个区间共同决定。短模式、短区间、一次性检查适合直接使用；长文本和长模式的重复查询可以考虑 C++17 searcher，例如 std::boyer_moore_searcher，但 searcher 的迭代器、预处理成本和比较器条件需要单独纳入设计。

std::adjacent_find 回答另一类局部序列问题：区间中是否存在一对相邻元素满足关系。默认关系是相等，也可以传入二元谓词。它返回第一对相邻元素中的前一个迭代器，未命中时返回 last。标准语义可在 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";
    }
}

adjacent_find 只观察相邻对，所以它的状态量很小：当前元素和下一个元素。长度为 0 或 1 的区间没有相邻对，结果直接是 last。长度足够时，它最多检查 N - 1 对。这个算法适合重复事件检测、单调性局部断点检测、状态机相邻跳转检测。若要查找长度大于二的模式，应回到 search，因为 adjacent_find 的返回值只代表一对元素的起点。

search 与 adjacent_find 的边界可以按模式长度判断。模式长度为 1 时，find 更直接；模式长度为 2 且关系只依赖相邻元素时，adjacent_find 更贴近意图；模式长度大于 2 或模式本身是一个区间时，search 表达完整子序列匹配。

26.4 mismatch、equal 与 range comparison

std::mismatch 和 std::equal 把查询对象从一个区间扩展为两个区间的对应元素比较。它们都按顺序推进两个迭代器，并使用相等比较或二元谓词判断当前位置是否匹配。区别在输出形态：mismatch 返回第一处差异位置，equal 返回整体是否相等。

std::mismatch 返回一对迭代器，分别指向两个区间中第一处不匹配的位置。C++14 起提供四迭代器重载，可以同时传入第二个区间的结束位置。这个重载能把两个区间的长度边界写进调用点，适合比较外部输入、网络包字段、事件序列等长度可能不同的数据。标准语义和复杂度可在 std::mismatch 中回溯。

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';
    }
}

这段代码会把第一个差异定位到 expected 的 logout 和 actual 的第二个 confirm。mismatch 的价值在诊断：它不只告诉两段序列不同，还给出第一个偏离点。日志回放、协议解析、测试断言失败报告，都适合用这个返回形态生成更短的排查路径。

std::equal 返回 bool。它适合回答整体相等性，例如当前行为序列是否和基准序列一致。C++14 的四迭代器重载会同时检查长度和对应元素。若两个区间都是 random access iterator，长度不同可以先由 last - first 得出，随后直接返回 false，无需逐元素比较。相关语义和实现提示可在 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';
}

equal 的边界在“顺序”。两个无序哈希容器即使包含相同元素，迭代顺序也可能不同，直接拿它们的迭代器区间做 equal 会把顺序差异当成结果差异。比较容器整体相等时，容器自己的 operator== 往往能表达该容器定义的相等语义；比较区间逐位相等时，std::equal 才是准确工具。

mismatch 与 equal 的选择顺序是：需要第一个差异位置，使用 mismatch；只需要整体真假，使用 equal；两个区间长度都已知，优先使用四迭代器重载；比较规则改用二元谓词时，把二元谓词传入算法。谓词仍应是纯判断，并能接受两个区间解引用后的元素类型。

26.5 复杂度和 iterator 要求

查询算法的成本由三件事决定：算法是否能在结果确定时停止、每一步需要观察几个元素、迭代器是否支持高效距离和跳转。工程判断应从输出形态开始，随后再看算法名字。返回第一个位置的算法通常有短路边界；返回数量的算法需要完整遍历；比较两个区间的算法还要检查第二个区间的边界。

下面的流程图把本章算法的选择顺序压缩成一个可复用检查路径。它只覆盖本章的顺序查询算法，不覆盖排序后二分、集合算法和哈希容器成员查找。

迭代器要求决定算法能接受哪些输入。find、count、all_of 这类单向读取算法可以使用 input iterator，因为它们只需要从前向后读取一次。search 和 adjacent_find 的传统重载需要 forward iterator，因为它们可能需要保存候选位置并重新推进。带 execution policy 的重载通常要求 forward iterator，因为并行或策略执行需要更强的遍历能力。

复杂度也要按“至多”和“正好”区分。find、find_if、any_of、all_of、none_of、mismatch、equal 这类算法在顺序语义下可以在结果确定时结束，所以常见上界是至多 N 次比较或谓词调用。count 和 count_if 为了得到完整数量，正好执行 N 次判断。search 的朴素上界是 N * S，其中 N 是主区间长度，S 是模式区间长度。

谓词和比较器的成本会直接放大总成本。若谓词执行一次需要做字符串正则匹配、访问外部状态或分配临时对象，总耗时会随着比较次数线性增长。STL 算法只承诺调用次数上界，不替调用方压缩谓词内部开销。工程上应把昂贵字段预处理到元素状态中，或者把重复查询改成索引、哈希表、排序后二分等更合适的数据结构方案。

迭代器失效在查询算法中也有边界。查询算法本身不修改容器，所以它们不会主动让容器迭代器失效。谓词若捕获容器并在判断过程中插入、删除、扩容，就会破坏当前迭代器遍历。稳定做法是让谓词保持只读，所有容器修改放在算法调用之前或之后。若需要按查询结果修改容器，应先拿到迭代器，再按照对应容器的失效规则执行修改。

本章最后给出查询算法的判断顺序：先确认问题要返回迭代器、数量还是布尔值；再确认比较对象是单元素、相邻对、子序列还是两个区间；然后检查谓词是否只读、是否能接受元素类型；接着估算遍历上界和谓词成本；最后根据容器迭代器失效规则安排后续修改。这个顺序能把算法选择从 API 记忆转成可迁移的工程判断。

最小自检任务

阅读下面代码，判断每个算法的返回值或输出含义，并说明它们各自的遍历边界。要求按本章的判断顺序回答：先说明查询目标，再说明返回形态，再说明复杂度和边界。

#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';
}

答案要点

std::find 的目标是第一个等于 "confirm" 的元素，返回迭代器。它命中 actions[3]，所以第一个输出是 3。顺序版本最多比较 N 次，本例在第 4 个元素命中后结束。

std::count 的目标是数量，返回满足相等条件的元素个数。"confirm" 出现两次，所以第二个输出是 2。计数需要完整区间，正好执行 N 次相等比较。

std::any_of 的目标是存在性布尔判断，返回 bool。区间中没有 "fail"，所以第三个输出是 0。顺序版本可以在命中时结束，本例未命中，需要检查完整区间。

std::adjacent_find 的目标是第一对相邻相等元素，返回前一个元素的迭代器。actions[3] 和 actions[4] 都是 "confirm"，所以第四个输出是 3。它最多检查 N - 1 个相邻对。

std::mismatch 的目标是两个区间的第一处差异，返回一对迭代器。expected 在索引 4 是 "logout"，actions 在索引 4 是第二个 "confirm"，所以第五个输出是 4。四迭代器重载会同时受两个区间结束位置约束，比较次数至多为两个长度的较小值。

本章知识点总结

• 查询目标：选择查询算法前先确认目标是位置、数量、布尔值、子序列起点还是区间差异。
• 半开区间：本章算法都通过 [first, last) 表达输入边界，last 表示未命中或结束哨兵。
• 相等查找：std::find 使用 operator== 查找第一个完整值匹配位置。
• 谓词查找：std::find_if 和 std::find_if_not 使用一元谓词定位第一个满足或失效位置。
• 计数算法：std::count 和 std::count_if 返回数量，因此需要完整遍历输入区间。
• 布尔查询：all_of、any_of、none_of 把区间扫描转换成全部、存在和全无三类命题。
• 空区间结果：空区间上 all_of 与 none_of 返回 true，any_of 返回 false。
• 子序列查找：std::search 在主区间中定位模式区间的第一次出现，朴素比较上界为 N * S。
• 相邻查找：std::adjacent_find 定位第一对相邻元素关系，适合重复事件和局部跳转检测。
• 差异定位：std::mismatch 返回两个区间第一处差异的位置，适合诊断序列偏离点。
• 整体相等：std::equal 返回两个区间是否逐位相等，四迭代器重载能表达双方长度边界。
• 迭代器要求：单向读取查询通常接受 input iterator，search 和 adjacent_find 需要 forward iterator。
• 谓词边界：谓词应保持只读并返回可转换为 bool 的结果，谓词内部成本会放大遍历成本。
• 修改安排：查询算法本身不修改容器，基于结果修改容器时应按对应容器的迭代器失效规则执行。