std::random_shuffle, std::shuffle

template< class RandomIt >
void random_shuffle( RandomIt first, RandomIt last );

template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc& r );

template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc&& r );

template< class RandomIt, class URBG >
void shuffle( RandomIt first, RandomIt last, URBG&& g );

将给定范围 [first, last) 中的元素重新排序，使得这些元素的每个可能排列都以相等的概率出现。

如果 *first 的类型不是 Swappable(C++11 前)RandomIt 不是 ValueSwappable(C++11 起)，则行为未定义。

参数

复杂度

恰好需要 std:: distance ( first, last ) - 1 次交换。

可能的实现

另请参阅 libstdc++ 与 libc++ 中的实现。

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_int_distribution 实现的变体。
    }
}

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)]);
    }
}

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 作为其第三个参数。

示例

#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++ 标准。

1. ↑ 重载 (3) 存在相同缺陷，但该部分决议不适用于 C++98。

参见