25 Algorithms library [algorithms]

25.7 Mutating sequence operations [alg.modifying.operations]

25.7.12 Sample [alg.random.sample]

template<class PopulationIterator, class SampleIterator,
         class Distance, class UniformRandomBitGenerator>
  SampleIterator sample(PopulationIterator first, PopulationIterator last,
                        SampleIterator out, Distance n,
                        UniformRandomBitGenerator&& g);

template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Gen>
  requires (forward_iterator<I> || random_access_iterator<O>) &&
           indirectly_copyable<I, O> &&
           uniform_random_bit_generator<remove_reference_t<Gen>>
  O ranges::sample(I first, S last, O out, iter_difference_t<I> n, Gen&& g);
template<input_range R, weakly_incrementable O, class Gen>
  requires (forward_range<R> || random_access_iterator<O>) &&
           indirectly_copyable<iterator_t<R>, O> &&
           uniform_random_bit_generator<remove_reference_t<Gen>>
  O ranges::sample(R&& r, O out, range_difference_t<R> n, Gen&& g);

Mandates: For the overload in namespace std, Distance is an integer type and *first is writable ([iterator.requirements.general]) to out.

Preconditions: out is not in the range [first, last).

For the overload in namespace std:

(2.1)
PopulationIterator meets the Cpp17InputIterator requirements ([input.iterators]).
(2.2)
SampleIterator meets the Cpp17OutputIterator requirements ([output.iterators]).
(2.3)
SampleIterator meets the Cpp17RandomAccessIterator requirements ([random.access.iterators]) unless PopulationIterator meets the Cpp17ForwardIterator requirements ([forward.iterators]).
(2.4)
remove_reference_t<UniformRandomBitGenerator> meets the requirements of a uniform random bit generator type ([rand.req.urng]).

Effects: Copies

min (last - first, n)

elements (the sample) from [first, last) (the population) to out such that each possible sample has equal probability of appearance.

[Note 1:

Algorithms that obtain such effects include selection sampling and reservoir sampling.

— end note]

Returns: The end of the resulting sample range.

Complexity:

O (last - first)

Remarks:

(6.1)
For the overload in namespace std, stable if and only if PopulationIterator meets the Cpp17ForwardIterator requirements.

For the first overload in namespace ranges, stable if and only if I models forward_iterator .
(6.2)
To the extent that the implementation of this function makes use of random numbers, the object g serves as the implementation's source of randomness.