function template
<algorithm>

std::random_shuffle

generator by default (1)
template <class RandomAccessIterator>
  void random_shuffle (RandomAccessIterator first, RandomAccessIterator last);
specific generator (2)
template <class RandomAccessIterator, class RandomNumberGenerator>
  void random_shuffle (RandomAccessIterator first, RandomAccessIterator last,
                       RandomNumberGenerator& gen);
generator by default (1)
template <class RandomAccessIterator>
  void random_shuffle (RandomAccessIterator first, RandomAccessIterator last);
specific generator (2)
template <class RandomAccessIterator, class RandomNumberGenerator>
  void random_shuffle (RandomAccessIterator first, RandomAccessIterator last,
                       RandomNumberGenerator&& gen);
Randomly rearrange elements in range
Rearranges the elements in the range [first,last) randomly.

The function swaps the value of each element with that of some other randomly picked element. When provided, the function gen determines which element is picked in every case. Otherwise, the function uses some unspecified source of randomness.

To specify a uniform random generator as those defined in <random>, see shuffle.

The behavior of this function template (2) is equivalent to:
1
2
3
4
5
6
7
8
9
10
template <class RandomAccessIterator, class RandomNumberGenerator>
  void random_shuffle (RandomAccessIterator first, RandomAccessIterator last,
                       RandomNumberGenerator& gen)
{
  iterator_traits<RandomAccessIterator>::difference_type i, n;
  n = (last-first);
  for (i=n-1; i>0; --i) {
    swap (first[i],first[gen(i+1)]);
  }
}


Parameters

first, last
Random-access iterators to the initial and final positions of the sequence to be shuffled. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
gen
Unary function taking one argument and returning a value, both convertible to/from the appropriate difference type used by the iterators. The function shall return a non-negative value less than its argument.
This can either be a function pointer or a function object.

RandomAccessIterator shall point to a type for which swap is defined and swaps the value of its arguments.

Return value

none

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// random_shuffle example
#include <iostream>     // std::cout
#include <algorithm>    // std::random_shuffle
#include <vector>       // std::vector
#include <ctime>        // std::time
#include <cstdlib>      // std::rand, std::srand

// random generator function:
int myrandom (int i) { return std::rand()%i;}

int main () {
  std::srand ( unsigned ( std::time(0) ) );
  std::vector<int> myvector;

  // set some values:
  for (int i=1; i<10; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9

  // using built-in random generator:
  std::random_shuffle ( myvector.begin(), myvector.end() );

  // using myrandom:
  std::random_shuffle ( myvector.begin(), myvector.end(), myrandom);

  // print out content:
  std::cout << "myvector contains:";
  for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;

  std::cout << '\n';

  return 0;
}


Possible output:
myvector contains: 3 4 1 6 8 9 2 7 5

Complexity

Linear in the distance between first and last minus one: Obtains random values and swaps elements.

Data races

The objects in the range [first,last) are modified.

Exceptions

Throws if any of the random number generations, the element swaps or the operations on iterators throws.
Note that invalid arguments cause undefined behavior.

See also