algorithms.html

<cxx-clause id="algorithms">
  <h1>Algorithms library</h1>

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

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

namespace std {
namespace experimental {
inline namespace fundamentals_v2 {

  <cxx-ref insynopsis="" to="alg.search"></cxx-ref>
  template&lt;class ForwardIterator, class Searcher&gt;
  ForwardIterator search(ForwardIterator first, ForwardIterator last,
                         const Searcher&amp; searcher);

  <cxx-ref insynopsis="" to="alg.random.sample"></cxx-ref>
  template&lt;class PopulationIterator, class SampleIterator, class Distance>
  SampleIterator sample(PopulationIterator first, PopulationIterator last,
                        SampleIterator out, Distance n);

  template&lt;class PopulationIterator, class SampleIterator,
           class Distance, class UniformRandomNumberGenerator>
  SampleIterator sample(PopulationIterator first, PopulationIterator last,
                        SampleIterator out, Distance n,
                        UniformRandomNumberGenerator&amp;&amp; g);

  <cxx-ref insynopsis="" to="alg.random.shuffle"></cxx-ref>
  template&lt;class RandomAccessIterator>
  void shuffle(RandomAccessIterator first, RandomAccessIterator last);

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

  </cxx-section>

  <cxx-section id="alg.search">
    <h1>Search</h1>

    <cxx-function>
      <cxx-signature>template&lt;class ForwardIterator, class Searcher&gt;
ForwardIterator search(ForwardIterator first, ForwardIterator last,
                       const Searcher&amp; searcher);</cxx-signature>

      <cxx-effects>Equivalent to <code>return searcher(first, last);</code></cxx-effects>
      <cxx-remarks><code>Searcher</code> need not meet the <code>CopyConstructible</code> requirements.</cxx-remarks>
    </cxx-function>
  </cxx-section>

  <cxx-section id="alg.random.sample">
    <h1>Sampling</h1>

    <cxx-function>
      <cxx-signature class="formatted">template&lt;class PopulationIterator, class SampleIterator, class Distance>
SampleIterator sample(PopulationIterator first, PopulationIterator last,
                      SampleIterator out, Distance n);

template&lt;class PopulationIterator, class SampleIterator,
         class Distance, class UniformRandomNumberGenerator>
SampleIterator sample(PopulationIterator first, PopulationIterator last,
                      SampleIterator out, Distance n,
                      UniformRandomNumberGenerator&amp;&amp; g);</cxx-signature>


      <cxx-requires>
        <ul>
          <li><code>PopulationIterator</code> shall meet the requirements of an <code>InputIterator</code> type.</li>
          <li><code>SampleIterator</code> shall meet the requirements of an <code>OutputIterator</code> type.</li>
          <li><code>SampleIterator</code> shall meet the additional requirements of a <code>RandomAccessIterator</code> type
          unless <code>PopulationIterator</code> meets the additional requirements of a <code>ForwardIterator</code> type.</li>
          <li><code>PopulationIterator</code>'s value type shall be writable to <code>out</code>.</li>
          <li><code>Distance</code> shall be an integer type.</li>
          <li><code>UniformRandomNumberGenerator</code> shall meet the requirements of a uniform random number generator type (<cxx-ref in="cxx" to="rand.req.urng"></cxx-ref>)
          whose return type is convertible to <code>Distance</code>.</li>
          <li><code>out</code> shall not be in the range <cxx-range begin="first" end="last"></cxx-range>.</li>
        </ul>
      </cxx-requires>
      <cxx-effects>Copies <code>min(last−first, n)</code> elements (the <dfn>sample</dfn>)
      from <cxx-range begin="first" end="last"></cxx-range> (the <dfn>population</dfn>) to <code>out</code>
      such that each possible sample has equal probability of appearance.
      <cxx-note>Algorithms that obtain such effects include <cxx-term>selection sampling</cxx-term> and <cxx-term>reservoir sampling</cxx-term>.</cxx-note></cxx-effects>
      <cxx-returns>The end of the resulting sample range.</cxx-returns>
      <cxx-complexity>O(<code>last - first</code>).</cxx-complexity>
      <cxx-remarks>
        <ul>
          <li>Stable if and only if <code>PopulationIterator</code> meets the
            requirements of a <code>ForwardIterator</code> type.</li>
          <li>If <code>g</code> is not given in the argument list, it denotes
            the per-thread engine (<cxx-ref to="rand.util.randint"></cxx-ref>).
            To the extent that the implementation of this function makes use of
            random numbers, the object <code>g</code> shall serve as the
            implementation’s source of randomness.</li>
        </ul>
      </cxx-remarks>
    </cxx-function>
  </cxx-section>
  <cxx-section id="alg.random.shuffle">
    <h1>Shuffle</h1>
    <cxx-function>
      <cxx-signature>template&lt;class RandomAccessIterator>
  void shuffle(RandomAccessIterator first, RandomAccessIterator last);</cxx-signature>
      <cxx-effects>Permutes the elements in the range <code>[first,last)</code>
        such that each possible permutation of those elements has equal
        probability of appearance.</cxx-effects>
      <cxx-requires><code>RandomAccessIterator</code> shall satisfy the
        requirements of <code>ValueSwappable</code> (<cxx-ref in="cxx" to="swappable.requirements"></cxx-ref>).</cxx-requires>
      <cxx-complexity>Exactly <code>(last - first) - 1</code> swaps.</cxx-complexity>
      <cxx-remarks>To the extent that the implementation of this function
        makes use of random numbers, the per-thread engine (<cxx-ref to="rand.util.randint"></cxx-ref>)
        shall serve as the implementation's source of randomness.</cxx-remarks>
    </cxx-function>
  </cxx-section>
</cxx-clause>