25 Algorithms library [algorithms]

25.3 Mutating sequence operations [alg.modifying.operations]

25.3.12 Random shuffle [alg.random.shuffle]

template<class RandomAccessIterator> void random_shuffle(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class RandomNumberGenerator> void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator&& rand); template<class RandomAccessIterator, class UniformRandomNumberGenerator> void shuffle(RandomAccessIterator first, RandomAccessIterator last, UniformRandomNumberGenerator&& g);

Effects: Permutes the elements in the range [first,last) such that each possible permutation of those elements has equal probability of appearance.

Requires: RandomAccessIterator shall satisfy the requirements of ValueSwappable ([swappable.requirements]). The random number generating function object rand shall have a return type that is convertible to iterator_traits<RandomAccessIterator>::difference_type, and the call rand(n) shall return a randomly chosen value in the interval [0,n), for n > 0 of type iterator_traits<RandomAccessIterator>::difference_type. The type UniformRandomNumberGenerator shall meet the requirements of a uniform random number generator ([rand.req.urng]) type whose return type is convertible to iterator_traits<RandomAccessIterator>::difference_type.

Complexity: Exactly (last - first) - 1 swaps.

Remarks: To the extent that the implementation of these functions makes use of random numbers, the implementation shall use the following sources of randomness:

The underlying source of random numbers for the first form of the function is implementation-defined. An implementation may use the rand function from the standard C library.

In the second form of the function, the function object rand shall serve as the implementation's source of randomness.

In the third shuffle form of the function, the object g shall serve as the implementation's source of randomness.