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

[JoeLoser]

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]

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

[timsong-cpp]

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]

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]

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]

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