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

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?

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

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