std::ranges::shuffle

在标头 `<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

参阅

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

编译器支持
自立实现与有宿主实现
语言
标准库
标准库标头
具名要求
功能特性测试宏 (C++20)
语言支持库
概念库 (C++20)
元编程库 (C++11)
诊断库
通用工具库
字符串库
容器库
迭代器库
范围库 (C++20)
算法库
数值库
本地化库
输入/输出库
文件系统库 (C++17)
正则表达式库 (C++11)
并发支持库 (C++11)
技术规范
符号索引
外部库

std::ranges::shuffle

参数

返回值

复杂度

可能的实现

示例

参阅

导航