Convenience function wrapping C++17's std::sample for distance=1 case

Question

C++ has the function std::sample which randomly samples from a range and places the results via an output iterator. My goal is to create a utility that directly returns a single value in the event that we only want to sample a single random element from the container.

#include <iostream>
#include <random>
#include <algorithm>
#include <iterator>
#include <unordered_set>
#include <array>

template<class InputIt, class URBG>
auto singleRandomSample(InputIt t_begin, InputIt t_end, URBG&& rng)
{
    using value_type = typename std::iterator_traits<InputIt>::value_type;
    std::array<value_type, 1> out;
    std::sample(t_begin, t_end, out.begin(), 1, rng);
    return out.at(0);
}


int main()
{
    std::default_random_engine rng{ std::random_device{}() };
    std::unordered_set<char> vowels{ 'a', 'e', 'i', 'o', 'u', 'y' };
    for (std::size_t i = 0; i < 10; ++i)
    {
        auto randomVowel = singleRandomSample(vowels.begin(), vowels.end(), rng);
        std::cout << "Random vowel: " << randomVowel << '\n';
    }
}

This function creates a temporary container out to which a single element is added, then returns that element by value. It uses an std::array because I know I only need room for a single element, although if I decided it was important to be able to use this with non-default-constructible types I could switch to a std::vector and a std::back_inserter.

Is it correct to call std::sample using rng as an argument directly, or should I be using std::forward(rng)?

It feels slightly clunky to have an entire temporary container just to store a single value that's immediately returned. Is there another way this functionality could be implemented?

Answer 1

A pointer is an iterator.

template <typename InputIterator, typename URBG>
auto singleRandomSample(InputIterator first, InputIterator last, URBG&& rng)
{
    using value_type = typename std::iterator_traits<InputIterator>::value_type;

    auto result = value_type{};

    std::sample(first, last, &result, 1, std::forward<URBG>(rng));

    return result;
}

Or, with a better, C++20 interface:

template <std::input_iterator I, std::sentinel_for<I> S, typename URBG>
    requires std::uniform_random_bit_generator<std::remove_reference_t<URBG>>
auto singleRandomSample(I first, S last, URBG&& rng)
{
    auto result = std::iter_value_t<I>{};

    std::ranges::sample(first, last, &result, 1, std::forward<URBG>(rng));

    return result;
}

template <std::input_range R, typename URBG>
    requires std::uniform_random_bit_generator<std::remove_reference_t<URBG>>
auto singleRandomSample(R&& r, URBG&& rng)
{
    auto result = std::ranges::range_value_t<R>{};

    std::ranges::sample(r, &result, 1, std::forward<URBG>(rng));

    return result;
}

This requires the value type of the range to be default-constructible, but you were already counting on that with the array solution.

If you want a solution that does not require default construction, you could probably do something like using an optional type—like std::optional, or std::variant with std::monostate—and a custom output iterator that does an emplace into it.

Answer 2

Interface

First of all, I would consider usage cases. If there is significant need for sampling from one-pass-only sequences (streaming from a file or network), then I would keep current interface of returning selected value. This might open a can of worms though.

Otherwise I would tighten iterator requirement to forward iterator and return that iterator. Such interface would free from dealing with non-X-constructible types (where X is one or more from default, copy and move).

I would name the function as below:

• sample_single_value (in case of first interface)

• select_uniformly (second interface)

• pick_uniformly (second interface, though don’t like this one much)

Implementation

After checking out libstdc++ and libc++, it seems like both implement reservoir sampling, which is not hard to implement by hand for the second interface. For the first interface the current implementation looks fine (writing by hand would be more error prone and less readable).

Optimization for random access iterator case

One might be tempted to optimize for the case when population size is known, but due to the nature of RNG source being non-reentrant, the optimization will very likely produce different result due to difference in number of RNG invocations. I would not advise implementing the optimization, or at the very least I would put this quirk in big, bold, red font in the documentation.