function template
<algorithm>
std::shuffle
template <class RandomAccessIterator, class URNG>
void shuffle (RandomAccessIterator first, RandomAccessIterator last, URNG&& g);
Randomly rearrange elements in range using generator
Rearranges the elements in the range [first,last) randomly, using g as uniform random number generator.
The function swaps the value of each element with that of some other randomly picked element. The function determines the element picked by calling g().
This function works with standard generators as those defined in <random>. To shuffle the elements of the range without such a generator, see random_shuffle instead.
The behavior of this function template is equivalent to:
1
2
3
4
5
6
7
8
|
template <class RandomAccessIterator, class URNG>
void shuffle (RandomAccessIterator first, RandomAccessIterator last, URNG&& g)
{
for (auto i=(last-first)-1; i>0; --i) {
std::uniform_int_distribution<decltype(i)> d(0,i);
swap (first[i], first[d(g)]);
}
}
|
Parameters
- first, last
- Forward 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.
ForwardIterator shall point to a type for which swap is defined and swaps the value of its arguments.
- g
- A uniform random number generator, used as the source of randomness.
URNG shall be a uniform random number generator, such as one of the standard generator classes (see <random> for more information).
Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
// shuffle algorithm example
#include <iostream> // std::cout
#include <algorithm> // std::move_backward
#include <array> // std::array
#include <random> // std::default_random_engine
#include <chrono> // std::chrono::system_clock
int main () {
std::array<int,5> foo {1,2,3,4,5};
// obtain a time-based seed:
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
shuffle (foo.begin(), foo.end(), std::default_random_engine(seed));
std::cout << "shuffled elements:";
for (int& x: foo) std::cout << ' ' << x;
std::cout << '\n';
return 0;
}
|
Possible output:
shuffled elements: 3 1 4 2 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.