1093. Multiple definitions for random_shuffle algorithm

Section: 26.7.13 [alg.random.shuffle] Status: Resolved Submitter: Alisdair Meredith Opened: 2009-03-22 Last modified: 2016-01-28

Priority: Not Prioritized

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

View all issues with Resolved status.

Discussion:

There are a couple of issues with the declaration of the random_shuffle algorithm accepting a random number engine.

1. The Iterators must be shuffle iterators, yet this requirement is missing.
2. The RandomNumberEngine concept is now provided by the random number library (n2836) and the placeholder should be removed.

[ 2009-05-02 Daniel adds: ]

this issue completes adding necessary requirement to the third new random_shuffle overload. The current suggestion is:

template<RandomAccessIterator Iter, UniformRandomNumberGenerator Rand>
requires ShuffleIterator<Iter>
void random_shuffle(Iter first, Iter last, Rand&& g);

IMO this is still insufficient and I suggest to add the requirement

Convertible<Rand::result_type, Iter::difference_type>

to the list (as the two other overloads already have).

Rationale:

Its true that this third overload is somewhat different from the remaining two. Nevertheless we know from UniformRandomNumberGenerator, that it's result_type is an integral type and that it satisfies UnsignedIntegralLike<result_type>.

To realize it's designated task, the algorithm has to invoke the Callable aspect of g and needs to perform some algebra involving it's min()/max() limits to compute another index value that at this point is converted into Iter::difference_type. This is so, because 24.3.5.7 [random.access.iterators] uses this type as argument of it's algebraic operators. Alternatively consider the equivalent iterator algorithms in 24.4.3 [iterator.operations] with the same result.

This argument leads us to the conclusion that we also need Convertible<Rand::result_type, Iter::difference_type> here.

[ Batavia (2009-05): ]

Alisdair notes that point (ii) has already been addressed.

We agree with the proposed resolution to point (i) with Daniel's added requirement.

Move to Review.

[ 2009-06-05 Daniel updated proposed wording as recommended in Batavia. ]

[ 2009-07-28 Alisdair adds: ]

Revert to Open, with a note there is consensus on direction but the wording needs updating to reflect removal of concepts.

[ 2009-10 post-Santa Cruz: ]

Leave Open, Walter to work on it.

[ 2010 Pittsburgh: Moved to NAD EditorialResolved, addressed by N3056. ]

Rationale:

Solved by N3056.

Proposed resolution:

Change in [algorithms.syn] and 26.7.13 [alg.random.shuffle]:

concept UniformRandomNumberGenerator<typename Rand> { }
template<RandomAccessIterator Iter, UniformRandomNumberGenerator Rand>
  requires ShuffleIterator<Iter> &&
  Convertible<Rand::result_type, Iter::difference_type>
  void random_shuffle(Iter first, Iter last, Rand&& g);