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


C++ Problem Overview

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?

C++ Solutions

Solution 1 - C++

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.

Solution 2 - C++

C++17 std::sample

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


#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;
    for (auto i : out)
        std::cout << i << std::endl;

Compile and run:

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

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.

Solution 3 - C++

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.

Solution 4 - C++

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());

Solution 5 - C++

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;

Solution 6 - C++

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

Solution 7 - C++

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

Solution 8 - C++

#include <vector>
using std::vector;

vector<int> vi = {1, 2, 3, 4, 5};
randomPosition = rand() % vi.size();
randomElement = vi[randomPosition]

srand(time(0)) seed for random, if not use it, it will get same random integer every execution.

Solution 9 - C++

You can use 0~1 random function to generate a float number for every element in the container as its score. And then select the one with highest score.


All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionpaperjamView Question on Stackoverflow
Solution 1 - C++Christopher SmithView Answer on Stackoverflow
Solution 2 - C++Ciro Santilli Путлер Капут 六四事View Answer on Stackoverflow
Solution 3 - C++Alexandre C.View Answer on Stackoverflow
Solution 4 - C++cprogrammerView Answer on Stackoverflow
Solution 5 - C++Dave SView Answer on Stackoverflow
Solution 6 - C++ypnosView Answer on Stackoverflow
Solution 7 - C++CedekasmeView Answer on Stackoverflow
Solution 8 - C++maxView Answer on Stackoverflow
Solution 9 - C++zccView Answer on Stackoverflow