From cppreference.com
Defined in header
Call signature
template<std::input_iteratorI,std::sentinel_for<I>S,std::weakly_incrementableO,classGen>requires(std::forward_iterator<I>||std::random_access_iterator<O>)&&std::indirectly_copyable<I,O>&&std::uniform_random_bit_generator<std::remove_reference_t<Gen>>Osample(Ifirst,Slast,Od_first,std::iter_difference_t<I>count,Gen&&gen); (1) (since C++20)template<ranges::input_rangeR,std::weakly_incrementableO,classGen>requires(ranges::forward_range<R>||std::random_access_iterator<O>)&&std::indirectly_copyable<ranges::iterator_t<R>,O>&&std::uniform_random_bit_generator<std::remove_reference_t<Gen>>Osample(R&&r,Od_first,ranges::range_difference_t<R>count,Gen&&gen); (2) (since C++20)Randomly copies count different elements from the source range [first, last) or r to the destination range beginning at d_first, such that each possible combination has equal probability of appearance. The source of randomness is gen.
If count is greater than ranges::distance(first,last) or ranges::distance(r), all elements in the source range will be copied.
The algorithm is stable (preserves the relative order of the selected elements) only if I or ranges::iterator_t<R> models
.
If out is in the source range, the behavior is undefined.
The function-like entities described on this page are
(informally known as niebloids), that is:
Explicit template argument lists cannot be specified when calling any of them.
None of them are visible to
.
When any of them are found by
as the name to the left of the function-call operator,
is inhibited.
Parameters
first, last - the iterator-sentinel pair defining the source
r - the source range d_first - the beginning of the destination range count - the sample size gen - the random number generator Return value
The past-the-end iterator of the destination range.
Complexity
1) Linear in ranges::distance(first,last).
2) Linear in ranges::distance(r).
Notes
This function may implement selection sampling or
.
Possible implementation
structsample_fn{template<std::input_iteratorI,std::sentinel_for<I>S,std::weakly_incrementableO,classGen>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>>Ooperator()(Ifirst,Slast,Od_first,std::iter_difference_t<I>count,Gen&&gen)const{usingdiff_t=std::iter_difference_t<I>;usingdistrib_t=std::uniform_int_distribution<diff_t>;usingparam_t=typenamedistrib_t::param_type;distrib_tD{};ifconstexpr(std::forward_iterator<I>){// this branch preserves stability of the sample elementsautorest{ranges::distance(first,last)};for(count=ranges::min(count,rest);count!=0;++first)if(D(gen,param_t(0,--rest))<count){*out++=*first;--count;}returnout;}else{// O is a random_access_iteratordiff_tsample_size{};// copy [first, first + M) elements to random access outputfor(;first!=last&&sample_size!=count;++first)out[sample_size++]=*first;// overwrite some of the copied elements with randomly selected onesfor(autopop_size{sample_size};first!=last;++first,++pop_size){constautoi{D(gen,param_t{0,pop_size})};if(i<count)out[i]=*first;}returnout+sample_size;}}template<ranges::input_rangeR>autoget_end(R&&r){returnranges::end(r);}template<ranges::forward_rangeR>autoget_end(R&&r){returnranges::next(ranges::begin(r),ranges::end(r));}template<ranges::input_rangeR,std::weakly_incrementableO,classGen>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>>Ooperator()(R&&r,Od_first,ranges::range_difference_t<R>count,Gen&&gen)const{return(*this)(ranges::begin(r),get_end(r),std::move(out),count,std::forward<Gen>(gen));}};inlineconstexprsample_fnsample{};Example
Run this code
#include<algorithm>#include<iomanip>#include<iostream>#include<iterator>#include<random>#include<vector>voidprint(constauto&rem,constauto&v){std::cout<<rem<<" = ["<<std::size(v)<<"] { ";forconstauto&e:v)std::cout<<e<<' ';std::cout<<"}\n";}intmain(){constautoin={1,2,3,4,5,6};print("in",in);std::vector<int>out;constintmax=in.size()+2;autogen=std::mt19937{std::random_device{}()};for(intn{};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 } See also
(C++17)
selects N random elements from a sequence
(function template)
(C++20)
randomly re-orders elements in a range
(algorithm function object)