func.html

<cxx-clause id="func">
  <h1>Function objects</h1>

  <cxx-section id="header.functional.synop">
    <h1>Header <code>&lt;experimental/functional></code> synopsis</h1>

    <cxx-ednote class="para">
    The following header synopsis fixes the missing <tt>noexcept</tt> specifications of the comparison functions as recently resolved by <a href="http://cplusplus.github.io/LWG/lwg-active.html#2401">LWG 2401</a>.
    We consider this change <em>editorial</em> at this point because the two different declarations were already in conflict,
    and this change does not have impact on the actual prototype specifications, which will have the same specifiers as in C++14.
    </cxx-ednote>

<pre><code>#include &lt;functional>

namespace std {
  namespace experimental {
  inline namespace fundamentals_v2 {

    // See <cxx-ref in="cxx" to="bind"></cxx-ref>, Function object binders
    template &lt;class T> constexpr bool is_bind_expression_v
      = is_bind_expression&lt;T>::value;
    template &lt;class T> constexpr int is_placeholder_v
      = is_placeholder&lt;T>::value;

    <cxx-ref insynopsis="" to="func.wrap.func"></cxx-ref>
    template&lt;class&gt; class function; <i>// undefined</i>
    template&lt;class R, class... ArgTypes&gt; class function&lt;R(ArgTypes...)&gt;;

    template&lt;class R, class... ArgTypes&gt;
    void swap(function&lt;R(ArgTypes...)&gt;&amp;, function&lt;R(ArgTypes...)&gt;&amp;);

    template&lt;class R, class... ArgTypes&gt;
    bool operator==(const function&lt;R(ArgTypes...)&gt;&amp;, nullptr_t) noexcept;
    template&lt;class R, class... ArgTypes&gt;
    bool operator==(nullptr_t, const function&lt;R(ArgTypes...)&gt;&amp;) noexcept;
    template&lt;class R, class... ArgTypes&gt;
    bool operator!=(const function&lt;R(ArgTypes...)&gt;&amp;, nullptr_t) noexcept;
    template&lt;class R, class... ArgTypes&gt;
    bool operator!=(nullptr_t, const function&lt;R(ArgTypes...)&gt;&amp;) noexcept;

    <cxx-ref insynopsis="" to="func.searchers"></cxx-ref>
    template&lt;class ForwardIterator, class BinaryPredicate = equal_to&lt;&gt;&gt;
      class default_searcher;

    template&lt;class RandomAccessIterator,
             class Hash = hash&lt;typename iterator_traits&lt;RandomAccessIterator&gt;::value_type&gt;,
             class BinaryPredicate = equal_to&lt;&gt;&gt;
      class boyer_moore_searcher;

    template&lt;class RandomAccessIterator,
             class Hash = hash&lt;typename iterator_traits&lt;RandomAccessIterator&gt;::value_type&gt;,
             class BinaryPredicate = equal_to&lt;&gt;&gt;
      class boyer_moore_horspool_searcher;


    template&lt;class ForwardIterator, class BinaryPredicate = equal_to&lt;&gt;&gt;
    default_searcher&lt;ForwardIterator, BinaryPredicate&gt;
    make_default_searcher(ForwardIterator pat_first, ForwardIterator pat_last,
                          BinaryPredicate pred = BinaryPredicate());

    template&lt;class RandomAccessIterator,
             class Hash = hash&lt;typename iterator_traits&lt;RandomAccessIterator&gt;::value_type&gt;,
             class BinaryPredicate = equal_to&lt;&gt;&gt;
    boyer_moore_searcher&lt;RandomAccessIterator, Hash, BinaryPredicate&gt;
    make_boyer_moore_searcher(
        RandomAccessIterator pat_first, RandomAccessIterator pat_last,
        Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());

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

    <cxx-ref insynopsis="" to="func.not_fn"></cxx-ref>
    template &lt;class F> unspecified not_fn(F&& f);

  } // namespace fundamentals_v2
  } // namespace experimental

