Namespaces
Variants
Views
Actions

Difference between revisions of "cpp/algorithm/sample"

From cppreference.com
< cpp‎ | algorithm
m (→‎Possible implementation)
(Wording update.)
 
(9 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 
{{cpp/title|sample}}
 
{{cpp/title|sample}}
 
{{cpp/algorithm/navbar}}
 
{{cpp/algorithm/navbar}}
−
 
+
{{ddcl|header=algorithm|since=c++17|
−
{{dcl begin}}
+
template< class PopulationIt, class SampleIt, class Distance, class URBG >
−
{{dcl header | algorithm }}
+
SampleIterator sample( PopulationIt first, PopulationIt last,
−
{{dcl |since=c++17 |
+
                       SampleIt out, Distance n, URBG&& g );
−
template< class PopulationIterator, class SampleIterator,
+
−
          class Distance, class URBG >
+
−
SampleIterator sample( PopulationIterator first, PopulationIterator last,
+
−
                       SampleIterator out, Distance n,  
+
−
                      URBG&& g);
+
 
}}
 
}}
−
{{dcl end}}
 
  
−
Selects {{tt|n}} elements from the sequence {{math|[first; last)}} (without replacement) such that each possible sample has equal probability of appearance, and writes those selected elements into the output iterator {{tt|out}}. Random numbers are generated using the random number generator {{tt|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 all elements in the sequence.
  
−
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|PopulationIt}} meets the requirements of {{named req|ForwardIterator}}.
  
−
The behavior is undefined if {{tt|out}} is in {{math|[first; last)}}.
+
If {{rev inl|until=c++20|the value type of {{c|first}}}}{{rev inl|since=c++20|{{c|*first}}}} is not [[cpp/iterator#Types and writability|writable]] to {{c|out}}, the program is ill-formed.
 +
 
 +
If any of the following conditions is satisfied, the behavior is undefined:
 +
* {{c|out}} is in {{range|first|last}}.
 +
* {{tt|PopulationIt}} does not meet the requirements of {{named req|InputIterator}}.
 +
* {{tt|SampleIt}} does not meet the requirements of {{named req|OutputIterator}}.
 +
* All following conditions are satisfied:
 +
{{rev begin}}
 +
{{rev|until=c++23|
 +
:* {{tt|PopulationIt}} does not meet the requirements of {{named req|ForwardIterator}}.
 +
}}
 +
{{rev|since=c++23|
 +
:* {{tt|PopulationIt}} does not model {{lconcept|forward_iterator}}.
 +
}}
 +
{{rev end}}
 +
:* {{tt|SampleIt}} does not meet the requirements of {{named req|RandomAccessIterator}}.
 +
* Given the type {{tt|T}} as {{c/core|std::remove_reference_t<URBG>}}, any of the following conditions is satisfied:
 +
:* {{tt|T}} does not meet the requirements of {{named req|UniformRandomBitGenerator}}.
 +
{{rrev|until=c++20|
 +
:* The return type of {{tt|T}} is not convertible to {{tt|Distance}}.
 +
}}
  
 
===Parameters===
 
===Parameters===
 
{{par begin}}
 
{{par begin}}
−
{{par | first, last | pair of iterators forming the range from which to make the sampling (the population) }}
+
{{par|first, last|pair of iterators forming the range from which to make the sampling (the population)}}
−
{{par | out | the output iterator where the samples are written}}
+
{{par|out|the output iterator where the samples are written}}
−
{{par | n | number of samples to make}}
+
{{par|n|number of samples to make}}
−
{{par | g | the random number generator used as the source of randomness }}
+
{{par|g|the random number generator used as the source of randomness}}
 
{{par hreq}}
 
{{par hreq}}
−
{{par req named | PopulationIterator | InputIterator}}
+
{{par req|{{tt|Distance}} must be an integer type.}}
−
{{par req named | SampleIterator | OutputIterator}}
+
−
{{par req | {{tt|SampleIterator}} must also meet the requirements of {{named req|RandomAccessIterator}} if {{tt|PopulationIterator}} doesn't meet {{named req|ForwardIterator}} }}
+
−
{{par req | {{tt|PopulationIterator}}'s value type must be writeable to {{tt|out}}}}
+
−
{{par req | {{tt|Distance}} must be an integer type}}
+
−
{{par req | {{c|std::remove_reference_t<URBG>}} must meet the requirements of {{named req|UniformRandomBitGenerator}} and its return type must be convertible to {{tt|Distance}}}}
+
 
{{par end}}
 
{{par end}}
  
 
===Return value===
 
===Return value===
−
Returns a copy of {{tt|out}} after the last sample that was output, that is, end of the sample range.
+
Returns a copy of {{c|out}} after the last sample that was output, that is, end of the sample range.
  
 
===Complexity===
 
===Complexity===
−
Linear in {{c|std::distance(first,last)}}.
+
Linear in {{c|std::distance(first, last)}}.
−
 
+
−
===Notes===
+
−
This function may implement selection sampling or reservoir sampling.
+
  
 
===Possible implementation===
 
===Possible implementation===
 
See the implementations in [https://github.com/gcc-mirror/gcc/blob/14d8a5ae472ca5743016f37da2dd4770d83dea21/libstdc%2B%2B-v3/include/bits/stl_algo.h#L5743-L5869 libstdc++], [https://github.com/llvm/llvm-project/blob/f221d905b131158cbe3cbc4320d1ecd1376c3f22/libcxx/include/__algorithm/sample.h libc++] and [https://github.com/microsoft/STL/blob/472161105d596192194d4715ccad307c6c163b4a/stl/inc/algorithm#L4518-L4600 MSVC STL].
 
See the implementations in [https://github.com/gcc-mirror/gcc/blob/14d8a5ae472ca5743016f37da2dd4770d83dea21/libstdc%2B%2B-v3/include/bits/stl_algo.h#L5743-L5869 libstdc++], [https://github.com/llvm/llvm-project/blob/f221d905b131158cbe3cbc4320d1ecd1376c3f22/libcxx/include/__algorithm/sample.h libc++] and [https://github.com/microsoft/STL/blob/472161105d596192194d4715ccad307c6c163b4a/stl/inc/algorithm#L4518-L4600 MSVC STL].
 +
 +
===Notes===
 +
This function may implement selection sampling or {{enwiki|reservoir sampling}}.
 +
 +
{{feature test macro|__cpp_lib_sample|{{tt|std::sample}}|value=201603L|std=C++17}}
  
 
===Example===
 
===Example===
 
{{example
 
{{example
−
|
+
|
−
|code=
+
|code=
 +
#include <algorithm>
 
#include <iostream>
 
#include <iostream>
 +
#include <iterator>
 
#include <random>
 
#include <random>
 
#include <string>
 
#include <string>
−
#include <iterator>
+
 
−
#include <algorithm>
+
−
+
 
int main()
 
int main()
 
{
 
{
−
     std::string in = "hgfedcba", out;
+
     std::string in {"ABCDEFGHIJK"}, out;
−
     std::sample(in.begin(), in.end(), std::back_inserter(out),
+
     std::sample(in.begin(), in.end(), std::back_inserter(out), 4,
−
                 5, std::mt19937{std::random_device{}()});
+
                 std::mt19937 {std::random_device{}()});
−
     std::cout << "five random letters out of " << in << " : " << out << '\n';
+
     std::cout << "Four random letters out of " << in << " : " << out << '\n';
 
}
 
}
 
|p=true
 
|p=true
−
|output=
+
|output=
−
five random letters out of hgfedcba: gfcba
+
Four random letters out of ABCDEFGHIJK: EFGK
 
}}
 
}}
  
 
===See also===
 
===See also===
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc inc | cpp/algorithm/dsc random_shuffle}}
+
{{dsc inc|cpp/algorithm/dsc random_shuffle}}
−
{{dsc inc | cpp/algorithm/ranges/dsc sample}}
+
{{dsc inc|cpp/algorithm/ranges/dsc sample}}
 
{{dsc end}}
 
{{dsc end}}
  
 
{{langlinks|es|ja|ru|zh}}
 
{{langlinks|es|ja|ru|zh}}

Latest revision as of 01:10, 28 March 2024

 
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 PopulationIt, class SampleIt, class Distance, class URBG >

SampleIterator sample( PopulationIt first, PopulationIt last,

                       SampleIt 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 all elements in the sequence.

The algorithm is stable (preserves the relative order of the selected elements) only if PopulationIt meets the requirements of LegacyForwardIterator.

If the value type of first(until C++20)*first(since C++20) is not writable to out, the program is ill-formed.

If any of the following conditions is satisfied, the behavior is undefined:

  • out is in [first, last).
  • PopulationIt does not meet the requirements of LegacyInputIterator.
  • SampleIt does not meet the requirements of LegacyOutputIterator.
  • All following conditions are satisfied:
(until C++23)
 (since C++23)
  • The return type of T is not convertible to Distance.
(until C++20)

Contents

[edit] 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
-
Distance must be an integer type.

[edit] Return value

Returns a copy of out after the last sample that was output, that is, end of the sample range.

[edit] Complexity

Linear in std::distance(first, last).

[edit] Possible implementation

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

[edit] Notes

This function may implement selection sampling or reservoir sampling.

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

[edit] 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

[edit] 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=170521"