std::ranges::sample
Von de.cppreference.net
| Definiert in Header <algorithm>
|
||
| Aufrufsignatur |
||
template< std::input_iterator I, std::sentinel_for<I> S,
std::weakly_incrementable O, class Gen >
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>>
O sample( I first, S last, O out, std::iter_difference_t<I> n, Gen&& gen );
|
(1) | (seit C++20) |
template< ranges::input_range R, std::weakly_incrementable O, class Gen >
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>>
O sample( R&& r, O out, ranges::range_difference_t<R> n, Gen&& gen );
|
(2) | (seit C++20) |
1) Wählt
M = min(n, last - first) Elemente aus der Sequenz [first, last) (ohne Zurücklegen) aus, sodass jede mögliche Stichprobe die gleiche Wahrscheinlichkeit des Auftretens hat, und schreibt diese ausgewählten Elemente in den Bereich, der bei out beginnt. Der Algorithmus ist stabil (erhält die relative Reihenfolge der ausgewählten Elemente) nur, wenn
I std::forward_iterator modelliert. Das Verhalten ist undefiniert, wenn
out in [first, last) ist.2) Dasselbe wie (1), verwendet aber
r als Quellbereich, als ob ranges::begin(r) als first und ranges::end(r) als last verwendet würden.Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmus-Funktionsobjekte (informell als Niebloids bekannt), das heißt:
- Explizite Vorlagenargumentlisten können beim Aufruf einer von ihnen nicht angegeben werden.
- Keine von ihnen ist für argumentabhängige Suche sichtbar.
- Wenn eine von ihnen durch normale unqualifizierte Suche als Name links vom Funktionsaufrufoperator gefunden wird, wird argumentabhängige Suche unterdrückt.
Parameter
| first, last | - | das Iterator-Sentinel-Paar, das den Bereich der Elemente definiert, aus denen die Stichprobe erstellt wird ( die Grundgesamtheit ) |
| r | - | der Bereich, aus dem die Stichprobe erstellt wird ( die Grundgesamtheit ) |
| out | - | der Ausgabeiterator, in den die Stichproben geschrieben werden |
| n | - | Anzahl der zu entnehmenden Stichproben |
| gen | - | der Zufallszahlengenerator, der als Quelle für Zufälligkeit dient |
Rückgabewert
Ein Iterator gleich out + M , also das Ende des resultierenden Stichprobenbereichs.
Komplexität
Linear : 𝓞 ( last - first ) .
Hinweise
Diese Funktion kann Auswahlstichproben oder Reservoirstichproben implementieren.
Mögliche Implementierung
struct sample_fn { template<std::input_iterator I, std::sentinel_for<I> S, std::weakly_incrementable O, class Gen> requires (std::forward_iterator<I> or std::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{}; if constexpr (std::forward_iterator<I>) { // Dieser Zweig erhält die "Stabilität" der Stichprobenelemente auto 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 ist ein random_access_iterator diff_t sample_size{}; // Kopiere [first, first + M) Elemente in die "random access" Ausgabe for (; first != last && sample_size != n; ++first) out[sample_size++] = *first; // Überschreibe einige der kopierten Elemente mit zufällig ausgewählten for (auto pop_size{sample_size}; first != last; ++first, ++pop_size) { const auto 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> or std::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)); } }; inline constexpr sample_fn sample {}; |
Beispiel
Diesen Code ausführen
#include <algorithm> #include <iomanip> #include <iostream> #include <iterator> #include <random> #include <vector> void print(auto const& rem, auto const& v) { std::cout << rem << " = [" << std::size(v) << "] { "; for (auto const& e : v) std::cout << e << ' '; std::cout << "}\n"; } int main() { const auto in = {1, 2, 3, 4, 5, 6}; print("in", in); std::vector<int> out; const int 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); } }
Mögliche Ausgabe:
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 }
Siehe auch
|
(C++20)
|
ordnet Elemente in einem Bereich zufällig neu an
(Algorithmus-Funktionsobjekt) |
|
(C++17)
|
wählt N zufällige Elemente aus einer Sequenz aus
(Funktionstemplate) |