  template&lt;class R, class... ArgTypes, class Alloc&gt;
  struct uses_allocator&lt;experimental::function&lt;R(ArgTypes...)&gt;, Alloc&gt;;

} // namespace std</code></pre>

  </cxx-section>

  <cxx-section id="func.wrap.func">
    <h1>Class template <code>function</code></h1>

    <cxx-ednote>
      The following class template synopsis fixes the missing <code>noexcept</code> specification of the <code>nullptr_t</code> assignment operator
      as recently resolved by <a href="http://cplusplus.github.io/LWG/lwg-active.html#2401">LWG 2401</a>.
      We consider this change <em>editorial</em>, because the fundamentals-ts specification otherwise refers to a non-existing declaration in C++14.
    </cxx-ednote>

    <p>
      The specification of all declarations within this sub-clause <cxx-ref to="func.wrap.func"></cxx-ref>
      and its sub-clauses are the same as the corresponding declarations, as specified in <cxx-ref in="cxx" to="func.wrap.func"></cxx-ref>,
      unless explicitly specified otherwise. <cxx-note><code>std::experimental::function</code> uses
      <code>std::bad_function_call</code>, there is no additional type <code>std::experimental::bad_function_call</code></cxx-note>.
    </p>

<pre><code>namespace std {
  namespace experimental {
  inline namespace fundamentals_v2 {

    template&lt;class&gt; class function; <i>// undefined</i>

    template&lt;class R, class... ArgTypes&gt;
    class function&lt;R(ArgTypes...)&gt; {
    public:
      typedef R result_type;
      typedef T1 argument_type;
      typedef T1 first_argument_type;
      typedef T2 second_argument_type;

      typedef erased_type allocator_type;

      function() noexcept;
      function(nullptr_t) noexcept;
      function(const function&amp;);
      function(function&amp;&amp;);
      template&lt;class F&gt; function(F);
      template&lt;class A&gt; function(allocator_arg_t, const A&amp;) noexcept;
      template&lt;class A&gt; function(allocator_arg_t, const A&amp;,
        nullptr_t) noexcept;
      template&lt;class A&gt; function(allocator_arg_t, const A&amp;,
        const function&amp;);
      template&lt;class A&gt; function(allocator_arg_t, const A&amp;,
        function&amp;&amp;);
      template&lt;class F, class A&gt; function(allocator_arg_t, const A&amp;, F);

      function&amp; operator=(const function&amp;);
      function&amp; operator=(function&amp;&amp;);
      function&amp; operator=(nullptr_t) noexcept;
      template&lt;class F&gt; function&amp; operator=(F&amp;&amp;);
      template&lt;class F&gt; function&amp; operator=(reference_wrapper&lt;F&gt;);

      ~function();

      void swap(function&amp;);

      explicit operator bool() const noexcept;

      R operator()(ArgTypes...) const;

      const type_info&amp; target_type() const noexcept;
      template&lt;class T&gt; T* target() noexcept;
      template&lt;class T&gt; const T* target() const noexcept;

      pmr::memory_resource* get_memory_resource();
    };

    template &lt;class R, class... ArgTypes&gt;
    bool operator==(const function&lt;R(ArgTypes...)&gt;&amp;, nullptr_t) noexcept;
    template &lt;class R, class... ArgTypes&gt;
    bool operator==(nullptr_t, const function&lt;R(ArgTypes...)&gt;&amp;) noexcept;

    template &lt;class R, class... ArgTypes&gt;
    bool operator!=(const function&lt;R(ArgTypes...)&gt;&amp;, nullptr_t) noexcept;
    template &lt;class R, class... ArgTypes&gt;
    bool operator!=(nullptr_t, const function&lt;R(ArgTypes...)&gt;&amp;) noexcept;

    template &lt;class R, class... ArgTypes&gt;
    void swap(function&lt;R(ArgTypes...)&gt;&amp;, function&lt;R(ArgTypes...)&gt;&amp;);

  } // namespace fundamentals_v2
  } // namespace experimental

  template &lt;class R, class... ArgTypes, class Alloc&gt;
  struct uses_allocator&lt;experimental::function&lt;R(ArgTypes...)&gt;, Alloc&gt;
    : true_type { };

} // namespace std</code></pre>

    <cxx-section id="func.wrap.func.con">
      <h1><code>function</code> construct/copy/destroy</h1>

      <cxx-ednote>
        The following first paragraph has been slightly editorially improved to
        (a) make the difference between <code>std::function</code> and <code>std::experimental::function</code> clearer
        (which seems necessary due to the "including" wording that can be parsed in two different ways) and
        (b) to make intended normative wording clearer, that had been put into parenthesis before, by simply removing these parenthesis.
      </cxx-ednote>

      <p>
        When a <code>function</code> constructor that takes a first argument of type <code>allocator_arg_t</code> is invoked,
        the second argument is treated as a <cxx-term>type-erased allocator</cxx-term> (<cxx-ref to="memory.type.erased.allocator"></cxx-ref>).
        If the constructor moves or makes a copy
        of a function object (<cxx-ref in="cxx" to="function.objects"></cxx-ref>),
        including an instance of the <code>experimental::function</code> class template,
        then that move or copy is performed by <cxx-term>using-allocator construction</cxx-term> with allocator <code>get_memory_resource()</code>.
      </p>

      <p>
        In the following descriptions, let <code><em>ALLOCATOR_OF</em>(f)</code> be the allocator specified in the construction of <code>function</code> <code>f</code>,
        or <code>allocator&lt;char&gt;()</code> if no allocator was specified.
      </p>

      <cxx-function>
        <cxx-signature>function&amp; operator=(const function&amp; f);</cxx-signature>

        <cxx-effects><code>function(allocator_arg, <em>ALLOCATOR_OF</em>(*this), f).swap(*this);</code></cxx-effects>
        <cxx-returns><code>*this</code>.</cxx-returns>
      </cxx-function>

      <cxx-function>
        <cxx-signature>function&amp; operator=(function&amp;&amp; f);</cxx-signature>

        <cxx-effects><code>function(allocator_arg, <em>ALLOCATOR_OF</em>(*this), std::move(f)).swap(*this);</code></cxx-effects>
        <cxx-returns><code>*this</code>.</cxx-returns>
      </cxx-function>

      <cxx-ednote>The following <i>Effects</i> element has been fixed and syncs the wording "<code>*this != NULL</code>"
      with the C++14 working draft replacing it with "<code>*this != nullptr</code>"</cxx-ednote>

      <cxx-function>
        <cxx-signature>function&amp; operator=(nullptr_t) noexcept;</cxx-signature>

        <cxx-effects>If <code>*this != nullptr</code>, destroys the target of <code>this</code>.</cxx-effects>
        <cxx-postconditions><code>!(*this)</code>.
        The memory resource returned by <code>get_memory_resource()</code> after the assignment is equivalent to the memory resource before the assignment.
        <cxx-note>the address returned by <code>get_memory_resource()</code> might change</cxx-note></cxx-postconditions>
        <cxx-returns><code>*this</code>.</cxx-returns>
      </cxx-function>

      <cxx-function>
        <cxx-signature>template&lt;class F&gt; function&amp; operator=(F&amp;&amp; f);</cxx-signature>

        <cxx-effects><code>function(allocator_arg, <em>ALLOCATOR_OF</em>(*this), std::forward&lt;F&gt;(f)).swap(*this);</code></cxx-effects>
        <cxx-returns><code>*this</code>.</cxx-returns>
        <cxx-remarks>This assignment operator shall not participate in overload resolution unless
          <code>declval&lt;decay_t&lt;F&gt;&amp;&gt;()</code> is Callable (<cxx-ref in="cxx" to="func.wrap.func"></cxx-ref>)
          for argument types <code>ArgTypes...</code> and return type <code>R</code>.</cxx-remarks>
      </cxx-function>

      <cxx-function>
        <cxx-signature>template&lt;class F&gt; function&amp; operator=(reference_wrapper&lt;F&gt; f);</cxx-signature>

        <cxx-effects><code>function(allocator_arg, <em>ALLOCATOR_OF</em>(*this), f).swap(*this);</code></cxx-effects>
        <cxx-returns><code>*this</code>.</cxx-returns>
      </cxx-function>
    </cxx-section>

    <cxx-section id="func.wrap.func.mod">
      <h1><code>function</code> modifiers</h1>

      <cxx-function>
        <cxx-signature>void swap(function&amp; other);</cxx-signature>

        <cxx-requires><code>*this-&gt;get_memory_resource() == *other.get_memory_resource()</code>.</cxx-requires>
        <cxx-effects>Interchanges the targets of <code>*this</code> and <code>other</code>.</cxx-effects>
        <cxx-remarks>The allocators of <code>*this</code> and <code>other</code> are not interchanged.</cxx-remarks>
      </cxx-function>
    </cxx-section>
  </cxx-section>

  <cxx-section id="func.searchers">
    <h1>Searchers</h1>

    <p>
      This sub-clause provides function object types (<cxx-ref in="cxx" to="function.objects"></cxx-ref>) for operations
      that search for a sequence <cxx-range begin="pat_first" end="pat_last"></cxx-range> in another sequence <cxx-range begin="first" end="last"></cxx-range>
      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.
    </p>

    <p>
      Each specialization of a class template specified in this sub-clause <cxx-ref to="func.searchers"></cxx-ref> shall meet the <code>CopyConstructible</code> and <code>CopyAssignable</code> requirements.
      Template parameters named <code>ForwardIterator</code>, <code>ForwardIterator1</code>, <code>ForwardIterator2</code>, <code>RandomAccessIterator</code>, <code>RandomAccessIterator1</code>, <code>RandomAccessIterator2</code>, and <code>BinaryPredicate</code> of templates specified in this sub-clause <cxx-ref to="func.searchers"></cxx-ref> shall meet the same requirements and semantics as specified in <cxx-ref in="cxx" to="algorithms.general"></cxx-ref>.
      Template parameters named <code>Hash</code> shall meet the requirements as specified in <cxx-ref in="cxx" to="hash.requirements"></cxx-ref>.
    </p>

    <p>
      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 run-time performance than Boyer-Moore-Horspool
    </p>

    <cxx-section id="func.searchers.default">
      <h1>Class template <code>default_searcher</code></h1>

      <pre><code>template&lt;class ForwardIterator1, class BinaryPredicate = equal_to&lt;&gt;&gt;
