]> git.ipfire.org Git - people/ms/gcc.git/commit
libstdc++: Reduce ranges::minmax/minmax_element comparison complexity
authorPatrick Palka <ppalka@redhat.com>
Fri, 18 Jun 2021 23:33:39 +0000 (19:33 -0400)
committerPatrick Palka <ppalka@redhat.com>
Fri, 18 Jun 2021 23:33:39 +0000 (19:33 -0400)
commitcc9c94d43dcfa98436152af9c00f011e9dab25f6
tree2f588eb09a0135ca675ccfaa3cbc1ba57d435901
parenta798b3f15c47be55f535b754932a820b858870a8
libstdc++: Reduce ranges::minmax/minmax_element comparison complexity

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.

PR libstdc++/100387

libstdc++-v3/ChangeLog:

* include/bits/ranges_algo.h (__minmax_fn::operator()): Rewrite
to limit comparison complexity to 3*N/2.
(__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
libstdc++-v3/testsuite/25_algorithms/minmax/constrained.cc
libstdc++-v3/testsuite/25_algorithms/minmax_element/constrained.cc