Title
std::ranges::shuffle synopsis does not match algorithm definition
Status
c++20
Section
[alg.random.shuffle]
Submitter
Christopher Di Bella

Created on 2019-03-02.00:00:00 last changed 37 months ago

Messages

Date: 2019-06-17.03:21:08

Proposed resolution:

This wording is relative to N4800.

  1. Change [algorithm.syn] as indicated:

    // [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);
    }
    […]
    
Date: 2019-06-16.00:00:00

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

Date: 2019-03-05.00:00:00

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

Date: 2019-03-05.00:00:00

[ 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 [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);
    }
    
Date: 2019-03-15.00:00:00

[ 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.

Date: 2019-03-02.00:00:00

[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);
}

[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.

History
Date User Action Args
2021-02-25 10:48:01adminsetstatus: wp -> c++20
2019-07-22 15:46:37adminsetstatus: voting -> wp
2019-06-17 05:25:36adminsetstatus: ready -> voting
2019-06-17 03:21:08adminsetmessages: + msg10453
2019-06-17 03:21:08adminsetstatus: new -> ready
2019-03-05 19:25:33adminsetmessages: + msg10344
2019-03-05 18:54:44adminsetmessages: + msg10343
2019-03-03 19:21:59adminsetmessages: + msg10336
2019-03-03 19:21:59adminsetmessages: + msg10335
2019-03-02 00:00:00admincreate