Difference between revisions of "cpp/algorithm/sample"
(llvm-mirror was archived at the end of 2019. It was replaced with https://github.com/llvm/llvm-project) |
(Add link to msvc stl implementation) |
||
| Line 43: | Line 43: | ||
===Possible implementation=== | ===Possible implementation=== | ||
| − | See | + | See the implementations in [https://github.com/gcc-mirror/gcc/blob/d9375e490072d1aae73a93949aa158fcd2a27018/libstdc%2B%2B-v3/include/bits/stl_algo.h#L5703 libstdc++], [https://github.com/llvm-project/libcxx/blob/a12cb9d211019d99b5875b6d8034617cbc24c2cc/include/algorithm#L3110 libc++] and [https://github.com/microsoft/STL/blob/c10ae01b4d9508eed9d5f059a120ee7223b6ac12/stl/inc/algorithm#L4629 msvc]. |
===Example=== | ===Example=== | ||
Revision as of 12:30, 23 July 2020
| Defined in header <algorithm>
|
||
| template< class PopulationIterator, class SampleIterator, class Distance, class URBG > |
(since C++17) | |
Selects n elements from the sequence [first; last) (without replacement) 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 (preserves the relative order of the selected elements) only if PopulationIterator meets the requirements of LegacyForwardIterator
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 |
-PopulationIterator must meet the requirements of LegacyInputIterator.
| ||
-SampleIterator must meet the requirements of LegacyOutputIterator.
| ||
-SampleIterator must also meet the requirements of LegacyRandomAccessIterator if PopulationIterator doesn't meet LegacyForwardIterator
| ||
-PopulationIterator's value type must be writeable to out
| ||
-Distance must be an integer type
| ||
-std::remove_reference_t<URBG> must meet the requirements of UniformRandomBitGenerator 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.
Possible implementation
See the implementations in libstdc++, libc++ and msvc.
Example
#include <iostream> #include <random> #include <string> #include <iterator> #include <algorithm> int main() { std::string in = "hgfedcba", 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 hgfedcba: gfcba
See also
| (until C++17)(C++11) |
randomly re-orders elements in a range (function template) |
