std::random_shuffle, std::shuffle
| Definiert in Header <algorithm> |
||
template< class RandomIt > void random_shuffle( RandomIt first, RandomIt last ); |
(1) | (deprecated in C++14) (removed in C++17) |
| (2) | ||
template< class RandomIt, class RandomFunc > void random_shuffle( RandomIt first, RandomIt last, RandomFunc& r ); |
(bis C++11) | |
| template< class RandomIt, class RandomFunc > void random_shuffle( RandomIt first, RandomIt last, RandomFunc&& r ); |
(seit C++11) (deprecated in C++14) (removed in C++17) |
|
template< class RandomIt, class URBG > void shuffle( RandomIt first, RandomIt last, URBG&& g ); |
(3) | (seit C++11) |
Ordnet die Elemente im gegebenen Bereich [first, last) so um, dass jede mögliche Permutation dieser Elemente mit gleicher Wahrscheinlichkeit erscheint.
- Der Rückgabetyp von r ist nicht konvertierbar nach std::iterator_traits<RandomIt>::difference_type.
- Bei einem positiven Wert n vom Typ std::iterator_traits<RandomIt>::difference_type ist das Ergebnis von r(n) kein zufällig gewählter Wert im Intervall
[0,n).
T als std::remove_reference_t<URBG> ist das Verhalten undefiniert, wenn eine der folgenden Bedingungen erfüllt ist.-
Tist kein UniformRandomBitGenerator.
|
(bis C++20) |
Wenn der Typ von *first nicht Swappable ist(bis C++11)RandomIt ist kein ValueSwappable(seit C++11) ist das Verhalten undefiniert.
Inhalt |
[edit] Parameter
| first, last | - | das Iteratorenpaar, das den Bereich der zufällig zu mischenden Elemente definiert |
| r | - | Funktions-Objekt, das einen zufällig ausgewählten Wert zurückgibt |
| g | - | Generator-Objekt, das einen zufällig ausgewählten Wert zurückgibt |
| Typanforderungen | ||
-RandomIt muss die Anforderungen an einen LegacyRandomAccessIterator erfüllen. | ||
[edit] Komplexität
Genau std::distance(first, last) - 1 Swaps.
[edit] Mögliche Implementierung
Siehe auch die Implementierungen in libstdc++ und libc++.
| random_shuffle (1) |
|---|
template<class RandomIt> void random_shuffle(RandomIt first, RandomIt last) { typedef typename std::iterator_traits<RandomIt>::difference_type diff_t; for (diff_t i = last - first - 1; i > 0; --i) { using std::swap; swap(first[i], first[std::rand() % (i + 1)]); // rand() % (i + 1) is not actually correct, because the generated number is // not uniformly distributed for most values of i. The correct code would be // a variation of the C++11 std::uniform_int_distribution implementation. } } |
| random_shuffle (2) |
template<class RandomIt, class RandomFunc> void random_shuffle(RandomIt first, RandomIt last, RandomFunc&& r) { typedef typename std::iterator_traits<RandomIt>::difference_type diff_t; for (diff_t i = last - first - 1; i > 0; --i) { using std::swap; swap(first[i], first[r(i + 1)]); } } |
| shuffle (3) |
template<class RandomIt, class URBG> void shuffle(RandomIt first, RandomIt last, URBG&& g) { typedef typename std::iterator_traits<RandomIt>::difference_type diff_t; typedef std::uniform_int_distribution<diff_t> distr_t; typedef typename distr_t::param_type param_t; distr_t D; for (diff_t i = last - first - 1; i > 0; --i) { using std::swap; swap(first[i], first[D(g, param_t(0, i))]); } } |
[edit] Hinweise
Beachten Sie, dass die Implementierung nicht vom Standard diktiert wird. Selbst wenn Sie exakt denselben RandomFunc oder URBG (Uniform Random Number Generator) verwenden, können Sie bei unterschiedlichen Standardbibliotheksimplementierungen unterschiedliche Ergebnisse erzielen.
Der Grund für die Entfernung von std::random_shuffle in C++17 ist, dass die reine Iterator-Version normalerweise von std::rand abhängt, was auch für die Deprezierung diskutiert wird. (std::rand sollte durch die Klassen des <random>-Headers ersetzt werden, da std::rand als schädlich angesehen wird.) Zusätzlich hängt die reine Iterator-Version von std::random_shuffle normalerweise von einem globalen Zustand ab. Der std::shuffle-Algorithmus ist der bevorzugte Ersatz, da er einen URBG als dritten Parameter verwendet.
[edit] Beispiel
Mischt zufällig die Sequenz [1, 10] von ganzen Zahlen
#include <algorithm> #include <iostream> #include <iterator> #include <random> #include <vector> int main() { std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; std::random_device rd; std::mt19937 g(rd()); std::shuffle(v.begin(), v.end(), g); std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << '\n'; }
Mögliche Ausgabe
8 6 10 4 2 3 7 1 9 5
[edit] Fehlerberichte
Die folgenden Verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.
| DR | angewendet auf | Verhalten wie veröffentlicht | Korrigiertes Verhalten |
|---|---|---|---|
| LWG 395 | C++98 | die Quelle der Zufälligkeit von Überladung (1) war nicht spezifiziert, und std::rand konnte aufgrund der C-Bibliotheksanforderung nicht die Quelle sein |
es ist implementierungsabhängig, und die Verwendung von std::rand ist erlaubt |
| LWG 552 (N2423) |
C++98 | r musste nicht die Quelle der Zufälligkeit von Überladung (2) sein[1] |
Gefordert |
- ↑ Überladung (3) hat denselben Fehler, aber dieser Teil der Auflösung ist für C++98 nicht anwendbar.
[edit] Siehe auch
| erzeugt die nächstgrößere lexikographische Permutation eines Bereichs von Elementen (Funktionsvorlage) | |
| erzeugt die nächstkleinere lexikographische Permutation eines Bereichs von Elementen (Funktionsvorlage) | |
| (C++20) |
Ordnet Elemente in einem Bereich zufällig neu an (Algorithmus-Funktionsobjekt) |
