std::sample() algorithm

od C++17

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

Selects n elements from the sequence [first; last) (without replacement) such that each possible sample has equal probability of appearance, and writes those selected elements into the output iterator out.

Random numbers are generated using the random number generator g.

If n is greater than the number of elements in the sequence, selects last - first elements.

The algorithm is stable (preserves the relative order of the selected elements) only if PopulationIterator meets the requirements of LegacyForwardIterator.

Undefined Behaviour

The behavior is undefined

if out is in [first; last).

Parameters

first last	The range of elements from which to make the sampling (population).
out	The output iterator where the samples are written.
n	The number of samples.
g	The random number generator used as a source of randomness.

Type requirements

PopulationIterator	LegacyInputIterator
SampleIterator	LegacyOutputIterator
SampleIterator	LegacyRandomAccessIterator Only if PopulationIterator doesn't meet LegacyForwardIterator
Distance	Must be an integer type.

With URBG_NoRef defined as std::remove_reference_t<URBG>:

URBG_NoRef	UniformRandomBitGenerator
Return type of URBG_NoRef	Convertible to Distance

PopulationIterator::value_type must be writeable to out.

Return value

Returns a copy of out after the last sample that was output, that is, end of the sample range.

Complexity

Linear in std::distance(first, last);

Exceptions

(none)

Notes

This function may implement selection sampling or reservoir sampling.

Main.cpp

#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
#include <string>

int main()
{
    std::string in {"ABCDEFGHIJK"}, out;
    std::sample(in.begin(), in.end(), std::back_inserter(out), 4,
                std::mt19937 {std::random_device{}()});
    std::cout << "Four random letters out of " << in << " : " << out << '\n';
}

Possible Output

Four random letters out of ABCDEFGHIJK: ACID