std:: random_shuffle, std:: shuffle

Reordena los elementos en el rango dado [ first , last ) de tal forma que cada posible permutación de esos elementos tenga igual probabilidad de aparición.

Si el tipo de * first no es Swappable (hasta C++11) RandomIt no es ValueSwappable (desde C++11) , el comportamiento es indefinido.

Parámetros

Complejidad

Exactamente std:: distance ( first, last ) - 1 intercambios.

Implementación posible

Consulte también las implementaciones en libstdc++ y 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) no es realmente correcto, porque el número generado no está
        // distribuido uniformemente para la mayoría de los valores de i. El código correcto sería
        // una variación de la implementación 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))]);
    }
}

Notas

Tenga en cuenta que la implementación no está dictada por el estándar, por lo que incluso si utiliza exactamente la misma RandomFunc o URBG (Uniform Random Number Generator) puede obtener resultados diferentes con distintas implementaciones de la biblioteca estándar.

La razón para eliminar std::random_shuffle en C++17 es que la versión que solo utiliza iteradores normalmente depende de std::rand , que ahora también se está considerando para su desaprobación. ( std::rand debería ser reemplazado con las clases de la cabecera <random> , ya que std::rand está considerado perjudicial .) Además, la versión de std::random_shuffle que solo utiliza iteradores normalmente depende de un estado global. El algoritmo de mezcla de std::shuffle es el reemplazo preferido, ya que utiliza un URBG como su tercer parámetro.

Ejemplo

#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

Informes de defectos

Los siguientes informes de defectos que modifican el comportamiento se aplicaron retroactivamente a los estándares de C++ publicados anteriormente.

1. ↑ La sobrecarga (3) tiene el mismo defecto, pero esa parte de la resolución no es aplicable a C++98.

Véase también