A possible implementation of std::shuffle

user_6864265 0
Viewed 122

Here is an algorithm std::shuffle from https://en.cppreference.com/w/cpp/algorithm/random_shuffle:

 template<class RandomIt, class URBG>
 void shuffle(RandomIt first, RandomIt last, URBG&& g)
 {
     typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
     typedef std::uniform_int_distribution<diff_t> distr_t;
     typedef typename distr_t::param_type param_t;

     distr_t D;
     diff_t n = last - first;
     for (diff_t i = n-1; i > 0; --i) {
         using std::swap;
         swap(first[i], first[D(g, param_t(0, i))]);
     }
 }

  • Why the algorithm takes a forwarding reference to the generator URGB&& g? As long as it didn't use std::forward<URGB>(g) to forward the generator either as an l-value or as an r-value?

  • Why the using declaration is inside of loop body rather than outside of it? Does leaving it inside (iteratively) affects performance? Thank you!

forwarding-reference shuffle algorithm c++
1 Answers

Why the algorithm takes a forwarding reference to the generator URGB&& g?

Because the algorithm does not want to copy the generator, it passes by reference, and in order to be able to accept the temporary rvalue generator, it takes a forwarding reference.

As long as it didn't use std::forward<URGB>(g) to forward the generator either as an l-value or as an r-value?

Because the generator is not only invoked once. If the rvalue is forwarded, its state may be changed before the next invoked.

Why the using declaration is inside of loop body rather than outside of it?

This is a so-called std::swap two-step, and it is idiomatic to use unqualified swap immediately after using std::swap. The advantage of putting it inside the loop is that its scope is limited to the loop, and putting it outside may pollute the naming.

Does leaving it inside (iteratively) affects performance?

No.

user_116387180
Related