| Constrained algorithms and algorithms on ranges(C++20) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Constrained algorithms, e.g.ranges::copy,ranges::sort, ... | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Execution policies(C++17) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Numeric operations | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Operations on uninitialized memory | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
std::ranges| Non-modifying sequence operations | |||||||||||||||||||||||||||||||||
| Modifying sequence operations | |||||||||||||||||||||||||||||||||
| Partitioning operations | |||||||||||||||||||||||||||||||||
| Sorting operations | |||||||||||||||||||||||||||||||||
| Binary search operations (on sorted ranges) | |||||||||||||||||||||||||||||||||
| Set operations (on sorted ranges) | |||||||||||||||||||||||||||||||||
| Heap operations | |||||||||||||||||||||||||||||||||
| Minimum/maximum operations | |||||||||||||||||||||||||||||||||
| Permutation operations | |||||||||||||||||||||||||||||||||
| Fold operations | |||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||
| Operations on uninitialized storage | |||||||||||||||||||||||||||||||||
| Return types | |||||||||||||||||||||||||||||||||
Defined in header <algorithm> | ||
Call signature | ||
template<std::input_iterator I,std::sentinel_for<I> S, std::weakly_incrementable O,class Gen> | (1) | (since C++20) |
template<ranges::input_range R,std::weakly_incrementable O,class Gen> requires(ranges::forward_range<R>||std::random_access_iterator<O>)&& | (2) | (since C++20) |
[first, last) (without replacement) such that each possiblesample has equal probability of appearance, and writes those selected elements into the range beginning atout.I modelsstd::forward_iterator.[first, last).The function-like entities described on this page arealgorithm function objects (informally known asniebloids), that is:
Contents |
| first, last | - | the iterator-sentinel pair defining therange of elements from which to make the sampling (the population) |
| r | - | the range from which to make the sampling (the population) |
| out | - | the output iterator where the samples are written |
| n | - | number of samples to take |
| gen | - | the random number generator used as the source of randomness |
An iterator equal toout+ M, that is the end of the resulting sample range.
Linear: 𝓞(last- first).
This function may implementselection sampling orreservoir sampling.
struct sample_fn{template<std::input_iterator I,std::sentinel_for<I> S,std::weakly_incrementable O,class Gen> requires(std::forward_iterator<I> orstd::random_access_iterator<O>)&&std::indirectly_copyable<I, O>&&std::uniform_random_bit_generator<std::remove_reference_t<Gen>> O operator()(I first, S last, O out,std::iter_difference_t<I> n, Gen&& gen)const{using diff_t=std::iter_difference_t<I>;using distrib_t=std::uniform_int_distribution<diff_t>;using param_t=typename distrib_t::param_type; distrib_t D{}; ifconstexpr(std::forward_iterator<I>){// this branch preserves "stability" of the sample elementsauto rest{ranges::distance(first, last)};for(n=ranges::min(n, rest); n!=0;++first)if(D(gen, param_t(0,--rest))< n){*out++=*first;--n;}return out;}else{// O is a random_access_iterator diff_t sample_size{};// copy [first, first + M) elements to "random access" outputfor(; first!= last&& sample_size!= n;++first) out[sample_size++]=*first;// overwrite some of the copied elements with randomly selected onesfor(auto pop_size{sample_size}; first!= last;++first,++pop_size){constauto i{D(gen, param_t{0, pop_size})};if(i< n) out[i]=*first;}return out+ sample_size;}} template<ranges::input_range R,std::weakly_incrementable O,class Gen> requires(ranges::forward_range<R> orstd::random_access_iterator<O>)&&std::indirectly_copyable<ranges::iterator_t<R>, O>&&std::uniform_random_bit_generator<std::remove_reference_t<Gen>> O operator()(R&& r, O out,ranges::range_difference_t<R> n, Gen&& gen)const{return(*this)(ranges::begin(r),ranges::end(r), std::move(out), n,std::forward<Gen>(gen));}}; inlineconstexpr sample_fn sample{}; |
#include <algorithm>#include <iomanip>#include <iostream>#include <iterator>#include <random>#include <vector> void print(autoconst& rem,autoconst& v){std::cout<< rem<<" = ["<<std::size(v)<<"] { ";for(autoconst& e: v)std::cout<< e<<' ';std::cout<<"}\n";} int main(){constauto in={1,2,3,4,5,6}; print("in", in); std::vector<int> out;constint max= in.size()+2;auto gen=std::mt19937{std::random_device{}()}; for(int n{}; n!= max;++n){ out.clear(); std::ranges::sample(in,std::back_inserter(out), n, gen);std::cout<<"n = "<< n; print(", out", out);}}
Possible output:
in = [6] { 1 2 3 4 5 6 }n = 0, out = [0] { }n = 1, out = [1] { 5 }n = 2, out = [2] { 4 5 }n = 3, out = [3] { 2 3 5 }n = 4, out = [4] { 2 4 5 6 }n = 5, out = [5] { 1 2 3 5 6 }n = 6, out = [6] { 1 2 3 4 5 6 }n = 7, out = [6] { 1 2 3 4 5 6 }(C++20) | randomly re-orders elements in a range (algorithm function object)[edit] |
(C++17) | selects N random elements from a sequence (function template)[edit] |
