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 ([input.iterators]).
(1.2)
SampleIterator shall satisfy the requirements of an output iterator ([output.iterators]).
(1.3)
SampleIterator shall satisfy the additional requirements of a random access iterator ([random.access.iterators]) unless PopulationIterator satisfies the additional requirements of a forward iterator ([forward.iterators]).
(1.4)
PopulationIterator's value type shall be writable ([iterator.requirements.general]) 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 ([rand.req.urng]) 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.