class default_searcher {
public:
  default_searcher(ForwardIterator1 pat_first, ForwardIterator1 pat_last,
                   BinaryPredicate pred = BinaryPredicate());

  template&lt;class ForwardIterator2&gt;
  ForwardIterator2
  operator()(ForwardIterator2 first, ForwardIterator2 last) const;

private:
  ForwardIterator1 pat_first_; <i>// exposition only</i>
  ForwardIterator1 pat_last_;  <i>// exposition only</i>
  BinaryPredicate  pred_;      <i>// exposition only</i>
};
</code></pre>

      <cxx-function>
        <cxx-signature>default_searcher(ForwardIterator pat_first, ForwardIterator pat_last,
BinaryPredicate pred = BinaryPredicate());</cxx-signature>

        <cxx-effects>Constructs a <code>default_searcher</code> object, initializing <code>pat_first_</code> with <code>pat_first</code>, <code>pat_last_</code> with <code>pat_last</code>, and <code>pred_</code> with <code>pred</code>.</cxx-effects>
        <cxx-throws>Any exception thrown by the copy constructor of <code>BinaryPredicate</code> or <code>ForwardIterator1</code>.</cxx-throws>
      </cxx-function>

      <cxx-function>
        <cxx-signature>template&lt;class ForwardIterator2&gt;
