Library

since C++17

Basic

std::sample

Select n elements uniformly at random without replacement from a population range, preserving their relative order.

std::samplesince C++17

Selects exactly n elements uniformly at random without replacement from the population range [first, last), writing them to an output range in the same relative order they appear in the population.

Overview

std::sample, added in C++17 under <algorithm>, implements reservoir sampling. Every subset of size n drawn from a population of size N has equal probability 1 / C(N, n) of being selected — this is the defining property of a uniform sample without replacement.

Two important guarantees distinguish it from a naïve shuffle-then-take approach:

Stability: the selected elements appear in the output in the same relative order as in the population (useful when order carries meaning, e.g. time-series data).
Single-pass compatibility: when PopulationIterator satisfies only InputIterator (streams, generator ranges), the algorithm still works — provided SampleIterator is a RandomAccessIterator, which allows the in-place reservoir to be maintained.

When PopulationIterator is a ForwardIterator or stronger, SampleIterator may be any OutputIterator. If n equals or exceeds the population size, all elements are copied and the function returns an iterator past the last written element.

There is no parallel overload for std::sample. The algorithm's sequential state (the URBG and the reservoir) does not parallelise cleanly, and the standard intentionally omits an ExecutionPolicy overload.

C++20 added std::ranges::sample, which accepts range objects directly and returns an in_out_result carrying both the consumed-population iterator and the output iterator.

Syntax

cpp

// C++17 — header <algorithm>
template<
    class PopulationIterator,
    class SampleIterator,
    class Distance,
    class URBG
>
SampleIterator sample(
    PopulationIterator first,
    PopulationIterator last,
    SampleIterator    out,
    Distance          n,
    URBG&&            g
);

cpp

// C++20 — header <algorithm>, namespace std::ranges
template<
    ranges::input_range        R,
    std::weakly_incrementable  O,
    class                      Gen
>
requires (ranges::forward_range<R> || std::random_access_iterator<O>)
      && std::uniform_random_bit_generator<std::remove_reference_t<Gen>>
ranges::in_out_result<ranges::borrowed_iterator_t<R>, O>
ranges::sample(R&& r, O out, ranges::range_difference_t<R> n, Gen&& gen);

Parameters

Parameter	Requirement
`[first, last)`	`LegacyInputIterator` pair representing the population
`out`	`LegacyOutputIterator`; must be `RandomAccessIterator` when population is input-only
`n`	Number of elements to select; clamped to population size
`g`	A `UniformRandomBitGenerator` (`std::mt19937`, `std::default_random_engine`, etc.)

Return value: an iterator pointing past the last element written to out.

Examples

Basic reservoir sample from a vector

cpp

#include <algorithm>   // C++17 std::sample
#include <random>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> population(1'000);
    std::iota(population.begin(), population.end(), 1);  // 1..1000  (C++11 iota)

    std::vector<int> sample(50);

    std::mt19937 rng{std::random_device{}()};  // C++11 Mersenne Twister
    std::sample(population.begin(), population.end(),
                sample.begin(), 50, rng);      // C++17

    for (int v : sample)
        std::cout << v << ' ';
}
// Output: 50 integers in ascending order (relative order preserved)

Sampling from a single-pass input stream

When the population is an istream_iterator, a forward pass is impossible. The output must be a RandomAccessIterator so the algorithm can maintain the reservoir in place.

cpp

#include <algorithm>
#include <iterator>
#include <random>
#include <sstream>
#include <vector>
#include <iostream>

int main() {
    std::istringstream data{"10 20 30 40 50 60 70 80 90 100"};

    std::vector<int> reservoir(4);  // capacity known in advance
    std::mt19937 rng{42};

    // istream_iterator is InputIterator — reservoir must be RandomAccessIterator
    auto end = std::sample(
        std::istream_iterator<int>{data},
        std::istream_iterator<int>{},
        reservoir.begin(),
        4,
        rng
    );  // C++17

    reservoir.erase(end, reservoir.end());  // trim if stream had < 4 elements
    for (int v : reservoir) std::cout << v << '\n';
}

