[alg.random.shuffle] ranges::shuffle - "exactly" or "at most" for number of swaps? #5636
Comments
|
I think this issue fits in the scope of LWG issues rather than editorial ones. |
|
The two have the same effect per [structure.specifications]/7:
|
Perhaps this should be repurposed as an editorial issue asking why we sometimes say "at most" and sometimes "exactly" instead of picking a single form to use consistently? |
Thanks for the clarification, @timsong-cpp. As Casey said, I'd like to understand if there's a good reason for the difference in the use of "at most" versus "exactly" instead of one consistent form throughout. |
|
"Exactly" is clearly erroneous. For example, if the range has size 2, then it would require the algorithm to always swap them or to swap an element with itself. More generally, requiring a specific number of swaps excludes half the possible shuffles, except by using a self-swap. |
In
[alg.random.shuffle]section, forranges::shuffle, the standard states that the complexity is exactly(last - first) - 1)swaps. In some other algorithms, the wording of at most for the number of swaps is used.Should we change the wording for
ranges::shuffleto say at most instead of exactly for the number of swaps? It would be nice for a standard library implementation to perform fewer swaps than required where possible and still be conforming. If not, can someone provide clarity on why there must be exactly this number of swaps in all cases?This came up during discussion in the
libc++implementation ofranges::shufflehereThe text was updated successfully, but these errors were encountered: