Difference between revisions of "cpp/algorithm/sample"
(+ (using only the v1 5-argument overload despite P0220R1 because that was the intent (per reflector) and that's what was committed to the draft)) |
m (0346R1: URNG -> URBG) |
||
| Line 6: | Line 6: | ||
{{dcl |since=c++17 | | {{dcl |since=c++17 | | ||
template< class PopulationIterator, class SampleIterator, | template< class PopulationIterator, class SampleIterator, | ||
| − | class Distance, class | + | class Distance, class UniformRandomBitGenerator > |
SampleIterator sample( PopulationIterator first, PopulationIterator last, | SampleIterator sample( PopulationIterator first, PopulationIterator last, | ||
SampleIterator out, Distance n, | SampleIterator out, Distance n, | ||
| − | + | UniformRandomBitGenerator&& g); | |
}} | }} | ||
{{dcl end}} | {{dcl end}} | ||
| Line 30: | Line 30: | ||
{{par req | {{tt|PopulationIterator}}'s value type must be writeable to {{tt|out}}}} | {{par req | {{tt|PopulationIterator}}'s value type must be writeable to {{tt|out}}}} | ||
{{par req | {{tt|Distance}} must be an integer type}} | {{par req | {{tt|Distance}} must be an integer type}} | ||
| − | {{par req | {{tt| | + | {{par req | {{tt|UniformRandomBitGenerator}} must meet the requirements of {{concept|UniformRandomBitGenerator}} and its return type must be convertible to {{tt|Distance}}}} |
{{par end}} | {{par end}} | ||
Revision as of 10:21, 24 June 2016
| Defined in header <algorithm>
|
||
| template< class PopulationIterator, class SampleIterator, class Distance, class UniformRandomBitGenerator > |
(since C++17) | |
Selects n elements from the sequence [first; last) such that each possible sample has equal probability of appearance, and writes those selected elements into the output iterator out. Random numbers are generated using the random number generator g.
If n is greater than the number of elements in the sequence, selects last-first elements.
The algorithm is stable only if PopulationIterator meets the requirements of Template:concept
Contents |
Parameters
| first, last | - | pair of iterators forming the range from which to make the sampling (the population) |
| out | - | the output iterator where the samples are written. Must not be in the [first;last) range |
| n | - | number of samples to make |
| g | - | the random number generator used as the source of randomness |
-SampleIterator must also meet the requirements of Template:concept if PopulationIterator doesn't meet Template:concept
| ||
-PopulationIterator's value type must be writeable to out
| ||
-Distance must be an integer type
| ||
-UniformRandomBitGenerator must meet the requirements of Template:concept and its return type must be convertible to Distance
| ||
Return value
Returns a copy of out after the last sample that was output, that is, end of the sample range.
Complexity
Linear in std::distance(first,last)
Notes
This function may implement selection sampling or reservoir sampling.
Example
#include <iostream> #include <random> #include <string> #include <iterator> #include <algorithm> int main() { std::string in = "abcdefgh", out; std::sample(in.begin(), in.end(), std::back_inserter(out), 5, std::mt19937{std::random_device{}()}); std::cout << "five random letters out of " << in << " : " << out << '\n'; }
Possible output:
five random letters out of abcdefgh : cdefg
See also
| (until C++17)(C++11) |
randomly re-orders elements in a range (function template) |
