std:: random_shuffle, std:: shuffle

Ordnet die Elemente im angegebenen Bereich [ first , last ) so um, dass jede mögliche Permutation dieser Elemente die gleiche Wahrscheinlichkeit des Auftretens hat.

Wenn der Typ von * first nicht Swappable (bis C++11) RandomIt nicht ValueSwappable (seit C++11) ist, ist das Verhalten undefiniert.

Parameter

Komplexität

Genau std:: distance ( first, last ) - 1 Vertauschungen.

Mögliche Implementierung

Siehe auch die Implementierungen in libstdc++ und libc++ .

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) ist nicht korrekt, da die generierte Zahl
        // für die meisten Werte von i nicht gleichmäßig verteilt ist. Der korrekte Code wäre
        // eine Variation der C++11 std::uniform_int_distribution Implementierung.
    }
}

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)]);
    }
}

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))]);
    }
}

Hinweise

Beachten Sie, dass die Implementierung nicht durch den Standard vorgegeben ist, daher können Sie selbst bei Verwendung exakt derselben RandomFunc oder URBG (Uniform Random Number Generator) mit verschiedenen Standardbibliothek-Implementierungen unterschiedliche Ergebnisse erhalten.

Der Grund für die Entfernung von std::random_shuffle in C++17 ist, dass die Iterator-Only-Version üblicherweise von std::rand abhängt, welches nun ebenfalls zur Abschaffung diskutiert wird. ( std::rand sollte durch die Klassen des <random> -Headers ersetzt werden, da std::rand als schädlich betrachtet wird .) Zusätzlich hängt die Iterator-Only-Version von std::random_shuffle üblicherweise von einem globalen Zustand ab. Der Shuffle-Algorithmus von std::shuffle ist der bevorzugte Ersatz, da er einen URBG als dritten Parameter verwendet.

Beispiel

#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';
}

8 6 10 4 2 3 7 1 9 5

Fehlerberichte

Die folgenden verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.

1. ↑ Überladung (3) hat den gleichen Defekt, aber dieser Teil der Lösung ist nicht auf C++98 anwendbar.

Siehe auch