std:: random_shuffle, std:: shuffle

Переупорядочивает элементы в заданном диапазоне [ first , last ) таким образом, что каждая возможная перестановка этих элементов имеет равную вероятность появления.

Если тип * first не является Swappable (до C++11) RandomIt не является ValueSwappable (начиная с C++11) , поведение не определено.

Параметры

Сложность

Ровно std:: distance ( first, last ) - 1 обменов.

Возможная реализация

Смотрите также реализации в libstdc++ и 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))]);
    }
}

Примечания

Обратите внимание, что реализация не регламентирована стандартом, поэтому даже если вы используете точно такую же RandomFunc или URBG (Uniform Random Number Generator), вы можете получить разные результаты в разных реализациях стандартной библиотеки.

Причина удаления std::random_shuffle в C++17 заключается в том, что версия только с итераторами обычно зависит от std::rand , которая теперь также рассматривается для устаревания. ( std::rand следует заменить классами из заголовка <random> , поскольку std::rand считается вредной .) Кроме того, версия std::random_shuffle только с итераторами обычно зависит от глобального состояния. Алгоритм перемешивания std::shuffle является предпочтительной заменой, поскольку он использует URBG в качестве своего третьего параметра.

Пример

#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

Отчёты о дефектах

Следующие отчеты об изменениях поведения, влияющие на дефекты, были применены ретроактивно к ранее опубликованным стандартам C++.

1. ↑ Перегрузка (3) имеет тот же недостаток, но эта часть решения не применима к C++98.

Смотрите также