C++ 中的 shuffle 与 random_shuffle 详解

让我们深入探讨一下 C++ 标准库中关于随机排列元素的两种方法，看看它们是如何工作的，以及我们应该如何在代码中做出最佳选择。

该函数会随机重新排列范围 [first, last) 内的元素。它的工作原理是将每个元素的值与某个随机选中的元素进行交换。当我们提供了特定的函数时，该函数将决定每次操作中选中哪个元素；否则，它将使用某种未指定的随机源。

让我们通过一段代码来看看它的具体用法：

// CPP program Illustrating the
// use of random_shuffle
#include 
using namespace std;

// random generator function
int randomfunc(int j)
{
    return rand() % j;
}

int main()
{
    srand(unsigned(time(0)));
    vector arr;

    // set some values:
    for (int j = 1; j < 10; ++j)

        // 1 2 3 4 5 6 7 8 9
        arr.push_back(j);

    // using built-in random generator
    random_shuffle(arr.begin(), arr.end());

    // using randomfunc
    random_shuffle(arr.begin(), arr.end(), randomfunc);

    // print out content:
    cout << "arr contains:";
    for (auto i = arr.begin(); i != arr.end(); ++i)
        cout << ' ' << *i;

    cout << endl;

    return 0;
}

输出：

arr contains: 5 8 1 7 9 6 4 3 2

INLINECODEb6f6f79e 函数同样是用来随机重新排列范围 [first, last) 内的元素，但它要求我们提供一个均匀随机数生成器（URNG）。它通过调用 INLINECODE3592259b 来决定选中哪个元素，并与当前元素进行交换。让我们看看它是如何使用的：

// CPP program Illustrating
// the use of shuffle
#include 
using namespace std;

// Driver Program
int main()
{
    array s{ 1, 2, 3, 4, 5 };

    // To obtain a time-based seed
    unsigned seed = 0;

    // Use of shuffle
    shuffle(s.begin(), s.end(), default_random_engine(seed));

    cout << "shuffled elements are:";
    for (int& i : s)
        cout << ' ' << i;
    cout << endl;

    return 0;
}

输出：

shuffled elements are: 3 1 5 4 2

C++ 中 shuffle 和 random_shuffle 有什么区别？

在实际开发中，理解这两者的细微差别对我们编写高质量的代码至关重要：

• 核心区别：主要区别在于底层的随机数生成机制。INLINECODE6bed9d37 使用的是 INLINECODE7fd2db16 函数来随机化项目；而 INLINECODEf7856283 使用的是 INLINECODEa8a1b241（Uniform Random Number Generator），这是一个更优质的随机数生成器。虽然通过特定的 random_shuffle 重载版本，我们也能获得类似的行为，但默认实现有所不同。

• 最佳实践：INLINECODE724d8be6 是对 INLINECODE950426d0 的改进。为了获得更好的随机性和结果，我们应该优先使用前者。在现代 C++ 编程中，random_shuffle 甚至已经被标记为弃用（Deprecated）。

• 底层实现对比：让我们深入一下，看看两者在交换变量时的具体逻辑差异。

random_shuffle 的逻辑：

    template
    void random_shuffle(RandomIt first, RandomIt last, RandomFunc&& r)
    {
        typename iterator_traits::difference_type i, n;
        n = last - first;
        for (i = n-1; i > 0; --i) {
            using std::swap;
            swap(first[i], first[r(i+1)]);
        }
    }
    

shuffle 的逻辑：

    template
    void shuffle(RandomIt first, RandomIt last, 
                 UniformRandomBitGenerator&& g)
    {
        typedef typename iterator_traits::difference_type diff_t;
        typedef uniform_int_distribution 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))]);
        }
    }