搜索器

1. 搜索器概述

在 C++17 之前，如果我们想在一个字符串中查找子串，通常使用 std::string::find。虽然它很简单，但有几个明显的局限性：

  1. 算法单一：C++ 标准库只提供了简单的朴素算法（逐个字符比较）。
  2. 无法指定算法：如果你想用更高效的算法（如 KMP 或 Boyer-Moore），必须自己实现或寻找第三方库。
  3. 无法用于容器：find 是 std::string 的成员函数，不能直接用于 std::vector<char> 或其他容器。
  4. 接口不统一：字符串查找和泛型算法（如 std::search）的接口不一致。

C++17 引入了搜索器概念。它允许我们把 搜索算法 和 搜索操作 分离开来。现在，标准库里直接提供了Boyer-Moore 和 Boyer-Moore-Horspool 这两个高性能算法！

C++17 在 <functional> 头文件里引入了三种搜索器，每种都基于不同的算法：

  1. std::default_searcher：
    • 算法：就是标准库原来用的那种朴素算法。
    • 用途：默认选项，短字符串用它足够了。
  2. std::boyer_moore_searcher：
    • 算法：Boyer-Moore 算法。工业界最强悍的字符串搜索算法之一。
    • 特点：对于短模式不友好，预处理慢，但长文本搜索极快。
  3. std::boyer_moore_horspool_searcher：
    • 算法：Boyer-Moore 的简化版（BM-Horspool）。
    • 特点：预处理比标准的 BM 快，通常性能也非常好，实际应用中往往比标准 BM 更受欢迎。

这些搜索器是可调用对象（类重载了 operator()），可以传递给 std::search 算法使用。使用时需要包含头文件：

1
2
#include <functional> // 搜索器定义在这里
#include <algorithm>  // std::search 定义在这里

std::search函数原型：

1
2
template< class ForwardIt, class Searcher >
ForwardIt search(ForwardIt first, ForwardIt last, const Searcher& searcher);
  • first, last：要搜索的原始字符串的起始位置和结束位置对应的迭代器，区间为左闭右开
  • searcher：指定的搜索器

注意：std::search 是 C++17 之前就有的，但在 C++17 中，它增加了一个重载版本，专门接收搜索器对象。

搜索器类构造函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
default_searcher(ForwardIt pat_first,
                  ForwardIt pat_last,
                  BinaryPredicate pred = BinaryPredicate());

boyer_moore_searcher(RandomIt1 pat_first,
                      RandomIt1 pat_last,
                      Hash hf = Hash(),
                      BinaryPredicate pred = BinaryPredicate());

boyer_moore_horspool_searcher(RandomIt1 pat_first,
                               RandomIt1 pat_last,
                               Hash hf = Hash(),
                               BinaryPredicate pred = BinaryPredicate());
  • pat_first, pat_last：要搜索的子字符串的起始位置和结束位置对应的迭代器，区间为左闭右开
  • hf：一个可调用对象，用于对字符串元素进行哈希
  • pred：一个可调用对象，用于确定相等性

让我们通过一个具体例子来展示搜索器的使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <string>
#include <vector>
#include <functional> 

int main() 
{
    // 1. 准备数据
    std::string hay = "This is a long string containing the substring 'algorithm' at the end.";
    std::string needle = "algorithm";

    // 2. 创建搜索器
    std::boyer_moore_searcher searcher(needle.begin(), needle.end());

    // 3. 执行搜索
    auto it = std::search(hay.begin(), hay.end(), searcher);

    // 4. 判断结果
    if (it != hay.end()) 
    {
        std::cout << "找到了！位置: " << std::distance(hay.begin(), it) << std::endl;
    } 
    else 
    {
        std::cout << "没找到" << std::endl;
    }

    return 0;
}

2. 实际应用

2.1 大文件搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <functional>
#include <iostream>
#include <string>
#include <vector>
#include <fstream>

class MultiPatternSearcher 
{
public:
    MultiPatternSearcher(const std::vector<std::string>& patterns) 
        : m_patterns(patterns) {}
    
    // 使用 Boyer-Moore 搜索所有模式
    std::vector<std::pair<std::string, size_t>> search_in_file(const std::string& filename) 
    {
        std::vector<std::pair<std::string, size_t>> results;
        std::ifstream file(filename);
        
        if (!file) 
        {
            throw std::runtime_error("Cannot open file: " + filename);
        }
        
        // 读取整个文件
        std::string content((std::istreambuf_iterator<char>(file)), std::istreambuf_iterator<char>());
        
        // 对每个模式进行搜索
        for (const auto& pattern : m_patterns) 
        {
            auto searcher = std::boyer_moore_searcher(pattern.begin(), pattern.end());
            
            auto it = content.begin();
            while (it != content.end()) 
            {
                auto result = std::search(it, content.end(), searcher);
                if (result != content.end()) 
                {
                    size_t pos = std::distance(content.begin(), result);
                    results.emplace_back(pattern, pos);
                    it = result + 1;  // 继续搜索
                } 
                else 
                {
                    break;
                }
            }
        }
        
        return results;
    }

private:
    std::vector<std::string> m_patterns;
};

int main() 
{
    // 定义要搜索的多个关键词
    std::vector<std::string> keywords = {"ERROR", "WARNING", "FATAL", "CRITICAL"};
    
    MultiPatternSearcher searcher(keywords);
    
    try 
    {
        auto results = searcher.search_in_file("logfile.txt");
        
        std::cout << "Found " << results.size() << " occurrences:\n";
        for (const auto& [pattern, position] : results) 
        {
            std::cout << "  '" << pattern << "' at position " << position << std::endl;
        }
    } 
    catch (const std::exception& e) 
    {
        std::cerr << "Error: " << e.what() << std::endl;
    }
    
    return 0;
}

2.2 自定义数据类型搜索

搜索器不仅可以搜索字符串，还可以搜索任意序列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <functional>
#include <iostream>
#include <vector>
#include <algorithm>

struct Person 
{
    int id;
    std::string name;
    int age;
    
    // 相等运算符，用于搜索比较
    bool operator==(const Person& other) const 
    {
        return id == other.id && name == other.name && age == other.age;
    }
};

int main() 
{
    // 创建人员数据库
    std::vector<Person> database = 
    {
        {1, "Alice", 30},
        {2, "Bob", 25},
        {3, "Charlie", 35},
        {4, "David", 28},
        {5, "Eve", 32}
    };
    
    // 要搜索的人员序列
    std::vector<Person> search_pattern = 
    {
        {2, "Bob", 25},
        {3, "Charlie", 35}
    };
    
    // 创建搜索器
    auto searcher = std::default_searcher(search_pattern.begin(), search_pattern.end());
    
    // 执行搜索
    auto result = std::search(database.begin(), database.end(), searcher);
    
    if (result != database.end()) 
    {
        std::cout << "Pattern found at position: " 
                  << std::distance(database.begin(), result) << std::endl;
        
        // 显示找到的序列
        for (auto it = result; it != result + search_pattern.size(); ++it) 
        {
            std::cout << "  ID: " << it->id 
                      << ", Name: " << it->name 
                      << ", Age: " << it->age << std::endl;
        }
    } 
    else 
    {
        std::cout << "Pattern not found" << std::endl;
    }
    
    return 0;
}