Namespaces
Variants
Views
Actions

Difference between revisions of "cpp/algorithm/sample"

From cppreference.com
< cpp‎ | algorithm
m (Output will maintain order)
m (fmt.)
Line 1: Line 1:
 
{{cpp/title|sample}}
 
{{cpp/title|sample}}
 
{{cpp/algorithm/navbar}}
 
{{cpp/algorithm/navbar}}
−
{{dcl begin}}
+
{{ddcl|header=algorithm|since=c++17|
−
{{dcl header|algorithm}}
+
−
{{dcl|since=c++17|
+
 
template< class PopulationIterator, class SampleIterator,
 
template< class PopulationIterator, class SampleIterator,
 
           class Distance, class URBG >
 
           class Distance, class URBG >
Line 10: Line 8:
 
                       URBG&& g );
 
                       URBG&& g );
 
}}
 
}}
−
{{dcl end}}
 
  
−
Selects {{tt|n}} elements from the sequence {{range|first|last}} (without replacement) such that each possible sample has equal probability of appearance, and writes those selected elements into the output iterator {{c|out}}. Random numbers are generated using the random number generator {{c|g}}.
+
Selects {{c|n}} elements from the sequence {{range|first|last}} (without replacement) such that each possible sample has equal probability of appearance, and writes those selected elements into the output iterator {{c|out}}. Random numbers are generated using the random number generator {{c|g}}.
  
−
If {{tt|n}} is greater than the number of elements in the sequence, selects {{c|last - first}} elements.
+
If {{c|n}} is greater than the number of elements in the sequence, selects {{c|last - first}} elements.
  
 
The algorithm is stable (preserves the relative order of the selected elements) only if {{tt|PopulationIterator}} meets the requirements of {{named req|ForwardIterator}}
 
The algorithm is stable (preserves the relative order of the selected elements) only if {{tt|PopulationIterator}} meets the requirements of {{named req|ForwardIterator}}
Line 42: Line 39:
  
 
===Notes===
 
===Notes===
−
This function may implement selection sampling or reservoir sampling.
+
This function may implement selection sampling or {{enwiki|reservoir sampling}}.
  
−
{{feature test macro|__cpp_lib_sample|[[#Top|{{tt|std::sample}}]]|value=201603L|std=C++17}}
+
{{feature test macro|__cpp_lib_sample|{{tt|std::sample}}|value=201603L|std=C++17}}
  
 
===Possible implementation===
 
===Possible implementation===

Revision as of 16:00, 20 July 2023

 
C++
 
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy, ranges::sort, ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
(C++11)                (C++11)(C++11)

Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17)(C++11)
(C++20)(C++20)
Sampling operations
sample
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
Minimum/maximum operations
(C++11)
(C++17)
Lexicographical comparison operations
(C++20)
Permutation operations
C library
Numeric operations
Operations on uninitialized memory
 
Defined in header <algorithm>
template< class PopulationIterator, class SampleIterator,

          class Distance, class URBG >
SampleIterator sample( PopulationIterator first, PopulationIterator last,
                       SampleIterator out, Distance n,

                       URBG&& g );
 (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

The behavior is undefined if out is in [first, last).

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
n - number of samples to make
g - the random number generator used as the source of randomness
Type requirements
-
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.

Feature-test macro Value Std Feature
__cpp_lib_sample 201603L (C++17) std::sample

Possible implementation

See the implementations in libstdc++, libc++ and MSVC STL.

Example

Run this code
#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
#include <string>
 
int main()
{
    std::string in {"ABCDEFGHIJK"}, out;
    std::sample(in.begin(), in.end(), std::back_inserter(out), 4,
                std::mt19937 {std::random_device{}()});
    std::cout << "Four random letters out of " << in << " : " << out << '\n';
}

Possible output: 

Four random letters out of ABCDEFGHIJK: EFGK

See also

(until C++17)(C++11)
 randomly re-orders elements in a range
(function template) [edit]
(C++20)
 selects N random elements from a sequence
(niebloid)[edit]
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/sample&oldid=155272"