paperjam paperjam - 2 months ago 8
C++ Question

get random element from 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?

Answer

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.