std:: random_shuffle, std:: shuffle

Réorganise les éléments dans la plage donnée [ first , last ) de telle 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 également 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) n'est pas réellement correct, car le nombre généré n'est
        // pas uniformément distribué pour la plupart des valeurs de i. Le code correct serait
        // une variation de l'implémentation de std::uniform_int_distribution de C++11.
    }
}

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 la même RandomFunc ou URBG (Uniform Random Number Generator) vous pourriez 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 ne prenant que des itérateurs dépend généralement de std::rand , qui est maintenant également envisagée pour la dépréciation. ( std::rand devrait être remplacée par les classes de l'en-tête <random> , car std::rand est considérée comme nuisible .) De plus, la version de std::random_shuffle ne prenant que des itérateurs dépend généralement d'un état global. L'algorithme de mélange de std::shuffle est le remplacement privilégié, car il utilise un URBG comme troisiè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.

1. ↑ La surcharge (3) présente le même défaut, mais cette partie de la résolution n'est pas applicable à C++98.

Voir aussi