How to get a random element from a C++ container?

Question

What is a good way to get a [pseudo-]random element from an STL range?

The best I can come up with is to do std::random_shuffle(c.begin(), c.end()) and then take my random element from c.begin().

However, I might want a random element from a const container, or I might not want the cost of a full shuffle.

Is there a better way?

Answer 1

I posted this solution on a Google+ article where someone else referenced this. Posting it here, as this one is slightly better than others because it avoids bias by using std::uniform_int_distribution:

#include  <random>
#include  <iterator>

template<typename Iter, typename RandomGenerator>
Iter select_randomly(Iter start, Iter end, RandomGenerator& g) {
    std::uniform_int_distribution<> dis(0, std::distance(start, end) - 1);
    std::advance(start, dis(g));
    return start;
}

template<typename Iter>
Iter select_randomly(Iter start, Iter end) {
    static std::random_device rd;
    static std::mt19937 gen(rd());
    return select_randomly(start, end, gen);
}

Sample use is:

#include <vector>
using namespace std;

vector<int> foo;
/* .... */
int r = *select_randomly(foo.begin(), foo.end());

I ended up creating a gist with a better design following a similar approach.

Answer 2

C++17 std::sample

This is a convenient method to get several random elements without repetition.

main.cpp

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

int main() {
    const std::vector<int> in{1, 2, 3, 5, 7};
    std::vector<int> out;
    size_t nelems = 3;
    std::sample(
        in.begin(),
        in.end(),
        std::back_inserter(out),
        nelems,
        std::mt19937{std::random_device{}()}
    );
    for (auto i : out)
        std::cout << i << std::endl;
}

Compile and run:

g++-7 -o main -std=c++17 -Wall -Wextra -pedantic main.cpp
./main

Output: 3 random numbers are picked from 1, 2, 3, 5, 7 without repetition.

For efficiency, only O(n) is guaranteed since ForwardIterator is the used API, but I think stdlib implementations will specialize to O(1) where possible (e.g. vector).

Tested in GCC 7.2, Ubuntu 17.10. How to obtain GCC 7 in 16.04.

Answer 3

All the answers using % here are incorrect, since rand() % n will produce biased results: imagine RAND_MAX == 5 and the number of elements is 4. Then you'll get twice more the number 0 and 1 than the numbers 2 or 3.

A correct way to do this is:

template <typename I>
I random_element(I begin, I end)
{
    const unsigned long n = std::distance(begin, end);
    const unsigned long divisor = (RAND_MAX + 1) / n;

    unsigned long k;
    do { k = std::rand() / divisor; } while (k >= n);

    std::advance(begin, k);
    return begin;
}

Another problem is that std::rand is only assumed to have 15 random bits, but we'll forget about this here.

Answer 4

This works fine as long as RAND_MAX is much greater than the container size, otherwise it suffers from the bias problem cited by Alexandre:

vector<int>::iterator randIt = myvector.begin();
std::advance(randIt, std::rand() % myvector.size());

Answer 5

If you can't access the size, I think you would want to do the following. It returns the iterator to the random element.

#include <algorithm>
#include <iterator>

template <class InputIterator> InputIterator 
random_n(InputIterator first, InputIterator last) {
   typename std::iterator_traits<InputIterator>::difference_type distance = 
        std::distance(first, last);
   InputIterator result = first;
   if (distance > 1) {
      // Uses std::rand() naively.  Should replace with more uniform solution. 
      std::advance( result, std::rand() % distance );
   }
   return result;
}
// Added in case you want to specify the RNG.  RNG uses same 
// definition as std::random_shuffle
template <class InputIterator, class RandomGenerator> InputIterator 
random_n(InputIterator first, InputIterator last, RandomGenerator& rand) {
   typename std::iterator_traits<InputIterator>::difference_type distance = 
       std::distance(first, last);
   InputIterator result = first;
   if (distance > 1) {
      std::advance( result, rand(distance) );
   }
   return result;
}

Answer 6

Take the number of elements, c.size(), then get a random_number between 0 and c.size(), and use:

auto it = c.begin();
std::advance(it, random_number)

Have a look at http://www.cplusplus.com/reference/clibrary/cstdlib/rand/

Answer 7

You can try to get a random number between 0 and the number of elements of the container. You could then access to the corresponding element of the container. For example, you can do this:

#include <cstdlib>
#include <ctime>

// ...
std::srand(std::time(0)); // must be called once at the start of the program
int r = std::rand() % c.size() + 1; 
container_type::iterator it = c.begin();
std::advance(it, r);