C++20 ranges version

cpp

#include <algorithm>
#include <random>
#include <ranges>
#include <vector>
#include <print>  // C++23

int main() {
    auto evens = std::views::iota(0, 200)
               | std::views::filter([](int x){ return x % 2 == 0; });  // C++20

    std::vector<int> out(10);
    std::mt19937 rng{std::random_device{}()};

    auto [_, o] = std::ranges::sample(evens, out.begin(), 10, rng);  // C++20
    out.erase(o, out.end());

    std::println("{}", out);  // C++23
}

Statistical validation: mean of repeated samples

cpp

#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <cmath>
#include <iostream>

int main() {
    constexpr int N = 100'000;
    constexpr int k = 1'000;
    constexpr int trials = 200;

    std::vector<double> population(N);
    std::iota(population.begin(), population.end(), 1.0);
    const double true_mean = (N + 1) / 2.0;

    std::mt19937_64 rng{std::random_device{}()};  // C++11 64-bit MT
    std::vector<double> buf(k);
    double error_sum = 0;

    for (int t = 0; t < trials; ++t) {
        std::sample(population.begin(), population.end(),
                    buf.begin(), k, rng);  // C++17
        double sample_mean = std::reduce(buf.begin(), buf.end()) / k;  // C++17
        error_sum += std::abs(sample_mean - true_mean);
    }

    std::cout << "Average absolute error: " << error_sum / trials << '\n';
    // Should be close to 0 for a uniform sample
}

Best Practices

Seed the URBG once, reuse it. Constructing std::mt19937 is expensive (state initialisation of 624 words). Seed once at program startup or thread creation, then pass by reference to every call.

cpp

// Good: shared engine per thread
thread_local std::mt19937 rng{std::random_device{}()};
std::sample(pop.begin(), pop.end(), out.begin(), n, rng);

Pre-size the output container. std::sample writes through an output iterator — it does not push_back. Either reserve and use std::back_inserter (forward population only), or size the container to n and trim afterwards.

cpp

// With back_inserter — only valid when population is ForwardIterator or stronger
std::vector<int> out;
out.reserve(n);
std::sample(pop.begin(), pop.end(), std::back_inserter(out), n, rng);
// out.size() == min(n, pop.size())

Prefer std::mt19937 over std::default_random_engine. The standard gives default_random_engine no quality guarantees and it varies by implementation. Use std::mt19937 (C++11) for reproducibility and std::mt19937_64 when sampling from populations larger than ~4 billion.

For reproducible runs, record the seed alongside the sample:

cpp

std::uint64_t seed = 0xDEADBEEF'CAFEF00D;
std::mt19937_64 rng{seed};
std::sample(pop.begin(), pop.end(), out.begin(), n, rng);
// Log seed so the run can be replicated exactly

Common Pitfalls

Output iterator left in indeterminate state when n > population size. std::sample copies at most distance(first, last) elements. If the output buffer was pre-sized to n and the population is smaller, the trailing elements remain default-initialised (or garbage for trivial types). Always use the returned iterator to determine how many elements were actually written.

cpp

std::vector<int> out(n, -1);
auto end = std::sample(pop.begin(), pop.end(), out.begin(), n, rng);
out.erase(end, out.end());  // remove unused slots

Using the same URBG state for two samples expecting independence. Two calls to std::sample with the same rng object are sequentially independent — the second call continues from where the first left off, which is correct. The pitfall is copying the engine before the first call expecting that a copy produces the same sample; a copy does produce the same output only if reset to identical state, not if shared between calls.

Assuming the output is shuffled. std::sample preserves relative order. If your use case requires a random permutation of the sample, apply std::shuffle (C++11) afterwards.

cpp

std::sample(pop.begin(), pop.end(), out.begin(), n, rng);
std::shuffle(out.begin(), out.end(), rng);  // C++11, now truly random order

Passing n < 0. Distance is a signed or unsigned integer type, but n < 0 causes undefined behaviour — the standard requires n >= 0. Assert or clamp before calling if n is computed from user input.