ForwardIterator2 operator()(ForwardIterator2 first, ForwardIterator2 last) const;</cxx-signature>

        <cxx-effects>Equivalent to <code>return std::search(<w-br></w-br>first, last, pat_first_, pat_last_, pred_);</code></cxx-effects>
      </cxx-function>

      <cxx-section id="func.searchers.default.creation">
        <h1><code>default_searcher</code> creation functions</h1>

        <cxx-function>
          <cxx-signature>template&lt;class ForwardIterator, class BinaryPredicate = equal_to&lt;&gt;&gt;
default_searcher&lt;ForwardIterator, BinaryPredicate&gt;
make_default_searcher(ForwardIterator pat_first, ForwardIterator pat_last,
                      BinaryPredicate pred = BinaryPredicate());</cxx-signature>

          <cxx-effects>Equivalent to <code>return default_searcher&lt;ForwardIterator, BinaryPredicate&gt;(<w-br></w-br>pat_first, pat_last, pred);</code></cxx-effects>
        </cxx-function>
      </cxx-section>
    </cxx-section>

    <cxx-section id="func.searchers.boyer_moore">
      <h1>Class template <code>boyer_moore_searcher</code></h1>

<pre><code>template&lt;class RandomAccessIterator1,
         class Hash = hash&lt;typename iterator_traits&lt;RandomAccessIterator1&gt;::value_type&gt;,
         class BinaryPredicate = equal_to&lt;&gt;&gt;
