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) 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 的洗牌算法是首选的替换，因为它使用 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。

[编辑] 另请参阅

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)
执行支持库 (C++26)
技术规范
符号索引
外部库

cppreference.com

命名空间

变体

视图

操作