Пример класса для Boost boyer_moore search corpusIter type?

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) жалуется на попытку создать экземпляр хэш <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)).

Сказанное: я несколько сомневаюсь, что это фактически обеспечит вам прирост производительности по сравнению с просто преобразованием всего в нижний регистр. В таблице пропуска для char s используется оптимизация, которая использует массивы вместо unordered_map с для более быстрой индексации и меньшего количества распределений кучи. Эта оптимизация не используется для настраиваемого типа, например casechar.