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函數的底層實現。