std::ranges::shuffle
来自cppreference.com
定义于头文件 <algorithm>
|
||
调用签名 |
||
template< std::random_access_iterator I, std::sentinel_for<I> S, class Gen > requires std::permutable<I> && |
(1) | (C++20 起) |
template< ranges::random_access_range R, class Gen > requires std::permutable<ranges::iterator_t<R>> && |
(2) | (C++20 起) |
1) 重排给定范围
[first, last)
中的元素以使得那些元素的每个可能排列拥有相等的出现概率。2) 同 (1) ,但以
r
为范围,如同以 ranges::begin(r) 为 first
并以 ranges::end(r) 为 last
。此页面上描述的仿函数实体是 niebloid ,即:
实际上,它们能以函数对象,或以某些特殊编译器扩展实现。
参数
first, last | - | 要随机打乱的范围 |
r | - | 要随机打乱的范围 |
gen | - | 随机数生成器 |
返回值
等于 last
的迭代器。
复杂度
准确交换 (last - first) - 1
次。
可能的实现
struct shuffle_fn { template<std::random_access_iterator I, std::sentinel_for<I> S, class Gen> requires std::permutable<I> && std::uniform_random_bit_generator<std::remove_reference_t<Gen>> I operator()( I first, S last, Gen&& gen ) const { using diff_t = std::iter_difference_t<I>; using distr_t = std::uniform_int_distribution<diff_t>; using param_t = typename distr_t::param_type; distr_t D; const auto n{ last - first }; for (diff_t i{}; i != n; ++i) { ranges::iter_swap(first + i, first + D(gen, param_t(0, i))); } return ranges::next(first, last); } template<ranges::random_access_range R, class Gen> requires std::permutable<ranges::iterator_t<R>> && std::uniform_random_bit_generator<std::remove_reference_t<Gen>> ranges::borrowed_iterator_t<R> operator()( R&& r, Gen&& gen ) const { return (*this)(ranges::begin(r), ranges::end(r), std::move(gen)); } }; inline constexpr shuffle_fn shuffle{}; |
示例
运行此代码
#include <algorithm> #include <array> #include <iostream> #include <random> void print(const auto& a) { for (const auto e : a) { std::cout << e << ' '; } std::cout << "\n"; } int main() { std::array a{'A', 'B', 'C', 'D', 'E', 'F'}; print(a); std::random_device rd; std::mt19937 gen{rd()}; for (int i{}; i != 3; ++i) { std::ranges::shuffle(a, gen); print(a); } }
可能的输出:
A B C D E F F E A C D B E C B F A D B A E C F D
参阅
(C++20) |
产生某个元素范围的按字典序下一个较大的排列 (niebloid) |
(C++20) |
产生某个元素范围的按字典序下一个较小的排列 (niebloid) |
(C++17 前)(C++11) |
随机重排范围中的元素 (函数模板) |