20 General utilities library [utilities]
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_;
RandomAccessIterator1 pat_last_;
Hash hash_;
BinaryPredicate pred_;
};
boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first,
RandomAccessIterator1 pat_last,
Hash hf = Hash(),
BinaryPredicate pred = BinaryPredicate());
Preconditions: The value type of
RandomAccessIterator1 meets the
Cpp17DefaultConstructible,
Cpp17CopyConstructible, and
Cpp17CopyAssignable requirements
. Let
V be
iterator_traits<RandomAccessIterator1>::value_type.For any two values
A and
B of type
V,
if
pred(A, B) == true, then
hf(A) == hf(B) is
true.Effects: Initializes
pat_first_ with
pat_first,
pat_last_ with
pat_last,
hash_ with
hf, and
pred_ with
pred. Throws: Any exception thrown by the copy constructor of
RandomAccessIterator1,
or by the default constructor, copy constructor, or the copy assignment operator of the value type of
RandomAccessIterator1
or the copy constructor or
operator() of
BinaryPredicate or
Hash. May throw
bad_alloc if additional memory needed for internal data structures cannot be allocated
.template<class RandomAccessIterator2>
pair<RandomAccessIterator2, RandomAccessIterator2>
operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
Mandates:
RandomAccessIterator1 and
RandomAccessIterator2
have the same value type
. Effects: Finds a subsequence of equal values in a sequence
. Returns: A pair of iterators
i and
j such that
- i is the first iterator i in the range
[first, last - (pat_last_ - pat_first_)) such that
for every non-negative integer n less than pat_last_ - pat_first_
the following condition holds:
pred(*(i + n), *(pat_first_ + n)) != false, and
- j == next(i, distance(pat_first_, pat_last_)).
Returns
make_pair(first, first) if [
pat_first_, pat_last_) is empty,
otherwise returns
make_pair(last, last) if no such iterator is found
.Complexity: At most
(last - first) * (pat_last_ - pat_first_) applications of the predicate
.