Weighted Sampling

std::sample is unweighted — every element has equal selection probability. When elements differ in importance (e.g. users with longer account history should be sampled more often), use a distribution from <random> to drive index selection instead.

std::discrete_distribution<int> accepts a weight sequence and produces indices proportional to those weights. Sampling with it is a two-step process: draw an index, then look up the element.

cpp

// C++11
#include <random>
#include <vector>
#include <string>
#include <iostream>

int main() {
    // Users and their account ages in days (the "weight")
    std::vector<std::string> users  = {"alice", "bob", "carol", "dave", "eve"};
    std::vector<double>      ages   = {   3650,   180,   1200,    30,   730 };

    std::mt19937 rng{std::random_device{}()};  // C++11
    std::discrete_distribution<int> dist(ages.begin(), ages.end());  // C++11

    // Draw 5 samples with replacement, weighted by account age
    for (int i = 0; i < 5; ++i)
        std::cout << users[dist(rng)] << '\n';
}

For continuous ranges where a piecewise-constant density is known (e.g. geographic regions with different population densities), std::piecewise_constant_distribution maps a continuous variate onto intervals with per-interval weights.

cpp

// C++11
#include <random>
#include <iostream>

int main() {
    // Three intervals [0,1), [1,3), [3,6) with weights 1, 2, 0.5
    std::vector<double> boundaries = {0.0, 1.0, 3.0, 6.0};
    std::vector<double> weights    = {1.0, 2.0, 0.5};

    std::piecewise_constant_distribution<double> dist(  // C++11
        boundaries.begin(), boundaries.end(),
        weights.begin());

    std::mt19937 rng{std::random_device{}()};
    for (int i = 0; i < 6; ++i)
        std::cout << dist(rng) << '\n';
    // Values in [1,3) appear ~4x more often than values in [3,6)
}

When sampling without replacement under weights, no standard facility exists. The canonical approach is the exponential-key trick: assign each element a key U^(1/w) where U ~ Uniform(0,1), then take the top-k by key — efficiently achieved with a min-heap of size k.

Reservoir Sampling for Unknown-Size Streams

Algorithm R gives a uniform random sample of size k from a stream of unknown length in a single pass using O(k) memory. The algorithm maintains a reservoir of the first k elements, then for each subsequent element i (1-indexed, i > k) replaces a uniformly chosen reservoir slot with probability k/i.

std::sample applies this algorithm internally when the population iterator satisfies only InputIterator. The manual implementation below makes the logic explicit and can be adapted to non-standard stream sources.

cpp

// C++17
#include <algorithm>
#include <iterator>
#include <random>
#include <vector>
#include <iostream>

// Algorithm R: O(n) time, O(k) memory, single pass
template<class InputIt, class OutputIt, class Distance, class URBG>
OutputIt reservoir_sample(InputIt first, InputIt last,
                          OutputIt out, Distance k, URBG& rng) {
    Distance i = 0;
    for (; first != last && i < k; ++first, ++i)
        out[i] = *first;             // fill reservoir

    Distance filled = i;
    for (; first != last; ++first, ++i) {
        // Replace reservoir[j] with probability k / (i+1)
        std::uniform_int_distribution<Distance> pick(0, i);  // C++11
        Distance j = pick(rng);
        if (j < k)
            out[j] = *first;
    }
    return out + std::min(filled, k);
}

