Boost boyer_moore搜索corpusIter类型的示例类？

Question

我成功使用了：

boost::algorithm::boyer_moore_search<const char *,const char *>( haystack, haystack_end, needle, needle_end )

在大海捞针寻找针。现在我想使用BM_search对针进行不区分大小写的搜索。由于我的干草堆是巨型的，我的计划是将针转换为小写，并让干草堆迭代器将干草堆字符视为一个特殊类，其比较函数在比较之前将字母转换为小写。但是，我无法正确表达这一点。我尝试着：

class casechar {
    public:
      char ch;
      // other stuff...it's not right, but I don't think the compiler is even getting this far
} ;

class caseiter : public std::iterator<random_access_iterator_tag,casechar> {
      const casechar *ptr;
    public:
      // various iterator functions, but not enough of them, apparently!
} ;

boost::algorithm::boyer_moore_search<const caseiter,const char *>( HaYsTaCk, HaYsTaCk_EnD, needle, needle_end );

编译器（OSX上的g ++）抱怨尝试实例化hash <casechar>，我想对于一些BM内部事情。我迷失在模板<twisty_passages，all_different>的迷宫中。我可以强迫某人指点一点方向吗？我怀疑我只需要在casechar和/或caseiter中提供某些实现，但我不知道哪些实现。

谢谢！

Answer 1

The first problem you will run into是这样的：

BOOST_STATIC_ASSERT (( boost::is_same<
                       typename std::iterator_traits<patIter>::value_type, 
                       typename std::iterator_traits<corpusIter>::value_type>::value ));

这需要模式的迭代器的值类型和语料库的迭代器是相同的类型。换句话说，您还需要使用casechar作为模式。

这是我要做的：

• 写一个casechar，使用自定义operator ==等进行不区分大小写的比较。
• 无需编写自定义迭代器。 const casechar *是一个完全可以接受的随机访问迭代器。
• 写一个std::hash<casechar>专业化。这种专业化可能只是简单地返回像std::hash<char>()(std::tolower(ch))这样的东西。

也就是说，我有点怀疑这会让你获得性能提升，相比之下，只需将所有内容转换为小写。 chars的跳过表使用了一种优化，该优化使用数组而不是unordered_maps来实现更快的索引和更少的堆分配。此优化不用于自定义类型，例如casechar。

Answer 2

请在此处找到示例代码

std::vector<std::wstring> names;
names.push_back(L"Rahul");
names.push_back(L"John");
names.push_back(L"Alexa");
names.push_back(L"Tejas");
names.push_back(L"Alexandra");

std::vector<std::wstring> pattern;
pattern.push_back(L"Tejas");


auto itr = boost::algorithm::boyer_moore_search<std::vector<std::wstring>,
    std::vector<std::wstring>>(names, pattern);

if (itr != names.end())
{
    OutputDebugString(std::wstring(L"pattern found in the names " + *itr).c_str());
}
else
{
    OutputDebugString(std::wstring(L"pattern not found in the names").c_str());
}

对于我创建视频的代码的工作演示，请查看：

Boyer moore search | Boost api | C++ tutorial