C++17 详解 22 — search 和字符串匹配

本文为 《C++17 in detail》 一书的中文渣中渣译文，不足之处还望指正。

翻译太特么累人了……剩余部分还是只做摘要翻译吧。

11. search 和字符串匹配

11.1 新算法

C++17 从两方面更新了 std::search

• 指定执行策略以通过并行方式运行默认算法版本
• 提供 Searcher 对象（译注：即三种算法）处理查找

译注：执行策略是 STL 算法通用的更新特性，后边有专门的一章讲解，所以本章只介绍了 searcher。

三种 searcher：

• default_searcher：行为同 C++17 之前，通常采用最朴素的方案（译注：即逐元素遍历比较）。对前向迭代器可用。
• boyer_moore_searcher：使用 Boyer–Moore 算法，有两个规则：坏字符规则和好后缀规则。对随机访问迭代器可用。
• boyer_moore_horspool_searcher：B.M. 算法的简化版本，只使用坏字符规则，但仍然具有很好的平均复杂度。对随机访问迭代器可用。

std::search 中 searcher 和 执行策略不能共存。

函数原型：

template<class ForwardIterator, class Searcher>
ForwardIterator search(ForwardIterator first, ForwardIterator last,
                       const Searcher& searcher);

searcher 示例：

string testString = "Hello Super World";
string needle = "Super";
const auto it = search(begin(testString), end(testString),
                       boyer_moore_searcher(begin(needle), end(needle));
                       
if (it == cend(testString))
    cout << "The string " << needle << " not found\n";

译注：B.M. 或其它高阶查找算法，大都是以空间换时间的思路。比如，以额外空间存储要查找字符串的字符集合。所以要求 searcher 是一个类对象，以存储这些额外信息。