В этом подпункте предусмотрены function object types операции, которые ищут последовательность[pat_first, pat_last) в другой последовательности,[first, last) которая предоставляется оператору вызова функции объекта. Первая последовательность (шаблон для поиска) предоставляется конструктору объекта, а вторая (последовательность для поиска) предоставляется оператору вызова функции.
Каждая специализация шаблона класса , указанного в настоящем подпункте ,[func.search] должны отвечатьCopyConstructible иCopyAssignable требованиям. Параметры шаблона с именем
ForwardIterator,
ForwardIterator1,
ForwardIterator2,
RandomAccessIterator,
RandomAccessIterator1,
RandomAccessIterator2, а также
BinaryPredicate
шаблонов, указанных в этом подпункте, [func.search] должны соответствовать тем же требованиям и семантике, что и в[algorithms.general]. Названные параметры шаблонаHash должны соответствовать требованиям, указанным в[hash.requirements].
Программа поиска Бойера-Мура реализует алгоритм поиска Бойера-Мура. Программа поиска Boyer-Moore-Horspool реализует алгоритм поиска Boyer-Moore-Horspool. В общем, поисковик Бойера-Мура будет использовать больше памяти и работать лучше, чем Бойер-Мур-Хорспул.
template <class ForwardIterator1, class BinaryPredicate = equal_to<>>
class default_searcher {
public:
default_searcher(ForwardIterator1 pat_first, ForwardIterator1 pat_last,
BinaryPredicate pred = BinaryPredicate());
template <class ForwardIterator2>
pair<ForwardIterator2, ForwardIterator2>
operator()(ForwardIterator2 first, ForwardIterator2 last) const;
private:
ForwardIterator1 pat_first_; // exposition only
ForwardIterator1 pat_last_; // exposition only
BinaryPredicate pred_; // exposition only
};default_searcher(ForwardIterator pat_first, ForwardIterator pat_last,
BinaryPredicate pred = BinaryPredicate());
Effects: Создаетdefault_searcher объект, инициализируясьpat_first_ с помощьюpat_first, pat_last_с помощьюpat_lastи pred_ с помощьюpred.
Throws: Любое исключение, созданное конструктором копированияBinaryPredicate или ForwardIterator1.
template<class ForwardIterator2>
pair<ForwardIterator2, ForwardIterator2>
operator()(ForwardIterator2 first, ForwardIterator2 last) const;
template <class RandomAccessIterator1,
class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
class BinaryPredicate = equal_to<>>
class boyer_moore_searcher {
public:
boyer_moore_searcher(RandomAccessIterator1 pat_first,
RandomAccessIterator1 pat_last,
Hash hf = Hash(),
BinaryPredicate pred = BinaryPredicate());
template <class RandomAccessIterator2>
pair<RandomAccessIterator2, RandomAccessIterator2>
operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
private:
RandomAccessIterator1 pat_first_; // exposition only
RandomAccessIterator1 pat_last_; // exposition only
Hash hash_; // exposition only
BinaryPredicate pred_; // exposition only
};boyer_moore_searcher(RandomAccessIterator1 pat_first,
RandomAccessIterator1 pat_last,
Hash hf = Hash(),
BinaryPredicate pred = BinaryPredicate());
Requires: Тип значенияRandomAccessIterator1 должен соответствоватьDefaultConstructible требованиям,CopyConstructible требованиям иCopyAssignable требованиям.
Requires: Для любых двух значенийA иB типаiterator_traits<RandomAccessIterator1>::value_type, еслиpred(A, B) == true, тоhf(A) == hf(B) должно бытьtrue.
Effects: Создаетboyer_moore_searcher объект, инициализируясьpat_first_ сpat_first, pat_last_ сpat_last,hash_ сhfиpred_ сpred.
Throws: Любое исключение брошенная копию конструктораRandomAccessIterator1, или с помощью конструктора по умолчанию, конструктор копирования или оператор присваивания копии типа ценностнойRandomAccessIterator1или конструктор копирования илиoperator() изBinaryPredicate илиHash. Можетbad_alloc вызвать ошибку, если не может быть выделена дополнительная память, необходимая для внутренних структур данных.
template <class RandomAccessIterator2>
pair<RandomAccessIterator2, RandomAccessIterator2>
operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
Returns: Пара итераторовi иj такие, что
i - это первый итератор в диапазоне,[first, last - (pat_last_ - pat_first_)) такой, что для каждого неотрицательного целого числа,n меньшего, чемpat_last_ - pat_first_ выполняется следующее условие:, pred(*(i + n), *(pat_first_ + n)) != falseи
j == next(i, distance(pat_first_, pat_last_)).
Возвращает,make_pair(first, first) если[pat_first_, pat_last_) пусто, в противном случае возвращает,make_pair(last, last) если такой итератор не найден.
template <class RandomAccessIterator1,
class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
class BinaryPredicate = equal_to<>>
class boyer_moore_horspool_searcher {
public:
boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first,
RandomAccessIterator1 pat_last,
Hash hf = Hash(),
BinaryPredicate pred = BinaryPredicate());
template <class RandomAccessIterator2>
pair<RandomAccessIterator2, RandomAccessIterator2>
operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
private:
RandomAccessIterator1 pat_first_; // exposition only
RandomAccessIterator1 pat_last_; // exposition only
Hash hash_; // exposition only
BinaryPredicate pred_; // exposition only
};boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first,
RandomAccessIterator1 pat_last,
Hash hf = Hash(),
BinaryPredicate pred = BinaryPredicate());
Requires: Тип значенияRandomAccessIterator1 должны удовлетворятьDefaultConstructible, CopyConstructibleиCopyAssignable требования.
Requires: Для любых двух значенийA иB типаiterator_traits<RandomAccessIterator1>::value_type, еслиpred(A, B) == true, тоhf(A) == hf(B) должно бытьtrue.
Effects: Создаетboyer_moore_horspool_searcher объект, инициализируясьpat_first_ сpat_first, pat_last_ сpat_last,hash_ сhfиpred_ сpred.
Throws: Любое исключение брошенная копию конструктораRandomAccessIterator1, или с помощью конструктора по умолчанию, конструктор копирования или оператор присваивания копии типа ценностнойRandomAccessIterator1 или копирующего конструктора илиoperator() изBinaryPredicate илиHash. Можетbad_alloc вызвать ошибку, если не может быть выделена дополнительная память, необходимая для внутренних структур данных.
template <class RandomAccessIterator2>
pair<RandomAccessIterator2, RandomAccessIterator2>
operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
Returns: Пара итераторовi иj такие, что
i - это первый итераторi в диапазоне, [first, last - (pat_last_ - pat_first_)) такой, что для каждого неотрицательного целого числа,n меньшего, чемpat_last_ - pat_first_ выполняется следующее условие:, pred(*(i + n), *(pat_first_ + n)) != falseи
j == next(i, distance(pat_first_, pat_last_)).
Возвращает,make_pair(first, first) если[pat_first_, pat_last_) пусто, в противном случае возвращает,make_pair(last, last) если такой итератор не найден.