< cpp‎ | algorithm
Algorithm library
Execution policies (C++17)
Non-modifying sequence operations
Modifying sequence operations
Operations on uninitialized storage
Partitioning operations
Sorting operations
Binary search operations
Set operations (on sorted ranges)
Heap operations
Minimum/maximum operations

Numeric operations
C library
Defined in header <algorithm>
template< class PopulationIterator, class SampleIterator,

          class Distance, class UniformRandomBitGenerator >
SampleIterator sample( PopulationIterator first, PopulationIterator last,
                       SampleIterator out, Distance n,

                       UniformRandomBitGenerator&& g);
(since C++17)

Selects n elements from the sequence [first; last) 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 only if PopulationIterator meets the requirements of ForwardIterator


[edit] Parameters

first, last - pair of iterators forming the range from which to make the sampling (the population)
out - the output iterator where the samples are written. Must not be in the [first;last) range
n - number of samples to make
g - the random number generator used as the source of randomness
PopulationIterator must meet the requirements of InputIterator.
SampleIterator must meet the requirements of OutputIterator.
SampleIterator must also meet the requirements of RandomAccessIterator if PopulationIterator doesn't meet ForwardIterator
PopulationIterator's value type must be writeable to out
Distance must be an integer type
std::remove_reference_t<UniformRandomBitGenerator> must meet the requirements of UniformRandomBitGenerator and its return type must be convertible to Distance

[edit] Return value

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

[edit] Complexity

Linear in std::distance(first,last)

[edit] Notes

This function may implement selection sampling or reservoir sampling.

[edit] Example

#include <iostream>
#include <random>
#include <string>
#include <iterator>
#include <algorithm>
int main()
    std::string in = "abcdefgh", out;
    std::sample(in.begin(), in.end(), std::back_inserter(out),
                5, std::mt19937{std::random_device{}()});
    std::cout << "five random letters out of " << in << " : " << out << '\n';

Possible output:

five random letters out of abcdefgh : cdefg

[edit] See also

(until C++17)(C++11)
randomly re-orders elements in a range
(function template) [edit]