int main() {
    // Simulate a stream of 10 000 integers
    std::vector<int> stream(10'000);
    std::iota(stream.begin(), stream.end(), 0);

    std::vector<int> reservoir(100);
    std::mt19937 rng{std::random_device{}()};

    auto end = reservoir_sample(stream.begin(), stream.end(),
                                reservoir.data(), 100, rng);  // C++17
    reservoir.resize(end - reservoir.data());

    std::cout << "Sampled " << reservoir.size() << " elements\n";
}

Each element in the stream has an equal probability of being in the final reservoir, regardless of the total stream length — a property that can be verified by counting how often each index appears across many runs. This is precisely the guarantee std::sample provides for input-only ranges.

Sampling Without Replacement: Multiple Draws

std::sample is the idiomatic tool for a single draw of n elements without replacement. When you need multiple independent draws from the same population (e.g. cross-validation folds), re-running std::sample with the advancing RNG state produces statistically independent samples from the same distribution.

cpp

// C++17
#include <algorithm>
#include <random>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> population(100);
    std::iota(population.begin(), population.end(), 0);

    std::mt19937 rng{std::random_device{}()};
    std::vector<int> draw(10);

    for (int fold = 0; fold < 5; ++fold) {
        std::sample(population.begin(), population.end(),
                    draw.begin(), 10, rng);  // C++17
        std::cout << "Fold " << fold << ": ";
        for (int v : draw) std::cout << v << ' ';
        std::cout << '\n';
    }
    // Each fold is independent; elements may repeat across folds
}

When you need k samples that collectively cover the population exactly once (partition-style), Fisher-Yates shuffle followed by slicing is clearer and more efficient than repeated std::sample calls.

cpp

// C++11 — partition population into k non-overlapping samples of size n
#include <algorithm>
#include <random>
#include <vector>

int main() {
    std::vector<int> population(50);
    std::iota(population.begin(), population.end(), 0);

    std::mt19937 rng{std::random_device{}()};
    std::shuffle(population.begin(), population.end(), rng);  // C++11

    constexpr int n = 10;
    // population[0..9], [10..19], ... are now 5 non-overlapping samples
    for (int i = 0; i < 5; ++i) {
        auto begin = population.begin() + i * n;
        auto end   = begin + n;
        // use [begin, end) as fold i
    }
}

std::shuffle is O(N) and touches every element; std::sample for a single small draw is also O(N) but writes only k elements. For large populations with small k, std::sample avoids the full shuffle overhead and keeps the original order.

Stratified Sampling

Stratified sampling ensures each subgroup (stratum) is represented proportionally in the output, which simple random sampling may fail to guarantee for small or imbalanced populations.

A common pattern is to sort (or partition) the population by category, then apply std::sample independently within each stratum. std::partition_point locates stratum boundaries in O(log N) when the range is already partitioned.

cpp

// C++17
#include <algorithm>
#include <random>
#include <vector>
#include <iostream>

struct Record { int label; double value; };

int main() {
    // Sorted by label: 0=negative (70%), 1=positive (30%)
    std::vector<Record> data = {
        {0,1.1},{0,2.2},{0,3.3},{0,4.4},{0,5.5},{0,6.6},{0,7.7},
        {1,8.8},{1,9.9},{1,10.0}
    };

    // Find boundary between label 0 and label 1
    auto boundary = std::partition_point(data.begin(), data.end(),
                                         [](const Record& r){ return r.label == 0; });

    std::mt19937 rng{std::random_device{}()};

    // Sample proportionally: 4 from label-0, 2 from label-1 (60/40 → 4/2)
    std::vector<Record> train;
    train.reserve(6);
    std::sample(data.begin(), boundary,
                std::back_inserter(train), 4, rng);  // C++17
    std::sample(boundary, data.end(),
                std::back_inserter(train), 2, rng);  // C++17

    std::cout << "Training set (" << train.size() << " records):\n";
    for (auto& r : train)
        std::cout << "  label=" << r.label << " value=" << r.value << '\n';
    // Guaranteed: 4 negatives and 2 positives — class balance preserved
}

For multi-class problems, collect stratum iterators into a small array and loop. The sample size per stratum is typically round(stratum_size / total_size * desired_total), with any rounding residual assigned to the largest stratum.

Bootstrap Sampling (With Replacement)

Bootstrap sampling draws n elements from a population with replacement — the same element can appear multiple times in a single draw. This differs fundamentally from std::sample (without replacement) and is the basis for bootstrap confidence intervals and bagging in ensemble learning.

The standard library has no dedicated bootstrap function; the pattern is to generate random indices with std::uniform_int_distribution and look up elements directly.

