std::random_shuffle, std::shuffle
定义于头文件 <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
。3) 随机数生成器为函数对象
g
。参数
first, last | - | 要随机打乱的元素范围 |
r | - | 函数对象。若以 r(n) 调用,则返回可转换为 std::iterator_traits<RandomIt>::difference_type 的在区间 [0,n) 中随机选取的值
|
g | - | 均匀随机位生成器 (UniformRandomBitGenerator) ,其结果类型可隐式转换为 std::iterator_traits<RandomIt>::difference_type |
类型要求 | ||
-RandomIt 必须满足值可交换 (ValueSwappable) 和 遗留随机访问迭代器 (LegacyRandomAccessIterator) 的要求。
| ||
-std::remove_reference_t<URBG> 必须满足均匀随机位生成器 (UniformRandomBitGenerator) 的要求。
|
返回值
(无)
复杂度
与 first
和 last
间的距离成线性。
注意
标准未钦定实现,故即使你用准确相同的 RandomFunc
或 URBG
,也可能通过不同的标准库实现得到不同结果。
可能的实现
版本一 |
---|
template< class RandomIt > void random_shuffle( RandomIt first, RandomIt last ) { typename std::iterator_traits<RandomIt>::difference_type i, n; n = last - first; for (i = n-1; i > 0; --i) { using std::swap; swap(first[i], first[std::rand() % (i+1)]); // rand() % (i+1) 实际上不准确,因为生成的数对于多数 i 值不均匀分布。 // 正确实现将实际上需要重新实现 C++11 std::uniform_distributtion , // 这超出了此示例的范畴。 } } |
版本二 |
template<class RandomIt, class RandomFunc> void random_shuffle(RandomIt first, RandomIt last, RandomFunc&& r) { typename std::iterator_traits<RandomIt>::difference_type i, n; n = last - first; for (i = n-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; diff_t n = last - first; for (diff_t i = n-1; i > 0; --i) { using std::swap; swap(first[i], first[D(g, param_t(0, i))]); } } |
示例
下列代码随机打乱整数 1..10 :
运行此代码
#include <random> #include <algorithm> #include <iterator> #include <iostream> 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
参阅
产生某个元素范围的按字典顺序的下一个较大的排列 (函数模板) | |
产生某个元素范围的按字典顺序的下一个较小的排列 (函数模板) |