C++ shuffle函数——构建乱序序列

一、shuffle函数是什么

shuffle是C++STL（标准模板库）中的一个函数模板，它能构建一组乱序的序列。该模板函数定义在头文件中。shuffle函数的定义如下：

template
void shuffle(RandomAccessIterator first, RandomAccessIterator last, 
             UniformRandomBitGenerator&& g);

其中，RandomAccessIterator表示指向序列的迭代器，first和last分别指定了被重排的元素的范围。UniformRandomBitGenerator是一个随机数生成器引用（可以是任意支持括号运算符的对象或函数），用于提供随机化的数据源。

二、shuffle函数的使用方法

该函数的使用非常简单，首先定义一个数组或者向量等存储有序序列，然后调用shuffle函数随机打乱该序列，例如：

#include <iostream>
#include <algorithm>
#include <vector>
#include <time.h>
using namespace std;
int main(){
    vector<int> v(10);
    for (int i = 0; i < 10; i++){
        v[i] = i+1;
    }
    srand(time(NULL));          //设置随机种子
    random_shuffle(v.begin(), v.end());   //乱序序列
    for (int i = 0; i < 10; i++){
        cout << v[i] << " ";
    }
    cout << endl;
    return 0;
}

注意需要调用srand函数设置随机数的种子。其实，C++11中也定义了一个新函数shuffle，调用方式如下：

#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <time.h>
using namespace std;
int main(){
    vector<int> v(10);
    for (int i = 0; i < 10; i++){
        v[i] = i+1;
    }
    default_random_engine e(time(0));   //设置随机种子
    shuffle(v.begin(), v.end(), e);        //乱序序列
    for (int i = 0; i < 10; i++){
        cout << v[i] << " ";
    }
    cout << endl;
    return 0;
}

这里用C++11标准库提供的default_random_engine作为随机数生成器，可以不必调用srand函数。

三、cshuffle函数的实现

实际上，shuffle函数底层调用的是cshuffle函数，cshuffle函数是一个纯C函数，定义在头文件中。

其定义如下：

void cshuffle(void* base, size_t count, size_t size);

cshuffle函数以void指针作为输入，可以接受任意类型的数组，其中，base表示数组的首元素地址，count表示数组中元素的个数，size表示数组的元素大小。下面给出cshuffle函数的c++实现：

#include <iostream>
#include <algorithm>
#include <vector>
#include <time.h>
using namespace std;
void cshuffle(void* base, size_t count, size_t size){
    for(size_t i=count-1;i>0;i--){
        size_t j=rand() % (i+1);
        if(i!=j){
            void* p1=(char*)base+i*size;
            void* p2=(char*)base+j*size;
            swap(p1,p2);
        }
    }
}
int main(){
    int a[]={1,2,3,4,5};
    size_t len=sizeof(a)/sizeof(a[0]);
    cshuffle(a,len,sizeof(int));    //乱序序列
    for(size_t i=0; i<len; i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return 0;
}

四、小结

shuffle函数能够方便快捷地构建乱序序列，在使用前需要设置随机种子。

cshuffle函数是shuffle函数的底层实现，在底层使用了随机交换元素的方法，实现了打乱序列的效果。

总之，shuffle函数的使用方式非常简便，cshuffle函数的实现方法能深入理解shuffle函数的底层实现。