Get a random member of a container

Question

It was not obvious how to get a random member of a container. So I wrote a function to retrieve it given a generator.

namesapce ThorsAnvil
{
    namespace Util
    {
        using Distribution = std::uniform_int_distribution<int>;

        /* Get a distribution from [0, max)   */
        /* None maths nerds: Note the [ and ) */
        Distribution getDist(int max)
        {
            return Distribution{0, max - 1};
        }

        template<typename C, typename G>
        auto getRandomIteratorFromContainer(C& container, G& generator)
        {
            auto pos = container.begin();

            int     offset  = getDist(container.size())(generator);
            std::advance(pos, offset);

            return pos;
        }
    }
}

Answer 1

Long name

ThorsAnvil::Util::getRandomIteratorFromContainer is a really long name. I suggest something like getRandomElement or even randomElement.

Unnecessary function

getDist seems kind of unnecessary to me. I think it would be cleaner to construct the distribution directly.

std::uniform_int_distruction<int> dist{0, container.size() - 1};

Types

The integer type used for iterator arithmetic is typename C::difference_type. This is almost always equivalent to std::ptrdiff_t so to be crystal clear, use std::ptrdiff_t.

std::uniform_int_distruction<std::ptrdiff_t> dist{0, container.size() - 1};

Unnecessary variable

offset is initialized with a random offset and is only used once. If it's only used once then it doesn't really need to exist.

std::advance(pos, dist(generator));

Wrong function

std::advance modifies an existing iterator. This means that we need store the iterator, advance it, then return the iterator. That's three steps. std::next takes an iterator and returns an incremented one.

return std::next(container.begin(), dist(generator));

Covering all cases

Using .begin() and .size() is a little bit restrictive. If we use std::begin and std::size, this function will work on C-style arrays which is a nice. If we want to be even more general (as Toby mentioned in the comments), we can let ADL pick up the right function for containers that declare their own begin and size functions.

using std::begin;
using std::size;

Short names

My answer has been pretty nitpicky so far but this is particularly nitpicky. Long template parameter names that clearly describe the parameter are better than single character names.

template <typename Container, typename Generator>

How I would write it

After applying the above transformations. We get this function:

template <typename Container, typename Generator>
auto random_element(Container &con, Generator &gen) {
  using std::begin;
  using std::size;
  std::uniform_int_distribution<std::ptrdiff_t> dist{0, size(con) - 1};
  return std::next(begin(con), dist(gen));
}

Answer 2

In addition to Kerndog73's answer:

• Don't forget to check for an empty container to avoid undefined behavior. We should probably return the end() iterator in that case.

Answer 3

Instead of accepting a container, accept an iterator pair. We may want to use just part of a container (e.g. after using std::partition). In C++20, a standard forward_range view could be used.

It probably makes sense to use different implementations for forward-access and random-access collections (there's a single-pass algorithm for selecting 1 out of an unknown number of elements, so we could even accept input iterators).

Answer 4

I think you should clarify what you want. Depending on that, the answer will be slightly different.

If you want an iterator to a random element then Kerndog's answer is really close:

template <typename Container, typename Generator>
auto random_iterator(Container &con, Generator &gen) {
  using std::begin;
  using std::size;
  std::uniform_int_distribution<std::ptrdiff_t> dist{0, size(con) - 1};
  return std::next(begin(con), dist(gen));
}

template <typename Container, typename Generator>
auto random_iterator(const Container &con, Generator &gen) {
  using std::cbegin;
  using std::size;
  std::uniform_int_distribution<std::ptrdiff_t> dist{0, size(con) - 1};
  return std::next(cbegin(con), dist(gen));
}

Note that there should be a const/non-const overload.

If you only want the element from the container you should retrieve it or get a reference?

template <typename Container, typename Generator>
auto random_reference(const Container &con, Generator &gen) {
  using std::size;
  std::uniform_int_distribution<std::size_t> dist{0, size(con) - 1};
  return con[dist(gen)];
}

Which standard do you use? If C++20 is possible then you should use at least the range concept and ranges::size:

template <range Container, typename Generator>
auto random_const_iterator(const Container &con, Generator &gen) {
  std::uniform_int_distribution<std::ptrdiff_t> dist{0, std::ranges::size(con) - 1};
  return std::next(std::ranges::cbegin(con), dist(gen));
}

Note that std::ranges::size/std::ranges::cbegin are customization point objects (CPOs), so you should call them qualified; you do not need to use ADL as that is already inside the mechanics of the CPO.