class boyer_moore_searcher {
public:
  boyer_moore_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last,
                       Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());

  template&lt;class RandomAccessIterator2&gt;
  RandomAccessIterator2
  operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;

private:
  RandomAccessIterator1 pat_first_; <i>// exposition only</i>
  RandomAccessIterator1 pat_last_;  <i>// exposition only</i>
  Hash                  hash_;      <i>// exposition only</i>
  BinaryPredicate       pred_;      <i>// exposition only</i>
};
</code></pre>

      <cxx-function>
        <cxx-signature>boyer_moore_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last,
Hash hf = Hash(),
BinaryPredicate pred = BinaryPredicate());</cxx-signature>

        <cxx-requires>The value type of <code>RandomAccessIterator1</code> shall meet the <code>DefaultConstructible</code>, <code>CopyConstructible</code>, and <code>CopyAssignable</code> requirements.</cxx-requires>
        <cxx-requires>For any two values <code>A</code> and <code>B</code> of the type <code>iterator_traits&lt;RandomAccessIterator1&gt;::value_type</code>, if <code>pred(A,B)==true</code>, then <code>hf(A)==hf(B)</code> shall be true.</cxx-requires>
        <cxx-effects>Constructs a <code>boyer_moore_searcher</code> object, initializing <code>pat_first_</code> with <code>pat_first</code>, <code>pat_last_</code> with <code>pat_last</code>, <code>hash_</code> with <code>hf</code>, and <code>pred_</code> with <code>pred</code>.</cxx-effects>
        <cxx-throws>Any exception thrown by the copy constructor of <code>RandomAccessIterator1</code>,
        or by the default constructor, copy constructor, or the copy assignment operator of the value type of <code>RandomAccessIterator1</code>,
        or the copy constructor or <code>operator()</code> of <code>BinaryPredicate</code> or <code>Hash</code>.
        May throw <code>bad_alloc</code> if additional memory needed for internal data structures cannot be allocated.</cxx-throws>
      </cxx-function>

      <cxx-function>
        <cxx-signature>template&lt;class RandomAccessIterator2&gt;
