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) neu an, sodass jede mögliche Permutation dieser Elemente die gleiche Wahrscheinlichkeit des Auftretens hat.

Falls 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) 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 Standardbibliotheksimplementierungen unterschiedliche Ergebnisse erhalten.

Der Grund für die Entfernung von std::random_shuffle in C++17 ist, dass die iterator-only-Version normalerweise von std::rand abhängt, das jetzt ebenfalls zur Abschaffung 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 iterator-only std::random_shuffle-Version normalerweise von einem globalen Zustand ab. Der std::shuffle's-shuffle-Algorithmus ist der bevorzugte Ersatz, da er ein 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

Fehlermeldungen (Defect Reports)

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

Siehe auch