Proposed resolution:

This wording is relative to N4582.

1. Edit [alg.random.sample]/1 as indicated:

   template<class PopulationIterator, class SampleIterator,
            class Distance, class UniformRandomNumberGenerator>
     SampleIterator sample(PopulationIterator first, PopulationIterator last,
                           SampleIterator out, Distance n,
                           UniformRandomNumberGenerator&& g);
   

   -1- Requires::

   1. […]
   2. (1.6) — remove_reference_t<UniformRandomNumberGenerator> shall meet the requirements of a uniform random number generator type (26.6.1.3) whose return type is convertible to Distance.
   3. […]

2. Edit [alg.random.shuffle]/2 as indicated:

   template<class RandomAccessIterator, class UniformRandomNumberGenerator>
     void shuffle(RandomAccessIterator first,
                  RandomAccessIterator last,
                  UniformRandomNumberGenerator&& g);
   

   -1- […]

   -2- Requires: RandomAccessIterator shall satisfy the requirements of ValueSwappable (17.6.3.2). The type remove_reference_t<UniformRandomNumberGenerator> shall meet the requirements of a uniform random number generator (26.6.1.3) type whose return type is convertible to iterator_traits<RandomAccessIterator>::difference_type.

[ 2016-06 Oulu ]

Moved to P0/Ready during issues prioritization.

Friday: status to Immediate

std::shuffle and std::sample each accepts a UniformRandomNumberGenerator&& argument and says that "UniformRandomNumberGenerator shall meet the requirements of a uniform random number generator ([rand.req.urng]) type".

[rand.req.urng]/2 in turn starts with "A class G satisfies the requirements of a uniform random number generator if […]".

If an lvalue is passed, UniformRandomNumberGenerator is a reference type, not a class, and in fact expressions like G::min() will not compile if G is a reference type.