[libc++][ranges] Implement ranges::max_element

[philnik]

Summary

Implement ranges::max_element

[philnik]

• Fix CI

[Mordante]

In general looks good, but I'd like a bit more test coverage.

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.max_element.pass.cpp

29

Would it be possible to use special comparison and projection to validate the complexity?
Complexity: Exactly max(last - first - 1,0) comparisons and twice as many projections.

84

I would like a test where the maximum value occurs twice to validate whether it returns the first, per Returns: The first iterator i in the range….

90

For reviewing it would be nice to also validate the value assert(*ret == x); in all these tests.

[philnik]

In D117523#3308721, @Mordante wrote:

In general looks good, but I'd like a bit more test coverage.

Could you first review D117025? It's basically the same. I'll apply the changes there over here, once D117025 is done.

[Mordante]

In D117523#3308729, @philnik wrote:

In D117523#3308721, @Mordante wrote:

In general looks good, but I'd like a bit more test coverage.

Could you first review D117025? It's basically the same. I'll apply the changes there over here, once D117025 is done.

I'll look at it.

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.max_element.pass.cpp

84

I see in D117025 it has two times a min_element of 1 in the test at line 85.

[philnik]

• Fix CI
• Copy test from min_element

[• Quuxplusone]

Please git grep ranges::max_element and fix what you find. std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp needs updating at least.

[philnik]

• Enable niebloid test

[philnik]

• Rebased
• Fix CI

[philnik]

ping

[• Quuxplusone]

LGTM % comments, and the only significant comment affects the already-committed test for ranges::min_element. I think this is good to go, to get min and max back into parity; but then after that, they should both get some improved tests.

Also, before landing, please run a diff <(sed s/min/foo/g ranges_min_element.h) <(sed s/max/foo/g ranges_max_element.h) and make sure there are no extraneous differences between the two source files. If I understand correctly, there should only be one diff: the order of the arguments to __comp!

libcxx/include/__algorithm/ranges_max_element.h

35

Nit: static constexpr
https://quuxplusone.github.io/blog/2021/04/03/static-constexpr-whittling-knife/

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.max_element.pass.cpp

58–67

test_range is called only once — both here and in ranges.min_element.pass.cpp, although I feel sure I commented multiple times about this kind of thing. Replace its call-site there with

int a2[] = {7, 6, 5, 3, 4, 2, 1, 8};
assert(std::ranges::min_element(a) == a + 6);

and here with

int a2[] = {7, 6, 5, 3, 4, 2, 1, 8};
assert(std::ranges::max_element(a) == a + 7);

After that, think about whether there's any test coverage missing. (Hint: probably.)

[ldionne]

libcxx/include/algorithm

758

This forgot to update the synopsis with ranges::max_element. @philnik do you mind adding it?

libcxx/include/CMakeLists.txt

