std::random_shuffle, std::shuffle

template< class RandomIt >
void random_shuffle( RandomIt first, RandomIt last );

template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc& r );

template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc&& r );

template< class RandomIt, class URBG >
void shuffle( RandomIt first, RandomIt last, URBG&& g );

Ordnet die Elemente im gegebenen Bereich [first, last) so um, dass jede mögliche Permutation dieser Elemente mit gleicher Wahrscheinlichkeit auftritt.

Wenn der Typ von *first nicht Swappable(bis C++11)RandomIt ist nicht ValueSwappable(seit C++11), 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) 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.
    }
}

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

Anmerkungen

Beachten Sie, dass die Implementierung nicht durch den Standard vorgeschrieben ist. Selbst wenn Sie genau denselben RandomFunc oder URBG (Uniform Random Number Generator) verwenden, können Sie mit verschiedenen Implementierungen der Standardbibliothek unterschiedliche Ergebnisse erhalten.

Der Grund für die Entfernung von std::random_shuffle in C++17 ist, dass die nur-Iterator-Version normalerweise von std::rand abhängt, das jetzt ebenfalls zur Veraltung diskutiert wird. (std::rand sollte durch die Klassen des <random>-Headers ersetzt werden, da std::rand als schädlich angesehen wird.) Außerdem hängt die nur-Iterator-std::random_shuffle-Version normalerweise von einem globalen Zustand ab. Der Mischalgorithmus 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.

Siehe auch