std::random_shuffle, std::shuffle
| Определено в заголовке <algorithm>
|
||
template< class RandomIt >
void random_shuffle( RandomIt first, RandomIt last );
|
(1) | (устарело в C++14) (удалено в C++17) |
template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc& r );
|
(2) | (до C++11) |
template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc&& r );
|
(начиная с C++11) (устарело в C++14) (удалено в C++17) |
|
template< class RandomIt, class URBG >
void shuffle( RandomIt first, RandomIt last, URBG&& g );
|
(3) | (начиная с C++11) |
Переупорядочивает элементы в заданном диапазоне [first, last) так, что каждая возможная перестановка этих элементов имеет равную вероятность появления.
r.- Тип возвращаемого значения
rне преобразуется вstd::iterator_traits<RandomIt>::difference_type. - Для положительного значения
nтипаstd::iterator_traits<RandomIt>::difference_typeрезультатr(n)не является случайно выбранным значением в интервале[0,n).
g.T будет std::remove_reference_t<URBG>, если выполняется любое из следующих условий, поведение не определено:
Tне является UniformRandomBitGenerator.
|
(до C++20) |
Если тип *first не является Swappable(до C++11)RandomIt не является ValueSwappable(начиная с C++11), поведение не определено.
Параметры
| first, last | - | пара итераторов, определяющих диапазон элементов для случайного перемешивания |
| r | - | объект-функция, возвращающая случайно выбранное значение |
| g | - | объект-генератор, возвращающий случайно выбранное значение |
| Требования к типам | ||
-RandomIt должен соответствовать требованиям LegacyRandomAccessIterator.
| ||
Сложность
Ровно std::distance(first, last) - 1 обменов.
Возможная реализация
Смотрите также реализации в libstdc++ и libc++.
| random_shuffle (1) |
|---|
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.
}
}
|
| random_shuffle (2) |
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)]);
}
}
|
| shuffle (3) |
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 (генератор равномерных случайных чисел), вы можете получить разные результаты с разными реализациями стандартной библиотеки.
Причина удаления std::random_shuffle в C++17 заключается в том, что версия только с итераторами обычно зависит от std::rand, который сейчас также обсуждается на предмет устаревания. (std::rand следует заменить классами из заголовка <random>, так как std::rand считается вредным.) Кроме того, версия std::random_shuffle только с итераторами обычно зависит от глобального состояния. Алгоритм перемешивания std::shuffle's shuffle является предпочтительной заменой, так как использует URBG в качестве третьего параметра.
Пример
Случайное перемешивание последовательности [1, 10] целых чисел:
#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++.
| DR | Применено к | Поведение как опубликованное | Корректное поведение |
|---|---|---|---|
| LWG 395 | C++98 | источник случайности перегрузки (1) не был указан, и std::rand не мог быть источником из-за требований библиотеки C |
он определяется реализацией, и разрешено использование std::rand |
| LWG 552 (N2423) |
C++98 | r не требовался быть источникомслучайности для перегрузки (2)[1] |
требуется |
- ↑ Перегрузка (3) имеет тот же дефект, но эта часть исправления не применима к C++98.
Смотрите также
| генерирует следующую бо́льшую лексикографическую перестановку диапазона элементов (шаблон функции & алгоритм, объект-функция) | |
(C++20) |
|
| генерирует следующую ме́ньшую лексикографическую перестановку диапазона элементов (шаблон функции & алгоритм, объект-функция) | |
(C++20) |
|
(C++20) |
случайно переупорядочивает элементы в диапазоне (алгоритм, объект-функция) |