Difference between revisions of "cpp/algorithm/random shuffle"
From cppreference.com
(+shuffle) |
(here's what the new shuffle() does. tested with gcc 4.5.3. BTW old shuffle has different prototype in C++11 (takes an rvalue reference instead of lvalue reference), how does this wiki express that?) |
||
| Line 10: | Line 10: | ||
template< class RandomAccessIterator, RandomNumberGenerator r > | template< class RandomAccessIterator, RandomNumberGenerator r > | ||
void random_shuffle( RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& r ); | void random_shuffle( RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& r ); | ||
| + | }} | ||
| + | {{ddcl list item | num=3 | notes={{mark c++11 feature}} | | ||
| + | template< class RandomAccessIterator, UniformRandomNumberGenerator g > | ||
| + | void shuffle( RandomAccessIterator first, RandomAccessIterator last, UniformRandomNumberGenerator&& g ); | ||
}} | }} | ||
{{ddcl list end}} | {{ddcl list end}} | ||
| − | + | Reorders the elements in the given range {{tt|[first, last)}} such that each possible permutation of those elements has equal probability of appearance. | |
| − | + | 1) The random number generator is implementation-defined, the {{cpp|rand}} function may be used. | |
| − | Reorders the elements in the given range {{tt|[first, last)}} | + | 2) The random number generator is the function object {{tt|r}}. |
| + | 3) The random number generator is the function object {{tt|g}}. | ||
===Parameters=== | ===Parameters=== | ||
{{param list begin}} | {{param list begin}} | ||
{{param list item | first, last | the range of elements to shuffle randomly}} | {{param list item | first, last | the range of elements to shuffle randomly}} | ||
| − | {{param list item | r | function, returning a | + | {{param list item | r | function object returning a randomly chosen value in the interval [0,n) if invoked as {{tt|r(n)}} }} |
| + | {{param list item | g | function object returning a randomly chosen value in the interval [g.min(), g.max()] if invoked as {{tt|g()}} (intended to be used with uniform random number generators from the standard library) }} | ||
{{param list end}} | {{param list end}} | ||
| Line 42: | Line 48: | ||
} | } | ||
}} | }} | ||
| + | {{todo|reason=shuffle}} | ||
===Example=== | ===Example=== | ||
{{example cpp | {{example cpp | ||
| − | | | + | | The following code randomly shuffles the integers 1..10 |
| code= | | code= | ||
| + | #include <random> | ||
| + | #include <algorithm> | ||
| + | #include <iterator> | ||
| + | #include <iostream> | ||
| + | int main() | ||
| + | { | ||
| + | std::random_device rd; | ||
| + | std::mt19937 g(rd()); | ||
| + | std::vector<int> v = {1,2,3,4,5,6,7,8,9,10}; | ||
| + | std::shuffle(v.begin(), v.end(), g); | ||
| + | copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " ")); | ||
| + | std::cout << '\n'; | ||
| + | } | ||
| output= | | output= | ||
| − | + | 8 6 10 4 2 3 7 1 9 5 | |
}} | }} | ||
Revision as of 13:54, 12 August 2011
Template:cpp/algorithm/sidebar Template:ddcl list begin <tr class="t-dsc-header">
<td>Defined in header
</td>
<algorithm>
<td></td> <td></td> </tr> <tr class="t-dcl ">
<td >template< class RandomAccessIterator >
void random_shuffle( RandomAccessIterator first, RandomAccessIterator last );
</td>
void random_shuffle( RandomAccessIterator first, RandomAccessIterator last );
<td > (1) </td> <td class="t-dcl-nopad"> </td> </tr> <tr class="t-dcl ">
<td >template< class RandomAccessIterator, RandomNumberGenerator r >
void random_shuffle( RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& r );
</td>
void random_shuffle( RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& r );
<td > (2) </td> <td class="t-dcl-nopad"> </td> </tr> <tr class="t-dcl ">
<td >template< class RandomAccessIterator, UniformRandomNumberGenerator g >
void shuffle( RandomAccessIterator first, RandomAccessIterator last, UniformRandomNumberGenerator&& g );
</td>
void shuffle( RandomAccessIterator first, RandomAccessIterator last, UniformRandomNumberGenerator&& g );
<td > (3) </td> <td > Template:mark c++11 feature </td> </tr> Template:ddcl list end
Reorders the elements in the given range [first, last) such that each possible permutation of those elements has equal probability of appearance.
1) The random number generator is implementation-defined, the Template:cpp function may be used.
2) The random number generator is the function object r.
3) The random number generator is the function object g.
Contents |
Parameters
| first, last | - | the range of elements to shuffle randomly |
| r | - | function object returning a randomly chosen value in the interval [0,n) if invoked as r(n)
|
| g | - | function object returning a randomly chosen value in the interval [g.min(), g.max()] if invoked as g() (intended to be used with uniform random number generators from the standard library)
|
Return value
Complexity
linear in the distance between first and last
Equivalent function
| This section is incomplete Reason: shuffle |
