3191. std::ranges::shuffle synopsis does not match algorithm definition

Section: 26.7.13 [alg.random.shuffle] Status: C++20 Submitter: Christopher Di Bella Opened: 2019-03-02 Last modified: 2021-02-25

Priority: 1

View all other issues in [alg.random.shuffle].

View all issues with C++20 status.

Discussion:

26.4 [algorithm.syn] declares std::ranges::shuffle like so:

namespace ranges {
  template<RandomAccessIterator I, Sentinel<I> S, class Gen>
    requires Permutable<I> &&
             UniformRandomBitGenerator<remove_reference_t<Gen>> &&
             ConvertibleTo<invoke_result_t<Gen&>, iter_difference_t<I>>
  I shuffle(I first, S last, Gen&& g);

  template<RandomAccessRange R, class Gen>
    requires Permutable<iterator_t<R> &&
             UniformRandomBitGenerator<remove_reference_t<Gen>> &&
             ConvertibleTo<invoke_result_t<Gen&>, iter_difference_t<iterator_t<R>>>
  safe_iterator_t<R> shuffle(R&& r, Gen&& g);
}

26.7.13 [alg.random.shuffle] defines the algorithm like so:

namespace ranges {
  template<RandomAccessIterator I, Sentinel<I> S, class Gen>
    requires Permutable<I> &&
             UniformRandomBitGenerator<remove_reference_t<Gen>>
  I shuffle(I first, S last, Gen&& g);

  template<RandomAccessRange R, class Gen>
    requires Permutable<iterator_t<R>> &&
             UniformRandomBitGenerator<remove_reference_t<Gen>>
  safe_iterator_t<R> shuffle(R&& r, Gen&& g);
}

Notice the missing ConvertibleTo requirements in the latter. Looking at the Ranges TS, [alg.random.shuffle] includes this requirement, albeit in the Ranges TS-format.

[2019-03-03; Daniel comments]

Given that the accepted proposal P0896R4 voted in San Diego did contain the same error I decided to open this issue instead of submitting an editorial change request.

[2019-03-05 Priority set to 1 after reflector discussion]

Casey: The correct fix here is to remove the ConvertibleTo requirement from the header synopsis. UniformRandomBitGenerators have integral result types, and the core language guarantees that all integral types are convertible to all other integral types. We don't need to validate the core language in the associated constraints of ranges::shuffle.

Previous resolution [SUPERSEDED]:

This wording is relative to N4800.

1. Change 26.7.13 [alg.random.shuffle] as indicated:

   […]
   namespace ranges {
     template<RandomAccessIterator I, Sentinel<I> S, class Gen>
       requires Permutable<I> &&
                UniformRandomBitGenerator<remove_reference_t<Gen>> &&
                ConvertibleTo<invoke_result_t<Gen&>, iter_difference_t<I>>
       I shuffle(I first, S last, Gen&& g);
     template<RandomAccessRange R, class Gen>
       requires Permutable<iterator_t<R>> &&
                UniformRandomBitGenerator<remove_reference_t<Gen>> &&
                ConvertibleTo<invoke_result_t<Gen&>, iter_difference_t<iterator_t<R>>>
       safe_iterator_t<R> shuffle(R&& r, Gen&& g);
   }
   

[2019-03-05 Updated proposed wording according to Casey's suggestion]

[2019-06-16 Set to "Tentatively Ready" after five positive votes on the reflector.]

Proposed resolution:

This wording is relative to N4800.

1. Change 26.4 [algorithm.syn] as indicated:

   // 26.7.13 [alg.random.shuffle], shuffle
   […]
   namespace ranges {
     template<RandomAccessIterator I, Sentinel<I> S, class Gen>
       requires Permutable<I> &&
                UniformRandomBitGenerator<remove_reference_t<Gen>> &&
                ConvertibleTo<invoke_result_t<Gen&>, iter_difference_t<I>>
     I shuffle(I first, S last, Gen&& g);
   
     template<RandomAccessRange R, class Gen>
       requires Permutable<iterator_t<R> &&
                UniformRandomBitGenerator<remove_reference_t<Gen>> &&
                ConvertibleTo<invoke_result_t<Gen&>, iter_difference_t<iterator_t<R>>>
     safe_iterator_t<R> shuffle(R&& r, Gen&& g);
   }
   […]