cpp

// C++11
#include <random>
#include <vector>
#include <numeric>
#include <iostream>
#include <algorithm>
#include <cmath>

int main() {
    std::vector<double> population = {2.3, 5.1, 3.8, 7.2, 4.0,
                                      6.5, 1.9, 8.4, 3.3, 5.9};
    const int N = static_cast<int>(population.size());

    std::mt19937 rng{std::random_device{}()};
    std::uniform_int_distribution<int> pick(0, N - 1);  // C++11

    constexpr int B = 10'000;  // bootstrap iterations
    std::vector<double> boot_means(B);

    for (int b = 0; b < B; ++b) {
        double sum = 0.0;
        for (int i = 0; i < N; ++i)
            sum += population[pick(rng)];  // with replacement
        boot_means[b] = sum / N;
    }

    // 95% bootstrap confidence interval for the mean
    std::sort(boot_means.begin(), boot_means.end());  // C++11
    std::cout << "95% CI: ["
              << boot_means[static_cast<int>(0.025 * B)] << ", "
              << boot_means[static_cast<int>(0.975 * B)] << "]\n";
}

std::generate_n with a lambda is an idiomatic one-liner for filling a bootstrap sample buffer when the downstream consumer expects a pre-filled vector.

cpp

// C++11
std::vector<double> boot(N);
std::generate_n(boot.begin(), N, [&]{ return population[pick(rng)]; });

Contrast with std::sample. std::sample guarantees every element appears at most once in the output (without replacement); bootstrap sampling allows duplicates (with replacement). Choose std::sample for train/test splits and audit subsets; choose bootstrap for variance estimation and confidence intervals.

Thread-Safe Sampling and RNG Seeding

Sharing a single std::mt19937 across threads without synchronisation is a data race. The canonical solution is thread_local storage, which gives each thread its own independent engine at zero contention cost.

cpp

// C++11 — one engine per thread, no mutex required
#include <random>
#include <thread>
#include <algorithm>
#include <vector>

thread_local std::mt19937 tl_rng{std::random_device{}()};  // C++11

void worker(const std::vector<int>& pop, int k) {
    std::vector<int> out(k);
    std::sample(pop.begin(), pop.end(), out.begin(), k, tl_rng);  // C++17
    // process out ...
}

Seeding all threads from the same std::mt19937 instance produces correlated sequences. If you generate seeds for worker threads with a shared engine, two threads seeded with adjacent outputs from a low-quality generator can produce highly correlated streams. A simple mitigation is to XOR each seed with a hash of the thread id.

cpp

// C++11 — distinct, uncorrelated seeds per thread
#include <random>
#include <thread>
#include <functional>

std::mt19937 make_thread_rng() {
    auto base = std::random_device{}();              // C++11 hardware entropy
    auto tid  = std::hash<std::thread::id>{}(       // C++11 thread id hash
                    std::this_thread::get_id());
    return std::mt19937(base ^ static_cast<unsigned>(tid));
}

thread_local std::mt19937 tl_rng{make_thread_rng()};

For applications that require stronger guarantees — such as cryptographic simulation or reproducible parallel experiments — use std::seed_seq to mix multiple entropy sources into a full 624-word state, rather than a single 32-bit seed.

cpp

// C++11 — full-state seeding with seed_seq
#include <random>

std::mt19937 make_seeded_rng() {
    std::random_device rd;
    // Feed multiple 32-bit words from the hardware source
    std::seed_seq seq{rd(), rd(), rd(), rd(), rd(), rd(), rd(), rd()};  // C++11
    return std::mt19937{seq};
}

Avoid reseeding the engine on every std::sample call. Reseeding destroys the statistical independence guarantees of the Mersenne Twister's period. Seed once per thread at construction, then reuse the engine for the lifetime of the thread.

See Also

std::shuffle — random permutation of an entire range (C++11)
std::ranges::sample — C++20 range-based overload returning in_out_result
<random> — URBG types, distributions, and seeding utilities (C++11)