RandomAccessIterator2 operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;</cxx-signature>

        <cxx-requires><code>RandomAccessIterator1</code> and <code>RandomAccessIterator2</code> shall have the same value type.</cxx-requires>
        <cxx-effects>Finds a subsequence of equal values in a sequence.</cxx-effects>
        <cxx-returns>
          The first iterator <code>i</code> in the range <cxx-range begin="first" end="last - (pat_last_ - pat_first_)"></cxx-range>
          such that for every non-negative integer <code>n</code> less than <code>pat_last_ - pat_first_</code> the following condition holds:
          <code>pred(*(i + n), *(pat_first_ + n)) != false</code>.
          Returns <code>first</code> if <cxx-range begin="pat_first_" end="pat_last_"></cxx-range> is empty,
          otherwise returns <code>last</code> if no such iterator is found.
        </cxx-returns>
        <cxx-complexity>At most <code>(last - first) * (pat_last_ - pat_first_)</code> applications of the predicate.</cxx-complexity>
      </cxx-function>

      <cxx-section id="func.searchers.boyer_moore.creation">
        <h1><code>boyer_moore_searcher</code> creation functions</h1>

        <cxx-function>
          <cxx-signature>template&lt;class RandomAccessIterator,
class Hash = hash&lt;typename iterator_traits&lt;RandomAccessIterator&gt;::value_type&gt;,
class BinaryPredicate = equal_to&lt;&gt;&gt;
  boyer_moore_searcher&lt;RandomAccessIterator, Hash, BinaryPredicate&gt;
  make_boyer_moore_searcher(RandomAccessIterator pat_first, RandomAccessIterator pat_last,
                            Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());</cxx-signature>

          <cxx-effects>Equivalent to <code>return boyer_moore_searcher&lt;RandomAccessIterator, Hash, BinaryPredicate&gt;(<w-br></w-br>pat_first, pat_last, hf, pred);</code></cxx-effects>
        </cxx-function>
      </cxx-section>
    </cxx-section>

    <cxx-section id="func.searchers.boyer_moore_horspool">
      <h1>Class template <code>boyer_moore_horspool_searcher</code></h1>

<pre><code>
template&lt;class RandomAccessIterator1,
         class Hash = hash&lt;typename iterator_traits&lt;RandomAccessIterator1&gt;::value_type&gt;,
         class BinaryPredicate = equal_to&lt;&gt;&gt;
class boyer_moore_horspool_searcher {
public:
  boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last,
                                Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());

  template&lt;class RandomAccessIterator2&gt;
  RandomAccessIterator2
  operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;

private:
  RandomAccessIterator1 pat_first_; <i>// exposition only</i>
  RandomAccessIterator1 pat_last_;  <i>// exposition only</i>
  Hash                  hash_;      <i>// exposition only</i>
  BinaryPredicate       pred_;      <i>// exposition only</i>
};
</code></pre>

      <cxx-function>
        <cxx-signature>boyer_moore_horspool_searcher(
RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last,
Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());</cxx-signature>

        <cxx-requires>The value type of <code>RandomAccessIterator1</code> shall meet the <code>DefaultConstructible</code>, <code>CopyConstructible</code>, and <code>CopyAssignable</code> requirements.</cxx-requires>
        <cxx-requires>For any two values <code>A</code> and <code>B</code> of the type <code>iterator_traits&lt;RandomAccessIterator1&gt;::value_type</code>,
        if <code>pred(A,B)==true</code>, then <code>hf(A)==hf(B)</code> shall be true.</cxx-requires>
        <cxx-effects>Constructs a <code>boyer_moore_horspool_searcher</code> object, initializing <code>pat_first_</code> with <code>pat_first</code>,
        <code>pat_last_</code> with <code>pat_last</code>, <code>hash_</code> with <code>hf</code>, and <code>pred_</code> with <code>pred</code>.</cxx-effects>
        <cxx-throws>
          Any exception thrown by the copy constructor of <code>RandomAccessIterator1</code>,
          or by the default constructor, copy constructor, or the copy assignment operator of the value type of <code>RandomAccessIterator1</code>
          or the copy constructor or <code>operator()</code> of <code>BinaryPredicate</code> or <code>Hash</code>.
          May throw <code>bad_alloc</code> if additional memory needed for internal data structures cannot be allocated..
        </cxx-throws>
      </cxx-function>

      <cxx-function>
        <cxx-signature>template&lt;class RandomAccessIterator2&gt;
