69 lines
3.3 KiB
Markdown
69 lines
3.3 KiB
Markdown
[alg.random.shuffle]
|
||
|
||
# 26 Algorithms library [[algorithms]](./#algorithms)
|
||
|
||
## 26.7 Mutating sequence operations [[alg.modifying.operations]](alg.modifying.operations#alg.random.shuffle)
|
||
|
||
### 26.7.13 Shuffle [alg.random.shuffle]
|
||
|
||
[ð](#lib:shuffle)
|
||
|
||
`template<class RandomAccessIterator, class UniformRandomBitGenerator>
|
||
void shuffle(RandomAccessIterator first,
|
||
RandomAccessIterator last,
|
||
UniformRandomBitGenerator&& g);
|
||
|
||
template<[random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_for [iterator.concept.sentinel]")<I> S, class Gen>
|
||
requires [permutable](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]")<I> &&
|
||
[uniform_random_bit_generator](rand.req.urng#concept:uniform_random_bit_generator "29.5.3.3 Uniform random bit generator requirements [rand.req.urng]")<remove_reference_t<Gen>>
|
||
I ranges::shuffle(I first, S last, Gen&& g);
|
||
template<[random_access_range](range.refinements#concept:random_access_range "25.4.6 Other range refinements [range.refinements]") R, class Gen>
|
||
requires [permutable](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]")<iterator_t<R>> &&
|
||
[uniform_random_bit_generator](rand.req.urng#concept:uniform_random_bit_generator "29.5.3.3 Uniform random bit generator requirements [rand.req.urng]")<remove_reference_t<Gen>>
|
||
borrowed_iterator_t<R> ranges::shuffle(R&& r, Gen&& g);
|
||
`
|
||
|
||
[1](#1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8491)
|
||
|
||
*Preconditions*: For the overload in namespace std:
|
||
|
||
- [(1.1)](#1.1)
|
||
|
||
RandomAccessIterator meets
|
||
the [*Cpp17ValueSwappable*](swappable.requirements#:Cpp17ValueSwappable "16.4.4.3 Swappable requirements [swappable.requirements]") requirements ([[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements"))[.](#1.1.sentence-1)
|
||
|
||
- [(1.2)](#1.2)
|
||
|
||
The type remove_reference_t<UniformRandomBitGenerator> meets
|
||
the uniform random bit generator ([[rand.req.urng]](rand.req.urng "29.5.3.3 Uniform random bit generator requirements")) requirements[.](#1.2.sentence-1)
|
||
|
||
[2](#2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8503)
|
||
|
||
*Effects*: Permutes the elements in the range [first, last)
|
||
such that each possible permutation of those elements
|
||
has equal probability of appearance[.](#2.sentence-1)
|
||
|
||
[3](#3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8509)
|
||
|
||
*Returns*: last for the overloads in namespace ranges[.](#3.sentence-1)
|
||
|
||
[4](#4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8513)
|
||
|
||
*Complexity*: Exactly (last - first) - 1 swaps[.](#4.sentence-1)
|
||
|
||
[5](#5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8517)
|
||
|
||
*Remarks*: To the extent that the implementation of this function makes use
|
||
of random numbers, the object referenced by g shall serve as
|
||
the implementation's source of randomness[.](#5.sentence-1)
|