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::shuffle
#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.