Здравствуйте. Имеется дилема по поводу интерфейса для алгоритма поиска.
Итак, есть std::search. Он ищет подстроку в строке. И возвращает итератор на первое совпадение. Если мы хотим следующее вхождение, то просто передаём другой диапазон.
Что имеется в Boost.Algorithm - есть реализация алгоритма Бойера-Мура. Раньше он тоже возвращал итератор на первый найденный элемент. Теперь он возвращает пару итераторов (начало надйенного паттерна, конец найденного паттерна).
Но проблема в том, что Бойер-Мур возвращает итераторы только на первый найденный элемент. Чтобы найти все вхождения подстроки в строку, мы можем должны вызвать N раз. Накладных расходов на предпросчёт при каждом вызове нет - мы можем создать обьект Boyer-Moore, и только при создании будут рассчитаны две таблицы.
Проблема в том, что при поиске подстроки Бойер-Мур использует умный сдвиг по входной строке, и если мы будем вызывать N раз функцию поиска, эта информация о сдвиге будет теряться, и производительность будет проседать. Если мы хотим посчитать все вхождения подстроки в строку, то быстрее будет не N раз вызывать функцию, а за 1 раз найти все вхождения.
Но тогда придётся плодить какой-то новый интерфейс: один для нахождения первого вхождения, второй для нахождения всех вхождений.
Как будет лучше поступить здесь?
