名稱空間
變體
操作

std::random_shuffle, std::shuffle

來自 cppreference.com
< cpp‎ | 演算法
 
C++
 
演算法庫
有約束演算法與針對範圍的演算法 (C++20)
有約束的演算法，例如 ranges::copy、 ranges::sort 等……
執行策略 (C++17)
排序及相關操作
劃分操作
排序操作
二分搜尋操作
（於已劃分範圍上）
集合操作（於已排序範圍上）
歸併操作（於已排序範圍上）
堆操作
最小/最大值操作
(C++11)
(C++17)
字典序比較操作
(C++20)
排列操作
C 庫
數值操作
未初始化記憶體上的操作
 
定義於標頭檔案 <algorithm>
template< class RandomIt >
void random_shuffle( RandomIt first, RandomIt last );
 (1) (C++14 中已棄用)
(在 C++17 中已移除)
(2)
template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc& r );
 (C++11 前)
template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc&& r );
 (C++11 起)
(C++14 中已棄用)
(在 C++17 中已移除)
template< class RandomIt, class URBG >
void shuffle( RandomIt first, RandomIt last, URBG&& g );
 (3) (C++11 起)

重新排列給定範圍 [first, last) 中的元素，使得這些元素所有可能的排列都具有相同的出現機率。

1) 隨機源是實現定義的，但通常使用函式 std::rand。
2) 隨機源是函式物件 r。
如果滿足以下任何條件，則行為未定義：
  • r 的返回型別不可轉換為 std::iterator_traits<RandomIt>::difference_type。
  • 給定型別為 std::iterator_traits<RandomIt>::difference_type 的正值 n，r(n) 的結果不是區間 [​0​, n) 中隨機選擇的值。
3) 隨機源是物件 g。
假定型別 T 為 std::remove_reference_t<URBG>，如果滿足以下任何條件，則行為未定義：
(C++20 前)

如果*first 的型別不是 Swappable(C++11 前)RandomIt 不是 ValueSwappable(C++11 起)，則行為未定義。

目錄

[編輯] 引數

first, last - 定義要隨機洗牌的元素範圍的迭代器對
r - 返回隨機選擇值的函式物件
g - 返回隨機選擇值的生成器物件
型別要求
-
RandomIt 必須滿足 LegacyRandomAccessIterator 的要求。

[編輯] 複雜度

恰好 std::distance(first, last) - 1 次交換。

[編輯] 可能實現

另請參閱 libstdc++ 和 libc++ 中的實現。

random_shuffle (1) 
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) is not actually correct, because the generated number is
        // not uniformly distributed for most values of i. The correct code would be
        // a variation of the C++11 std::uniform_int_distribution implementation.
    }
}
random_shuffle (2) 
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)]);
    }
}
shuffle (3) 
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 作為其第三個引數。

[編輯] 示例

隨機洗牌整數序列 [1, 10]

執行此程式碼
#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++ 標準。

缺陷報告 應用於 釋出時的行為 正確的行為
LWG 395 C++98 過載 (1) 的隨機源未指定，且
由於 C 庫要求，std::rand 不能作為源		 它是實現定義的，
並且允許使用 std::rand
LWG 552
(N2423)		 C++98 未要求 r 作為
過載 (2) 的隨機源[1]		 需要
  1. ↑ 過載 (3) 存在相同的缺陷，但該部分的解決方案不適用於 C++98。

[編輯] 另請參閱

 生成元素範圍的下一個更大的字典序排列
(函式模板) [編輯]
 生成元素範圍的下一個更小的字典序排列
(函式模板) [編輯]
(C++20)
 隨機地重排一個範圍中的元素
(演算法函式物件)[編輯]
取自 “https://cppreference.tw/mwiki/index.php?title=cpp/algorithm/random_shuffle&oldid=180381”