std::random_shuffle, std::shuffle
来自 cppreference.cn
定义于头文件 <algorithm> |
||
template< class RandomIt > void random_shuffle( RandomIt first, RandomIt last ); |
(1) | (在 C++14 中弃用) (在 C++17 中移除) |
(2) | ||
template< class RandomIt, class RandomFunc > void random_shuffle( RandomIt first, RandomIt last, RandomFunc& r ); |
(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。
- 给定类型为 std::iterator_traits<RandomIt>::difference_type 的正值 n,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 也被讨论是否弃用。(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) 的随机性来源未指定,并且 由于 C 库要求,std::rand 可能不是来源 |
它是实现定义的, 并且允许使用 std::rand |
LWG 552 (N2423) |
C++98 | 未要求 r 成为 重载 (2) 的随机性来源[1] |
已要求 |
- ↑ 重载 (3) 具有相同的缺陷,但该解决方案的该部分不适用于 C++98。
[编辑] 参见
生成一个元素范围的下一个更大的字典序排列 (函数模板) | |
生成一个元素范围的下一个更小的字典序排列 (函数模板) | |
(C++20) |
随机重排一个范围内的元素 (算法函数对象) |