命名空间
变体
操作

std::random_shuffle, std::shuffle

来自 cppreference.cn
< cpp‎ | algorithm
 
 
算法库
约束算法和范围上的算法 (C++20)
约束算法,例如 ranges::copy, ranges::sort, ...
执行策略 (C++17)
排序和相关操作
划分操作
排序操作
二分搜索操作
(在已划分范围上)
集合操作(在已排序范围上)
归并操作(在已排序范围上)
堆操作
最小值/最大值操作
(C++11)
(C++17)
字典序比较操作
排列操作
C 库
数值操作
未初始化内存上的操作
 
定义于头文件 <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 起)

重排序给定范围 [firstlast) 中的元素,使得这些元素的每个可能排列都具有相等的出现概率。

1) 随机性来源是实现定义的,但通常使用函数 std::rand
2) 随机性来源是函数对象 r
如果满足以下任何条件,则行为是未定义的
  • r 的返回类型不能转换为 std::iterator_traits<RandomIt>::difference_type
  • 给定类型为 std::iterator_traits<RandomIt>::difference_type 的正值 nr(n) 的结果不是区间 [0n) 中随机选择的值。
3) 随机性来源是对象 g
给定类型 Tstd::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 次交换。

[编辑] 可能的实现

另请参见 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))]);
    }
}

[编辑] 注意

请注意,实现并非由标准规定,因此即使您使用完全相同的 RandomFuncURBG(均匀随机数生成器),您也可能在使用不同的标准库实现时获得不同的结果。

在 C++17 中移除 std::random_shuffle 的原因是,仅迭代器版本通常依赖于 std::rand,而现在 std::rand 也被讨论是否弃用。(std::rand 应该被 <random> 头文件中的类替换,因为 std::rand认为是有害的。)此外,仅迭代器 std::random_shuffle 版本通常依赖于全局状态。std::shuffle 的 shuffle 算法是首选的替代方案,因为它使用 URBG 作为其第三个参数。

[编辑] 示例

随机打乱整数序列 [110]

#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]
已要求
  1. 重载 (3) 具有相同的缺陷,但该解决方案的该部分不适用于 C++98。

[编辑] 参见

生成一个元素范围的下一个更大的字典序排列
(函数模板) [编辑]
生成一个元素范围的下一个更小的字典序排列
(函数模板) [编辑]
随机重排一个范围内的元素
(算法函数对象)[编辑]