20 General utilities library [utilities]
Subclause
[func.search] 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
.Each specialization of a class template specified in
[func.search]
shall meet the
Cpp17CopyConstructible and
Cpp17CopyAssignable requirements
.Template parameters named
- ForwardIterator,
- ForwardIterator1,
- ForwardIterator2,
- RandomAccessIterator,
- RandomAccessIterator1,
- RandomAccessIterator2, and
- BinaryPredicate
of templates specified in
[func.search] shall meet the same requirements and semantics as
specified in
[algorithms.general].Template parameters named
Hash shall meet the
Cpp17Hash
requirements (Table
34)
.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
.template<class ForwardIterator1, class BinaryPredicate = equal_to<>>
class default_searcher {
public:
constexpr default_searcher(ForwardIterator1 pat_first, ForwardIterator1 pat_last,
BinaryPredicate pred = BinaryPredicate());
template<class ForwardIterator2>
constexpr pair<ForwardIterator2, ForwardIterator2>
operator()(ForwardIterator2 first, ForwardIterator2 last) const;
private:
ForwardIterator1 pat_first_;
ForwardIterator1 pat_last_;
BinaryPredicate pred_;
};
constexpr default_searcher(ForwardIterator pat_first, ForwardIterator pat_last,
BinaryPredicate pred = BinaryPredicate());
Effects: Constructs a
default_searcher object, initializing
pat_first_
with
pat_first,
pat_last_ with
pat_last, and
pred_ with
pred. Throws: Any exception thrown by the copy constructor of
BinaryPredicate or
ForwardIterator1. template<class ForwardIterator2>
constexpr pair<ForwardIterator2, ForwardIterator2>
operator()(ForwardIterator2 first, ForwardIterator2 last) const;
Effects: Returns a pair of iterators
i and
j such that
- i == search(first, last, pat_first_, pat_last_, pred_), and
- if i == last, then j == last,
otherwise j == next(i, distance(pat_first_, pat_last_)).
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_;
RandomAccessIterator1 pat_last_;
Hash hash_;
BinaryPredicate pred_;
};
boyer_moore_searcher(RandomAccessIterator1 pat_first,
RandomAccessIterator1 pat_last,
Hash hf = Hash(),
BinaryPredicate pred = BinaryPredicate());
Preconditions: The value type of
RandomAccessIterator1 meets
the
Cpp17DefaultConstructible requirements,
the
Cpp17CopyConstructible requirements, and
the
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
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
. 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
.