std::ranges::shuffle

来自cppreference.com
< cpp‎ | algorithm‎ | ranges
 
 
算法库
受约束算法及范围上的算法 (C++20)
受约束算法: std::ranges::copy, std::ranges::sort, ...
执行策略 (C++17)
不修改序列的操作
(C++11)(C++11)(C++11)
(C++17)
修改序列的操作
Partitioning operations
划分操作
排序操作
(C++11)
二分搜索操作
集合操作(在已排序范围上)
堆操作
(C++11)
最小/最大操作
(C++11)
(C++17)

排列
数值运算
未初始化存储上的操作
(C++17)
(C++17)
(C++17)
C 库
 
受约束算法
不修改序列的操作
修改序列的操作
划分操作
排序操作
二分搜索操作
集合操作(在已排序范围上)
堆操作
最小/最大操作
排列
未初始化存储上的操作
返回类型
 
在标头 <algorithm> 定义
调用签名
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 shuffle( I first, S last, Gen&& gen );
(1) (C++20 起)
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> shuffle( R&& r, Gen&& gen );
(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

参阅

产生某个元素范围的按字典序下一个较大的排列
(niebloid)
产生某个元素范围的按字典序下一个较小的排列
(niebloid)
(C++17 前)(C++11)
随机重排范围中的元素
(函数模板)