7
\$\begingroup\$

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?

\$\endgroup\$
1
  • \$\begingroup\$ My goal was to, as much as possible, delegate implementation details to std::sample. The theory is that std::sample already works, but in the specific case that we only want a single element we can simplify the return type. As you identified my implementation doesn't work with non-default constructible types although it's not hard to modify it to do so. It does work with things like associative containers which I consider nice. \$\endgroup\$ – Nathan Pierson May 20 at 19:54
4
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ I believe there is UB with this solution. Going one past the last element is allowed for arrays, but I’m not sure if it is allowed for objects. I don’t think it will cause problems with current compilers, but legality seems a bit unclear. \$\endgroup\$ – Incomputable May 20 at 20:19
  • 2
    \$\begingroup\$ No, there is no UB. You are allowed to increment one past any valid pointer. You just can’t dereference it. \$\endgroup\$ – indi May 20 at 20:22
  • \$\begingroup\$ Oh, it wouldn't have occurred to me to use a pointer as an output iterator, that's definitely much nicer than a std::array<value_type, 1>. And thank you for the C++20 version, it's very cool seeing examples of concepts and requirements for something like this. \$\endgroup\$ – Nathan Pierson May 20 at 20:28
  • 2
    \$\begingroup\$ Hm, realized I’d better back up my claim that it’s not UB. So [[expr.add] sub-subpara 4.2](eel.is/c++draft/expr.add#4.2) explains what we all understand about arrays and pointer arithmetic. But note the footnote: “… an object that is not an array element is considered to belong to a single-element array for this purpose…”. So as long as you have a pointer to a valid object—in an array or not—then you can always increment it at least once. If it is the last in an array—including a single-element array—you get a “one-past-the-end” pointer. \$\endgroup\$ – indi May 20 at 22:02
  • \$\begingroup\$ @indi, Thanks! I didn't know one element array and an object are equivalent. \$\endgroup\$ – Incomputable May 21 at 10:37
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.