namespace std::ranges {
template <random_access_iterator I,
sentinel_for<I> S,
class Gen>
requires permutable<I> &&
uniform_random_bit_generator<remove_reference_t<Gen>>
I
shuffle(I first,
S last,
Gen&& g); // (1) C++20
template <random_access_range R,
class Gen>
requires permutable<iterator_t<R>> &&
uniform_random_bit_generator<remove_reference_t<Gen>>
borrowed_iterator_t<R>
shuffle(R&& r,
Gen&& g); // (2) C++20
}
概要
範囲のそれぞれの要素を同じ確率で並び替える。
- (1): イテレータ範囲を指定する
- (2): Rangeを直接指定する
計算量
正確に (last - first) - 1
回 swap する。
備考
以下の実装では、フィッシャー - イェーツのシャッフルアルゴリズムが使用されている:
- GCC: 4.9 (libstdc++)
- Clang: 3.4 (libc++)
- Visual C++: 2013
例
整数の配列をシャッフルする
#include <algorithm>
#include <iostream>
#include <vector>
#include <numeric>
#include <iterator>
#include <random>
int main() {
std::vector<int> v(10);
std::iota(v.begin(), v.end(), 0); // 0~9 までの値を生成
std::cout << "before: ";
std::ranges::copy(v, std::ostream_iterator<int>(std::cout));
std::cout << std::endl;
// シャッフル
std::random_device seed_gen;
std::mt19937 engine(seed_gen());
std::ranges::shuffle(v, engine);
std::cout << " after: ";
std::ranges::copy(v, std::ostream_iterator<int>(std::cout));
std::cout << std::endl;
}
出力例
before: 0123456789
after: 5803429716
文字列をシャッフルする
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
int main() {
std::string input = "0123456789abcdef";
std::cout << "before: " << input << std::endl;
// シャッフル
std::random_device seed_gen;
std::mt19937 engine(seed_gen());
std::ranges::shuffle(input, engine);
std::cout << " after: " << input << std::endl;
}
出力例
before: 0123456789abcdef
after: 49e351b8f0ad62c7
バージョン
言語
- C++20
処理系
- Clang: ??
- GCC: 10.1.0 ✅
- ICC: ??
- Visual C++: 2019 Update 10 ✅