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。

如果满足以下任意条件，那么行为未定义：

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>，如果满足以下任意条件，那么行为未定义：

T 不是均匀随机位生成器 (UniformRandomBitGenerator) 。

T::result_type 不可转换到 std::iterator_traits<RandomIt>::difference_type.

(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) 实际上不准确，因为生成的数对于多数 i 值不均匀分布。 // 正确实现将实际上需要重新实现 C++11 std::uniform_distributtion， // 这超出了此示例的范畴。 } }
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
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 的混洗算法为推荐的替代者，因其使用了 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++ 标准。

缺陷报告	应用于	出版时的行为	正确行为
LWG 395	C++98	未指定重载 (1) 的随机来源，而且 std::rand 由于 C 库的要求不能作为来源	由实现定义，并且可以将 std::rand 作为来源
LWG 552	C++98	不要求重载 (2) 的随机来源是 r^[1]	要求是

↑ 重载 (3) 也有同样的缺陷，但那部分的解决方案不适用于 C++98。

参阅

next_permutation	产生某个元素范围的按字典顺序的下一个较大的排列 (函数模板)
prev_permutation	产生某个元素范围的按字典顺序的下一个较小的排列 (函数模板)
ranges::shuffle (C++20)	随机重排范围中的元素 (niebloid)

[1] 重载 (3) 也有同样的缺陷，但那部分的解决方案不适用于 C++98。

[1]

编译器支持
自立实现与有宿主实现
语言
标准库
标准库标头
具名要求
功能特性测试宏 (C++20)
语言支持库
概念库 (C++20)
元编程库 (C++11)
诊断库
通用工具库
字符串库
容器库
迭代器库
范围库 (C++20)
算法库
数值库
本地化库
输入/输出库
文件系统库 (C++17)
正则表达式库 (C++11)
并发支持库 (C++11)
技术规范
符号索引
外部库

std::random_shuffle, std::shuffle

参数

复杂度

可能的实现

注解

示例

缺陷报告

参阅

导航