20 General utilities library [utilities]

20.14 Function objects [function.objects]

20.14.13 Searchers [func.search]

20.14.13.3 Class template boyer_moore_horspool_searcher [func.search.bmh]

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());

1

Requires: The value type of RandomAccessIterator1 shall meet the DefaultConstructible, CopyConstructible, and CopyAssignable requirements.

2

Requires: For any two values A and B of the type iterator_traits<RandomAccessIterator1>::value_type, if pred(A,B)==true, then hf(A)==hf(B) shall be true.

3

Effects: Constructs a boyer_moore_horspool_searcher object, initializing pat_first_ with pat_first, pat_last_ with pat_last, hash_ with hf, and pred_ with pred.

4

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;

5

Requires: RandomAccessIterator1 and RandomAccessIterator2 shall have the same value type.

6

Effects: Finds a subsequence of equal values in a sequence.

7

Returns: A pair of iterators i and j such that

  • (7.1)

    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

  • (7.2)

    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.

8

Complexity: At most (last - first) * (pat_last_ - pat_first_) applications of the predicate.

20.14.13.3.1 boyer_moore_horspool_searcher creation functions [func.search.bmh.creation]

template <class RandomAccessIterator, class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>, class BinaryPredicate = equal_to<>> boyer_moore_horspool_searcher<RandomAccessIterator, Hash, BinaryPredicate> make_boyer_moore_horspool_searcher( RandomAccessIterator pat_first, RandomAccessIterator pat_last, Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());

1

Effects: Equivalent to: 

return boyer_moore_horspool_searcher<RandomAccessIterator, Hash, BinaryPredicate>(
         pat_first, pat_last, hf, pred);