set(files
   __algorithm/partial_sort.h
   __algorithm/partial_sort_copy.h
   __algorithm/partition.h
   __algorithm/partition_copy.h
   __algorithm/partition_point.h
   __algorithm/pop_heap.h
   __algorithm/prev_permutation.h
   __algorithm/push_heap.h
+  __algorithm/ranges_max_element.h
   __algorithm/ranges_min_element.h
   __algorithm/ranges_swap_ranges.h
   __algorithm/remove.h
   __algorithm/remove_copy.h
   __algorithm/remove_copy_if.h
   __algorithm/remove_if.h
   __algorithm/replace.h
   __algorithm/replace_copy.h

libcxx/include/__algorithm/ranges_max_element.h

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_MAX_ELEMENT_H
+#define _LIBCPP___ALGORITHM_RANGES_MAX_ELEMENT_H
+
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __max_element {
+struct __fn {
+  template <class _Ip, class _Sp, class _Proj, class _Comp>
+  _LIBCPP_HIDE_FROM_ABI static constexpr
+  _Ip __go(_Ip __first, _Sp __last, _Comp& __comp, _Proj& __proj) {
+    if (__first == __last)
+      return __first;
+
+    _Ip __i = __first;
+    while (++__i != __last)
+      if (std::invoke(__comp, std::invoke(__proj, *__first), std::invoke(__proj, *__i)))
+        __first = __i;
+    return __first;
+  }
+
+  template <forward_iterator _Ip, sentinel_for<_Ip> _Sp, class _Proj = identity,
+            indirect_strict_weak_order<projected<_Ip, _Proj>> _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  _Ip operator()(_Ip __first, _Sp __last, _Comp __comp = {}, _Proj __proj = {}) const {
+    return __go(__first, __last, __comp, __proj);
+  }
+
+  template <forward_range _Rp, class _Proj = identity,
+            indirect_strict_weak_order<projected<iterator_t<_Rp>, _Proj>> _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  borrowed_iterator_t<_Rp> operator()(_Rp&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
+    return __go(ranges::begin(__r), ranges::end(__r), __comp, __proj);
+  }
+};
+} // namespace __max_element
+
+inline namespace __cpo {
+  inline constexpr auto max_element = __max_element::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_MAX_ELEMENT_H

libcxx/include/algorithm

 #include <__algorithm/minmax.h>
 #include <__algorithm/minmax_element.h>
 #include <__algorithm/mismatch.h>
 #include <__algorithm/move.h>
 #include <__algorithm/move_backward.h>
 #include <__algorithm/next_permutation.h>
 #include <__algorithm/none_of.h>
 #include <__algorithm/nth_element.h>
 #include <__algorithm/partial_sort.h>
 #include <__algorithm/partial_sort_copy.h>
 #include <__algorithm/partition.h>
 #include <__algorithm/partition_copy.h>
 #include <__algorithm/partition_point.h>
 #include <__algorithm/pop_heap.h>
 #include <__algorithm/prev_permutation.h>
 #include <__algorithm/push_heap.h>
+#include <__algorithm/ranges_max_element.h>
 #include <__algorithm/ranges_min_element.h>
 #include <__algorithm/ranges_swap_ranges.h>
 #include <__algorithm/remove.h>
 #include <__algorithm/remove_copy.h>
 #include <__algorithm/remove_copy_if.h>
 #include <__algorithm/remove_if.h>
 #include <__algorithm/replace.h>
 #include <__algorithm/replace_copy.h>

libcxx/include/module.modulemap

module __algorithm {
       module partial_sort             { private header "__algorithm/partial_sort.h" }
       module partial_sort_copy        { private header "__algorithm/partial_sort_copy.h" }
       module partition                { private header "__algorithm/partition.h" }
       module partition_copy           { private header "__algorithm/partition_copy.h" }
       module partition_point          { private header "__algorithm/partition_point.h" }
       module pop_heap                 { private header "__algorithm/pop_heap.h" }
       module prev_permutation         { private header "__algorithm/prev_permutation.h" }
       module push_heap                { private header "__algorithm/push_heap.h" }
+      module ranges_max_element       { private header "__algorithm/ranges_max_element.h" }
       module ranges_min_element       { private header "__algorithm/ranges_min_element.h" }
       module ranges_swap_ranges       { private header "__algorithm/ranges_swap_ranges.h" }
       module remove                   { private header "__algorithm/remove.h" }
       module remove_copy              { private header "__algorithm/remove_copy.h" }
       module remove_copy_if           { private header "__algorithm/remove_copy_if.h" }
       module remove_if                { private header "__algorithm/remove_if.h" }
       module replace                  { private header "__algorithm/replace.h" }
       module replace_copy             { private header "__algorithm/replace_copy.h" }

libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_max_element.module.verify.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: modules-build
+
+// WARNING: This test was generated by 'generate_private_header_tests.py'
+// and should not be edited manually.
+
+// expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max_element.h'}}
+#include <__algorithm/ranges_max_element.h>

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.max_element.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+//  template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
+//    indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
+//  constexpr I ranges::max_element(I first, S last, Comp comp = {}, Proj proj = {});
+//
+//  template<forward_range R, class Proj = identity,
+//    indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+//  constexpr borrowed_iterator_t<R> ranges::max_element(R&& r, Comp comp = {}, Proj proj = {});
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <random>
+#include <ranges>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class T>
+concept HasMaxElement = requires (T t) { std::ranges::max_element(t); };
+
+struct NoLessThanOp {};
+struct NotTotallyOrdered {
+  int i;
+  bool operator<(const NotTotallyOrdered& o) const { return i < o.i; }
+};
+
+static_assert(HasMaxElement<std::array<int, 0>>);
+static_assert(!HasMaxElement<int>);
+static_assert(!HasMaxElement<NoLessThanOp>);
+static_assert(!HasMaxElement<NotTotallyOrdered>);
+
+template <class Iter>
+constexpr void test_iterators(Iter first, Iter last) {
+  std::same_as<Iter> auto it = std::ranges::max_element(first, last);
+  if (first != last) {
+    for (Iter j = first; j != last; ++j)
+      assert(!(*j > *it));
+  } else {
+    assert(it == first);
+  }
+}
+
+template <class Range, class Iter>
+constexpr void test_range(Range&& rng, Iter begin, Iter end) {
+  std::same_as<Iter> auto it = std::ranges::max_element(std::forward<Range>(rng));
+  if (begin != end) {
+    for (Iter j = begin; j != end; ++j)
+      assert(!(*j > *it));
+  } else {
+    assert(it == begin);
+  }
+}
+
+template <class It>
+constexpr void test(std::initializer_list<int> a, int expected) {
+  const int* first = a.begin();
+  const int* last = a.end();
+  {
+    std::same_as<It> auto it = std::ranges::max_element(It(first), It(last));
+    assert(base(it) == first + expected);
+  }
+  {
+    using Sent = sentinel_wrapper<It>;
+    std::same_as<It> auto it = std::ranges::max_element(It(first), Sent(It(last)));
+    assert(base(it) == first + expected);
+  }
+  {
+    auto range = std::ranges::subrange(It(first), It(last));
+    std::same_as<It> auto it = std::ranges::max_element(range);
+    assert(base(it) == first + expected);
+  }
+  {
+    using Sent = sentinel_wrapper<It>;
+    auto range = std::ranges::subrange(It(first), Sent(It(last)));
+    std::same_as<It> auto it = std::ranges::max_element(range);
+    assert(base(it) == first + expected);
+  }
+}
+
+template <class It>
+constexpr bool test() {
+  test<It>({}, 0);
+  test<It>({1}, 0);
+  test<It>({1, 2}, 1);
+  test<It>({2, 1}, 0);
+  test<It>({2, 1, 2}, 0);
+  test<It>({2, 1, 1}, 0);
+
+  return true;
+}
+
+constexpr void test_borrowed_range_and_sentinel() {
+  int a[] = {7, 6, 1, 3, 5, 1, 2, 4};
+
+  int* ret = std::ranges::max_element(std::views::all(a));
+  assert(ret == a + 0);
+  assert(*ret == 7);
+}
+
+constexpr void test_comparator() {
+  int a[] = {7, 6, 9, 3, 5, 1, 2, 4};
+  int* ret = std::ranges::max_element(a, std::ranges::greater{});
+  assert(ret == a + 5);
+  assert(*ret == 1);
+}
+
+constexpr void test_projection() {
+  int a[] = {7, 6, 9, 3, 5, 1, 2, 4};
+  {
+    int* ret = std::ranges::max_element(a, std::ranges::less{}, [](int i) { return i == 5 ? 100 : i; });
+    assert(ret == a + 4);
+    assert(*ret == 5);
+  }
+  {
+    int* ret = std::ranges::max_element(a, std::less<int*>{}, [](int& i) { return &i; });
+    assert(ret == a + 7);
+    assert(*ret == 4);
+  }
+}
+
+struct Immobile {
+  int i;
+
+  constexpr Immobile(int i_) : i(i_) {}
+  Immobile(const Immobile&) = delete;
+  Immobile(Immobile&&) = delete;
+
+  auto operator<=>(const Immobile&) const = default;
+};
+
+constexpr void test_immobile() {
+
+  Immobile arr[] {1, 2, 3};
+  assert(std::ranges::max_element(arr) == arr);
+  assert(std::ranges::max_element(arr, arr + 3) == arr);
+}
+
+constexpr void test_dangling() {
+  int compares = 0;
+  int projections = 0;
+  auto comparator = [&](int a, int b) {
+    ++compares;
+    return a < b;
+  };
+  auto projection = [&](int a) {
+    ++projections;
+    return a;
+  };
+  [[maybe_unused]] std::same_as<std::ranges::dangling> auto ret =
+      std::ranges::max_element(std::array{1, 2, 3}, comparator, projection);
+  assert(compares == 2);
+  assert(projections == 4);
+}
+
+constexpr bool test() {
+
+  test<forward_iterator<const int*>>();
+  test<bidirectional_iterator<const int*>>();
+  test<random_access_iterator<const int*>>();
+  test<const int*>();
+
+  int a[] = {7, 6, 5, 3, 4, 2, 1, 8};
+  test_iterators(a, a + 8);
+  int a2[] = {7, 6, 5, 3, 4, 2, 1, 8};
+  test_range(a2, a2, a2 + 8);
+
+  test_borrowed_range_and_sentinel();
+  test_comparator();
+  test_projection();
+  test_dangling();
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

 //static_assert(test(std::ranges::is_partitioned, a, odd));
 //static_assert(test(std::ranges::is_permutation, a, a));
 //static_assert(test(std::ranges::is_sorted, a));
 //static_assert(test(std::ranges::is_sorted_until, a));
 //static_assert(test(std::ranges::lexicographical_compare, a, a));
 //static_assert(test(std::ranges::lower_bound, a, 42));
 //static_assert(test(std::ranges::make_heap, a));
 //static_assert(test(std::ranges::max, a));
-//static_assert(test(std::ranges::max_element, a));
+static_assert(test(std::ranges::max_element, a));
 //static_assert(test(std::ranges::merge, a, a, a));
 //static_assert(test(std::ranges::min, a));
 static_assert(test(std::ranges::min_element, a));
 //static_assert(test(std::ranges::minmax, a));
 //static_assert(test(std::ranges::minmax_element, a));
 //static_assert(test(std::ranges::mismatch, a, a));
 //static_assert(test(std::ranges::move, a, a));
 //static_assert(test(std::ranges::move_backward, a, a));