Index: libcxx/include/__algorithm/ranges_minmax.h =================================================================== --- libcxx/include/__algorithm/ranges_minmax.h +++ libcxx/include/__algorithm/ranges_minmax.h @@ -76,8 +76,7 @@ _LIBCPP_ASSERT(__first != __last, "range has to contain at least one element"); if constexpr (forward_range<_Range>) { - auto __result = std::__minmax_element_impl(__first, __last, __comp, __proj); - return {*__result.first, *__result.second}; + return __minmax_fwd_unchecked(__first, __last, __comp, __proj); } else { // input_iterators can't be copied, so the implementation for input_iterators has to store // the values instead of a pointer to the correct values @@ -120,6 +119,65 @@ return __result; } } +private: + template + [[nodiscard]] static constexpr minmax_result> __minmax_fwd_unchecked( + _It __first, const _Se __last, _Pr __pred, _Pj __proj) { + _LIBCPP_ASSERT(forward_iterator<_It>, "_It must be forward_iterator"); + _LIBCPP_ASSERT((sentinel_for<_Se, _It>), "_Se must be sentinel for _It"); + _LIBCPP_ASSERT((indirect_strict_weak_order<_Pr, projected<_It, _Pj>>), ""); + + _LIBCPP_ASSERT(__first != __last, "range has to contain at least one element"); + + using _ValueT = iter_value_t<_It>; + + auto __found_min = __first; + if (++__first == __last) { + // This initialization is correct, similar to the N4928 [dcl.init.aggr]/6 example + minmax_result<_ValueT> __result = {static_cast<_ValueT>(*__found_min), __result.min}; + return __result; + } + + auto __found_max = __first; + if (std::invoke(__pred, std::invoke(__proj, *__found_max), std::invoke(__proj, *__found_min))) { + ranges::swap(__found_min, __found_max); + } + + while (++__first != __last) { // process one or two elements + _It __prev = __first; + if (++__first == __last) { // process last element + if (std::invoke(__pred, std::invoke(__proj, *__prev), std::invoke(__proj, *__found_min))) { + __found_min = __prev; + } else if (!std::invoke(__pred, std::invoke(__proj, *__prev), std::invoke(__proj, *__found_max))) { + __found_max = __prev; + } + + break; + } + + // process two elements + if (std::invoke(__pred, std::invoke(__proj, *__first), std::invoke(__proj, *__prev))) { + // test __first for new smallest + if (std::invoke(__pred, std::invoke(__proj, *__first), std::invoke(__proj, *__found_min))) { + __found_min = __first; + } + + if (!std::invoke(__pred, std::invoke(__proj, *__prev), std::invoke(__proj, *__found_max))) { + __found_max = __prev; + } + } else { // test __prev for new smallest + if (std::invoke(__pred, std::invoke(__proj, *__prev), std::invoke(__proj, *__found_min))) { + __found_min = __prev; + } + + if (!std::invoke(__pred, std::invoke(__proj, *__first), std::invoke(__proj, *__found_max))) { + __found_max = __first; + } + } + } + + return {static_cast<_ValueT>(*__found_min), static_cast<_ValueT>(*__found_max)}; + } }; } // namespace __minmax Index: libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp =================================================================== --- libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp +++ libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp @@ -334,12 +334,43 @@ return true; } +class input_move_iterator { +public: + using iterator_category = std::input_iterator_tag; + using iterator_concept = std::input_iterator_tag; + using difference_type = std::ptrdiff_t; + using value_type = std::shared_ptr; + using pointer = std::shared_ptr*; + using reference = std::shared_ptr&&; + + input_move_iterator() = default; + explicit input_move_iterator(std::shared_ptr* ptr) : m_ptr(ptr) {} + + reference operator*() const { return std::ranges::iter_move(m_ptr); } + pointer operator->() const { return m_ptr; } + + input_move_iterator& operator++() { + ++m_ptr; + return *this; + } + input_move_iterator operator++(int) { + input_move_iterator tmp = *this; + ++*this; + return tmp; + } + + friend bool operator==(const input_move_iterator& a, const input_move_iterator& b) { return a.m_ptr == b.m_ptr; } + +private: + std::shared_ptr* m_ptr{nullptr}; +}; + int main(int, char**) { test(); static_assert(test()); { - // check that the iterator isn't moved from multiple times + // check that the random access iterator isn't moved from multiple times std::shared_ptr a[] = { std::make_shared(42) }; auto range = std::ranges::subrange(std::move_iterator(a), std::move_iterator(a + 1)); auto [min, max] = std::ranges::minmax(range); @@ -347,6 +378,15 @@ assert(min != nullptr); assert(max == min); } + { + // check that the input iterator isn't moved from multiple times + std::shared_ptr a[] = {std::make_shared(42)}; + auto range = std::ranges::subrange(input_move_iterator(a), input_move_iterator(a + 1)); + auto [min, max] = std::ranges::minmax(range); + assert(a[0] == nullptr); + assert(min != nullptr); + assert(max == min); + } return 0; }