std::random_shuffle, std::shuffle
来自 zh.cppreference.net
（重定向自 cpp/algorithm/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) 中的元素，使得这些元素的每个可能排列具有相等的出现概率。
1) 随机性的来源由实现定义，但通常使用函数 std::rand。
2) 随机性的来源是函数对象
r。 如果满足以下任一条件，则行为未定义：
- 的返回类型
r不可转换为std::iterator_traits<RandomIt>::difference_type。 - 给定正数
n类型为std::iterator_traits<RandomIt>::difference_type，结果r(n)不是区间[0,n)中随机选择的值。
3) 随机性的来源是对象
g。 给定类型
T 为 std::remove_reference_t<URBG>，如果满足以下任一条件，则行为未定义：
|
(C++20 前) |
如果 的类型*first 不是 Swappable(C++11 前)RandomIt 不是 ValueSwappable(C++11 起)，则行为未定义。
参数
| first, last | - | 定义随机混洗的元素范围的迭代器对 范围 |
| r | - | 返回随机选择值的函数对象 |
| g | - | 返回随机选择值的生成器对象 |
| 类型要求 | ||
-RandomIt 必须满足 LegacyRandomAccessIterator 的要求。
| ||
复杂度
恰好 std::distance(first, last) - 1 次交换。
可能的实现
| 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（统一随机数生成器），使用不同的标准库实现也可能得到不同的结果。
在 C++17 中移除 std::random_shuffle 的原因在于，仅迭代器版本通常依赖于 std::rand，而后者目前也正在讨论弃用。（std::rand 应替换为 <random> 头文件中的类，因为 std::rand 被认为是有害的。）此外，仅迭代器的 std::random_shuffle 版本通常依赖于全局状态。std::shuffle 的 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) |
随机重排序范围中的元素 (算法函数对象) |