On 05/05/21 10:39 +0100, Jonathan Wakely wrote:
On 04/05/21 21:42 -0400, Patrick Palka via Libstdc++ wrote:
This rewrites ranges::minmax and ranges::minmax_element so that it
performs at most 3*N/2 many comparisons, as required by the standard.
In passing, this also fixes PR100387 by avoiding a premature std::move
in ranges::minmax and in std::shift_right.
Tested on x86_64-pc-linux-gnu, does this look OK for trunk and perhaps
10/11?
libstdc++-v3/ChangeLog:
PR libstdc++/100387
* include/bits/ranges_algo.h (__minmax_fn::operator()): Rewrite
to limit comparison complexity to 3*N/2. Avoid premature std::move.
(__minmax_element_fn::operator()): Likewise.
(shift_right): Avoid premature std::move of __result.
* testsuite/25_algorithms/minmax/constrained.cc (test04, test05):
New tests.
* testsuite/25_algorithms/minmax_element/constrained.cc (test02):
Likewise.
---
libstdc++-v3/include/bits/ranges_algo.h | 87 ++++++++++++++-----
.../25_algorithms/minmax/constrained.cc | 31 +++++++
.../minmax_element/constrained.cc | 19 ++++
3 files changed, 113 insertions(+), 24 deletions(-)
diff --git a/libstdc++-v3/include/bits/ranges_algo.h
b/libstdc++-v3/include/bits/ranges_algo.h
index cda3042c11f..bbd29127e89 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -3291,18 +3291,39 @@ namespace ranges
auto __first = ranges::begin(__r);
auto __last = ranges::end(__r);
__glibcxx_assert(__first != __last);
+ auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
minmax_result<range_value_t<_Range>> __result = {*__first, *__first};
while (++__first != __last)
{
- auto __tmp = *__first;
- if (std::__invoke(__comp,
- std::__invoke(__proj, __tmp),
- std::__invoke(__proj, __result.min)))
- __result.min = std::move(__tmp);
- if (!(bool)std::__invoke(__comp,
- std::__invoke(__proj, __tmp),
- std::__invoke(__proj, __result.max)))
- __result.max = std::move(__tmp);
+ // Process two elements at a time so that we perform at most
+ // 3*N/2 many comparisons in total (each of the N/2 iterations
Is "many" a typo here?
+ // of this loop performs three comparisions).
+ auto __val1 = *__first;
Can we avoid making this copy if the range satisfies forward_range, by
keeping copies of the min/max iterators, or just forwarding to
ranges::minmax_element?
Hmm, on the other hand, for a forward range of ints we're probably
better off jsut making the copy here and not going through the
indirections done by minmax_element.
Maybe something like:
if constexpr (forward_range<_Range> && is_scalar_v<range_value_t<_Range>>)
