std::random_shuffle, std::shuffle
ja.cppreference.net より
(cpp/algorithm/shuffle から転送)
| ヘッダ <algorithm>
|
||
template< class RandomIt >
void random_shuffle( RandomIt first, RandomIt last );
|
で定義 (1) | (C++14 で非推奨) (C++17 で削除) |
template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc& r );
|
(2) | (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に変換可能でない。- 型
nの正の値std::iterator_traits<RandomIt>::difference_typeが与えられたとき、r(n)の結果が区間[0,n)内のランダムに選ばれた値ではない。
3) 乱数の生成源はオブジェクト
g です。 型
T を std::remove_reference_t<URBG> として与えたとき、以下の条件のいずれかが満たされる場合、動作は未定義です:
TUniformRandomBitGenerator ではない。
|
(C++20 まで) |
*first の型が Swappable(C++11 まで)RandomItValueSwappable(C++11 以降) でない場合、動作は未定義です。
引数
| first, last | - | ランダムにシャッフルする要素の 範囲 を指定するイテレータのペア |
| r | - | ランダムな値を返す関数オブジェクト |
| g | - | ランダムな値を返すジェネレータオブジェクト |
| 型要件 | ||
-RandomIt は LegacyRandomAccessIterator の要件を満たさなければなりません。
| ||
計算量
正確に std::distance(first, last) - 1 回の swap を行います。
実装例
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 の shuffle アルゴリズムは、第3引数として 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++ 標準に遡って適用されました。
| DR | 適用先 | 公開された動作 | 正しい動作 |
|---|---|---|---|
| LWG 395 | C++98 | オーバーロード (1) の乱数生成源が指定されておらず、 std::rand は C ライブラリの要件により生成源になり得なかった |
処理系定義であり、 std::rand の使用が許可される |
| LWG 552 (N2423) |
C++98 | rがオーバーロード (2)[1] |
の乱数生成源である必要がなかった |
- ↑ オーバーロード (3) にも同じ欠陥がありますが、その解決の一部は C++98 には適用されません。
関連項目
| 要素範囲の次の辞書式順序でより大きな順列を生成する (関数テンプレート & アルゴリズム関数オブジェクト) | |
(C++20) |
|
| 要素範囲の次の辞書式順序でより小さな順列を生成する (関数テンプレート & アルゴリズム関数オブジェクト) | |
(C++20) |
|
(C++20) |
範囲内の要素をランダムに並べ替える (アルゴリズム関数オブジェクト) |