RandomAccessIterator2 operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;</cxx-signature>

        <cxx-requires><code>RandomAccessIterator1</code> and <code>RandomAccessIterator2</code> shall have the same value type.</cxx-requires>
        <cxx-effects>Finds a subsequence of equal values in a sequence.</cxx-effects>
        <cxx-returns>
          The first iterator <code>i</code> in the range <cxx-range begin="first" end="last - (pat_last_ - pat_first_)"></cxx-range>
          such that for every non-negative integer <code>n</code> less than <code>pat_last_ - pat_first_</code> the following condition holds:
          <code>pred(*(i + n), *(pat_first_ + n)) != false</code>.
          Returns <code>first</code> if <cxx-range begin="pat_first_" end="pat_last_"></cxx-range> is empty,
          otherwise returns <code>last</code> if no such iterator is found.
        </cxx-returns>
        <cxx-complexity>At most <code>(last - first) * (pat_last_ - pat_first_)</code> applications of the predicate.</cxx-complexity>
      </cxx-function>

      <cxx-section id="func.searchers.boyer_moore_horspool.creation">
        <h1><code>boyer_moore_horspool_searcher</code> creation functions</h1>

        <cxx-function>
          <cxx-signature>template&lt;class RandomAccessIterator,
         class Hash = hash&lt;typename iterator_traits&lt;RandomAccessIterator&gt;::value_type&gt;,
         class BinaryPredicate = equal_to&lt;&gt;&gt;
boyer_moore_horspool_searcher&lt;RandomAccessIterator, Hash, BinaryPredicate&gt;
make_boyer_moore_horspool_searcher(
    RandomAccessIterator pat_first, RandomAccessIterator pat_last,
    Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());</cxx-signature>

          <cxx-effects>Equivalent to <code>return boyer_moore_horspool_searcher&lt;RandomAccessIterator, Hash, BinaryPredicate&gt;(<w-br></w-br>pat_first, pat_last, hf, pred);</code></cxx-effects>
        </cxx-function>
      </cxx-section>
    </cxx-section>
  </cxx-section>

  <cxx-section id="func.not_fn">
    <h1>Function template <code>not_fn</code></h1>

    <cxx-function>
      <cxx-signature>template &lt;class F&gt; <em>unspecified</em> not_fn(F&amp;&amp; f);</cxx-signature>

      <p>In the text that follows:</p>
      <ul>
        <li><code>FD</code> is the type <code>decay_t&lt;F&gt;</code>,</li>
        <li><code>fd</code> is an lvalue of type <code>FD</code> constructed from <code>std::forward&lt;F&gt;(f),</code></li>
        <li><code>fn</code> is a forwarding call wrapper created as a result of <code>not_fn(f)</code>,</li>
      </ul>
      <cxx-requires>
        <code>is_constructible&lt;FD, F&gt;::value</code> shall be <code>true</code>.
        <code>fd</code> shall be a callable object (<cxx-ref in="cxx" to="func.def"></cxx-ref>).
      </cxx-requires>
      <cxx-returns>
        A forwarding call wrapper <code>fn</code> such that the expression <code>fn(a1, a2, ..., aN)</code>
        is equivalent to <code>!<em>INVOKE</em>(fd, a1, a2, ..., aN)</code> (<cxx-ref in="cxx" to="func.require"></cxx-ref>).
      </cxx-returns>
      <cxx-throws>Nothing unless the construction of <code>fd</code> throws an exception.</cxx-throws>
      <cxx-remarks>
        The return type shall satisfy the requirements of <code>MoveConstructible</code>.
        If <code>FD</code> satisfies the requirements of <code>CopyConstructible</code>, then
        the return type shall satisfy the requirements of <code>CopyConstructible</code>.
        <cxx-note>This implies that <code>FD</code> is MoveConstructible.</cxx-note>
      </cxx-remarks>
      <p><cxx-note>Function template <code>not_fn</code> can usually provide a better solution than using the negators <code>not1</code> and <code>not2</code></cxx-note></p>
    </cxx-function>
  </cxx-section>
</cxx-clause>