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 [first, last) donnée 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 uniforme), vous pouvez obtenir des résultats différents avec des implémentations de bibliothèque standard différentes.

La raison de la suppression de std::random_shuffle en C++17 est que la version uniquement itérateur dépend généralement de std::rand, qui est maintenant également discutée pour la dépréciation. (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 uniquement itérateur std::random_shuffle dépend généralement d'un état global. L'algorithme de mélange 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 suivants modifiant le comportement ont été appliqués rétroactivement aux normes C++ précédemment publiées.

Voir aussi