[Bug libstdc++/100223] New: Missing early return in std::partial_sort

[Bug libstdc++/100223] New: Missing early return in std::partial_sort

[hewillk at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100223

            Bug ID: 100223
           Summary: Missing early return in std::partial_sort
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: hewillk at gmail dot com
  Target Milestone: ---

Hi, can we add an early return to std::partial_sort to avoid unnecessary O(n)
operations when __first is equal to __middle, just like std::rotate does, and
make the result more consistent with ranges::partial_sort?

https://godbolt.org/z/Kb5x8zfeh

[Bug libstdc++/100223] Missing early return in std::partial_sort

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100223

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Arguably, the caller can do this check if they think it can occur in their
code. That way all calls to the algorithm don't pay for the check.

But it's probably cheap enough to check anyway.

[Bug libstdc++/100223] Missing early return in std::partial_sort

[hewillk at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100223

--- Comment #2 from 康桓瑋 <hewillk at gmail dot com> ---
(In reply to Jonathan Wakely from comment #1)
> Arguably, the caller can do this check if they think it can occur in their
> code. That way all calls to the algorithm don't pay for the check.
> 
> But it's probably cheap enough to check anyway.

Exactly, since the <algorithm> is full of such checks, I think there is nothing
wrong with adding one for partial_sort.