23 General utilities library [utilities]

23.14 Function objects [function.objects]

23.14.14 Searchers [func.search]

1
#
This subclause provides function object types ([function.objects]) for operations that search for a sequence [pat_first, pat_­last) in another sequence [first, last) that is provided to the object's function call operator.
The first sequence (the pattern to be searched for) is provided to the object's constructor, and the second (the sequence to be searched) is provided to the function call operator.
2
#
Each specialization of a class template specified in this subclause [func.search] shall meet the CopyConstructible and CopyAssignable requirements.
Template parameters named of templates specified in this subclause [func.search] shall meet the same requirements and semantics as specified in [algorithms.general].
Template parameters named Hash shall meet the requirements as specified in [hash.requirements].
3
#
The Boyer-Moore searcher implements the Boyer-Moore search algorithm.
The Boyer-Moore-Horspool searcher implements the Boyer-Moore-Horspool search algorithm.
In general, the Boyer-Moore searcher will use more memory and give better runtime performance than Boyer-Moore-Horspool.

23.14.14.1 Class template default_­searcher [func.search.default]

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());
1
#
Effects: Constructs a default_­searcher object, initializing pat_­first_­ with pat_­first, pat_­last_­ with pat_­last, and pred_­ with pred.
2
#
Throws: Any exception thrown by the copy constructor of BinaryPredicate or ForwardIterator1.
🔗
template<class ForwardIterator2> pair<ForwardIterator2, ForwardIterator2> operator()(ForwardIterator2 first, ForwardIterator2 last) const;
3
#
Effects: Returns a pair of iterators i and j such that
  • (3.1)
    i == search(first, last, pat_­first_­, pat_­last_­, pred_­), and
  • (3.2)
    if i == last, then j == last, otherwise j == next(i, distance(pat_­first_­, pat_­last_­)).

23.14.14.2 Class template boyer_­moore_­searcher [func.search.bm]

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());
1
#
Requires: The value type of RandomAccessIterator1 shall meet the DefaultConstructible requirements, the CopyConstructible requirements, and the 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_­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 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.

23.14.14.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.