您的位置:

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函数的底层实现。