随机重排算法

MSTL随机重排算法的实现 更多...

函数
template<typename Iterator, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
void	shuffle (Iterator first, Iterator last)
	随机重排序列
template<typename Iterator, typename Generator, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
void	shuffle (Iterator first, Iterator last, Generator &rand)
	随机重排序列（使用自定义随机数生成器）

详细描述

MSTL随机重排算法的实现

函数说明

shuffle() [1/2]

template<typename Iterator, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>

void shuffle	(	Iterator	first,
		Iterator	last )

随机重排序列

模板参数

Iterator

随机访问迭代器类型

参数

first	序列起始迭代器
last	序列结束迭代器

使用Fisher-Yates洗牌算法（Knuth洗牌）将范围 [first, last) 中的元素随机重排。 算法对每个位置 i（从第二个元素开始），在 [first, i] 范围内随机选择一个位置 j， 然后交换位置 i 和 j 的元素。

注解

要求 Iterator 满足随机访问迭代器概念

使用默认的 random_lcd 线性同余随机数生成器

在文件 shuffle.hpp 第 34 行定义.

引用了 _MSTL, distance(), iter_swap(), next() , 以及 random_lcd::next_int().

shuffle() [2/2]

template<typename Iterator, typename Generator, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>

void shuffle	(	Iterator	first,
		Iterator	last,
		Generator &	rand )

随机重排序列（使用自定义随机数生成器）

模板参数

Iterator	随机访问迭代器类型
Generator	随机数生成器类型

参数

first	序列起始迭代器
last	序列结束迭代器
rand	自定义随机数生成器

使用Fisher-Yates洗牌算法将范围 [first, last) 中的元素随机重排。 允许使用自定义的随机数生成器，提供更大的灵活性。

随机数生成器需要满足以下要求：

• 可调用，接受一个整数参数 n
• 返回 [0, n) 范围内的随机整数

注解

要求 Iterator 满足随机访问迭代器概念

随机数生成器必须提供 operator()(integer) -> integer 方法

在文件 shuffle.hpp 第 63 行定义.

引用了 _MSTL, iter_swap() , 以及 next().