1
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
  • 4
    \$\begingroup\$ Code not working: namesapce Did you test your code? ;) \$\endgroup\$ – L. F. Feb 5 at 4:58
  • \$\begingroup\$ It helps reviewers if you show the necessary #include lines, rather than us all having to figure out what's required. And I'd expect #include <iterator> in there, as it's impossible to instantiate the template without needing a definition of std::advance, even though it can be parsed without. \$\endgroup\$ – Toby Speight Feb 5 at 12:27
7
\$\begingroup\$

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));
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Technically, it should be std::ptrdiff_t. \$\endgroup\$ – user673679 Feb 5 at 8:10
  • \$\begingroup\$ @user673679 They're the same thing. It's personal preference whether you use ptrdiff_t or std::ptrdiff_t. I personally don't see the point in the extra 5 characters. \$\endgroup\$ – Indiana Kernick Feb 5 at 8:11
  • \$\begingroup\$ Yeah. I'd prefer to use the one that's guaranteed to exist. \$\endgroup\$ – user673679 Feb 5 at 8:22
  • 1
    \$\begingroup\$ There's one aspect you changed, but didn't mention explicitly, the use of C and G as names. One thing is that these single letters don't convey much information. Another thing is that these are ALL_UPPERCASE, so one could even mistake them for macros. \$\endgroup\$ – uli Feb 5 at 12:20
  • \$\begingroup\$ @uli I did mention this under Short names. I don't think they could be mistaken for macros as it's pretty common to use single character names for template parameters (thanks Java!). Sometimes you can't be more specific than "a type" so you just use T. \$\endgroup\$ – Indiana Kernick Feb 5 at 13:06
3
\$\begingroup\$

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.
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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).

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The const overload isn't necessary. If Container is const, begin will return a const iterator. random_reference won't uses the subscription operator so it will only work on vectors and arrays. random_reference should probably call random_iterator. I'm really glad that ADL nonsense is hidden away in std::ranges::*. That's one "pattern" that I really dislike. I'm guessing std::swap still has the same problem though. \$\endgroup\$ – Indiana Kernick Feb 5 at 21:12
  • \$\begingroup\$ Jeez, I clearly didn't proofread that comment before sending it! \$\endgroup\$ – Indiana Kernick Feb 5 at 23:06
  • 1
    \$\begingroup\$ Don't believe I need different variants for cont and non const versions. The Type C will automatically adapt to both versions correctly. Most containers have two versions of begin() a const and a non const version. \$\endgroup\$ – Martin York Feb 5 at 23:52

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.