std::ranges::shuffle - cppreference.com (original) (raw)

1. Reorders the elements in the given range [first, last) such that each possible permutation of those elements has equal probability of appearance.

2. Same as (1), but uses r as the range, as if using ranges::begin(r) as first and ranges::end(r) as last.

The function-like entities described on this page are algorithm function objects (informally known as niebloids), that is:

• Explicit template argument lists cannot be specified when calling any of them.
• None of them are visible to argument-dependent lookup.
• When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.

Contents

• 1 Parameters
• 2 Return value
• 3 Complexity
• 4 Possible implementation
• 5 Example
• 6 See also

[edit] Parameters

[edit] Return value

An iterator equal to last.

[edit] Complexity

Exactly (last - first) - 1 swaps.

[edit] Possible implementation

struct shuffle_fn { template<std::random_access_iterator I, std::sentinel_for S, class Gen> requires std::permutable && std::uniform_random_bit_generator<std::remove_reference_t> I operator()(I first, S last, Gen&& gen) const { using diff_t = std::iter_difference_t; using distr_t = std::uniform_int_distribution; using param_t = typename distr_t::param_type; distr_t D; const auto n {last - first}; for (diff_t i {1}; 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> && std::uniform_random_bit_generator<std::remove_reference_t> ranges::borrowed_iterator_t operator()(R&& r, Gen&& gen) const { return (*this)(ranges::begin(r), ranges::end(r), std::forward(gen)); } };   inline constexpr shuffle_fn shuffle {};

[edit] Example

#include #include #include #include   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); } }

Possible output:

A B C D E F F E A C D B E C B F A D B A E C F D

[edit] See also