mercredi 31 juillet 2019

A question about implementation of std::shuffle using URBG

With reference to the (possible) implementation of the third version of std::shuffle template as outlined in std::random_shuffle, std::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))]);
    }
}

I was trying to understand how the URBG object g is used along with std::uniform_int_distribution<diff_t> to get a result within the closed range [g, param_t(0, i)]:

swap(first[i], first[D(g, param_t(0, i))]);

Based on the explanation for distr_t::param_type provided under C++ named requirements: RandomNumberDistribution:

Given

  • P, the type named by D::param_type
  • d, a value of type D
  • p, a (possibly const) value of type P
  • g, g1, g2, lvalues of a type satisfying UniformRandomBitGenerator

The following expressions must be valid and have their specified effects:

d(g,p) The sequence of numbers returned by successive invocations of this call with the same g are randomly distributed according to the distribution parametrized by p

since in the above invocation:

swap(first[i], first[D(g, param_t(0, i))]);

the distribution parametrized by param_t(0, i) always falls within the required distribution range, the invocation of g should also generate a random result type (int) within the distribution range.

Is this understanding correct?




Aucun commentaire:

Enregistrer un commentaire