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

Réordonne les éléments dans la plage donnée [first, last) de sorte que chaque permutation possible de ces éléments ait une probabilité égale d'apparition.

Si le type de *first n'est pas Swappable(jusqu'à C++11)RandomIt n'est pas ValueSwappable(depuis C++11), le comportement est indéfini.

Paramètres

Complexité

Exactement std::distance(first, last) - 1 échanges.

Implémentation possible

Voir aussi les implémentations dans libstdc++ et 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))]);
    }
}

Notes

Notez que l'implémentation n'est pas dictée par la norme, donc même si vous utilisez exactement le même RandomFunc ou URBG (générateur de nombres aléatoires uniformes), vous pouvez obtenir des résultats différents avec différentes implémentations de la bibliothèque standard.

La raison de la suppression de std::random_shuffle en C++17 est que la version avec itérateurs uniquement dépend généralement de std::rand, qui est maintenant également discuté pour obsolescence. (std::rand devrait être remplacé par les classes de l'en-tête <random>, car std::rand est considéré comme nuisible.) De plus, la version avec itérateurs uniquement std::random_shuffle dépend généralement d'un état global. L'algorithme shuffle de std::shuffle est le remplacement préféré, car il utilise un URBG comme 3ème paramètre.

Exemple

#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

Rapports de défauts

Les rapports de défauts modifiant le comportement suivants ont été appliqués rétroactivement aux normes C++ précédemment publiées.

Voir aussi