search

cplusplus / draft

C++ standards drafts
http://www.open-std.org/jtc1/sc22/wg21/
5.66k stars 749 forks source link

[alg.random.shuffle] ranges::shuffle - "exactly" or "at most" for number of swaps? #5636

Open JoeLoser opened 2 years ago

JoeLoser commented 2 years ago

In [alg.random.shuffle] section, for ranges::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::shuffle to 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 of ranges::shuffle here

frederick-vs-ja commented 2 years ago

I think this issue fits in the scope of LWG issues rather than editorial ones.

timsong-cpp commented 2 years ago

The two have the same effect per [structure.specifications]/7:

Complexity requirements specified in the library clauses are upper bounds, and implementations that provide better complexity guarantees meet the requirements.

CaseyCarter commented 2 years ago

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?

JoeLoser commented 2 years ago

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.

Eric41293 commented 1 year ago

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