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:
Effects: Copies 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: .
Remarks:
  • 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.
  • 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.