random_shuffle
function template
<algorithm>
template <class RandomAccessIterator>
void random_shuffle ( RandomAccessIterator first, RandomAccessIterator last );
template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle ( RandomAccessIterator first, RandomAccessIterator last,
RandomNumberGenerator& rand );
Rearrange elements in range randomly
Rearranges the elements in the range [first,last) randomly.
The function swaps the value of each element with that of some other randomly chosen element. When provided, the function rand chooses which element.
The behavior of this function template is equivalent to:
1
2
3
4
5
6
7
8
|
template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle ( RandomAccessIterator first, RandomAccessIterator last,
RandomNumberGenerator& rand )
{
iterator_traits<RandomAccessIterator>::difference_type i, n;
n = (last-first);
for (i=n-1; i>0; --i) swap (first[i],first[rand(i+1)]);
}
|
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.
- rand
- Pointer to unary function taking one argument and returning a value, both of the appropriate difference type (generally ptrdiff_t). The function shall return a value between zero and its argument (lower than this).
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
33
34
35
36
37
38
|
// random_shuffle example
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;
// random generator function:
ptrdiff_t myrandom (ptrdiff_t i) { return rand()%i;}
// pointer object to it:
ptrdiff_t (*p_myrandom)(ptrdiff_t) = myrandom;
int main () {
srand ( unsigned ( time (NULL) ) );
vector<int> myvector;
vector<int>::iterator it;
// 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:
random_shuffle ( myvector.begin(), myvector.end() );
// using myrandom:
random_shuffle ( myvector.begin(), myvector.end(), p_myrandom);
// print out content:
cout << "myvector contains:";
for (it=myvector.begin(); it!=myvector.end(); ++it)
cout << " " << *it;
cout << endl;
return 0;
}
|
A possible output:
myvector contains: 3 4 1 6 8 9 2 7 5
|
Complexity
Linear: As many calls to swap as the length of the range [first,last) minus 1.
See also
| rotate | Rotate elements in range (function template) |
| reverse | Reverse range (function template) |
| generate | Generate values for range with function (function template) |
| swap | Exchange values of two objects (function template) |
|