28 Algorithms library [algorithms]

28.6 Mutating sequence operations [alg.modifying.operations]

28.6.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);

Requires:

(1.1)
PopulationIterator shall satisfy the requirements of an input iterator.
(1.2)
SampleIterator shall satisfy the requirements of an output iterator.
(1.3)
SampleIterator shall satisfy the additional requirements of a random access iterator unless PopulationIterator satisfies the additional requirements of a forward iterator.
(1.4)
PopulationIterator's value type shall be writable to out.
(1.5)
Distance shall be an integer type.
(1.6)
remove_reference_t<UniformRandomBitGenerator> shall meet the requirements of a uniform random bit generator type whose return type is convertible to Distance.
(1.7)
out shall not be in the range [first, last).

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: 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:

(5.1)
Stable if and only if PopulationIterator satisfies the requirements of a forward iterator.
(5.2)
To the extent that the implementation of this function makes use of random numbers, the object g shall serve as the implementation's source of randomness.