[libc++][ranges] Implement ranges::min_element

[philnik]

Summary

Implement ranges::min_element

[miscco]

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

120

Is there a reason the tests are disabled?

[philnik]

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

120

Just forgot to re-enable it. Thanks for noting.

[philnik]

• Guard with HAS_NO_RANGES and enable constepxr test

[philnik]

• Rebased
• Fix CI

[• Quuxplusone]

libcxx/include/__algorithm/ranges_min_element.h

50

This makes copies of __comp and __proj. At the very least we should std::move them; but I think we should also give serious consideration to just taking them by forwarding reference to begin with.

Speaking of how scary it is to mess with overload sets... what's the mandated behavior for a call like std::ranges::min_element(42) — does it need to SFINAE away quietly? If so, we should have a test for that.

libcxx/include/algorithm

26

Nit: lowercase since C++20 to match line 23 (and generally)

libcxx/include/module.modulemap

284

Typo here. I'll update lint_modulemap.sh.py. :)

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

31

I see zero reason for this test to use randomness. We just need to check that it works when the first element is the min; when the last element is the min; when some middle element is the min; when there's a tie for min; when the range's size is 1; when the range's size is 0; when the range's value type is immobile (i.e. we shouldn't ever be copying/moving elements).
And then check for SFINAE when the thing isn't a range; when the range's value type isn't <-comparable; when it is <-comparable but not totally_ordered.
I would also expect to see the word std::ranges::dangling used at least once in this test file.

[philnik]

• Address comments

[philnik]

• Add forward include

[philnik]

• Fix forward

[philnik]

• Fix CI

[philnik]

• Rebased
• Put implementation into other function
• Move Immobile declaration out of function

[philnik]

• IWYU

[• Quuxplusone]

The code looks great at this point! Significant comments on the test.

libcxx/include/__algorithm/ranges_min_element.h

35

Remove blank line.

44

bool(...) is unnecessary here, because the invoke_result_t of a predicate is guaranteed to be boolean-testable. If someone thinks the cast looks nice for some reason, I won't complain too much; but IMHO you should eliminate the cast as unnecessary.

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

33–34

Please either name this concept HasMinElement, or just use
static_assert(!std::is_invocable_v<decltype(std::ranges::min_element), int&>);
etc. without defining a named concept at all. I have a slight preference for the latter.
(Also, surely T i should be T t or perhaps R& r. Notice that you only ever pass lvalues here; that's one reason it would be clearer to use is_invocable_v instead of the named concept.)

71

Moot style point: Stylistically I prefer (x , ...) over (x, ...) for the same reason I prefer (x + ...) over (x+ ...).
However, this strikes me as vastly too "clever". I think the ultimate reason for this is line 131, which should just be 4 lines. My same comments from the mismatch review apply here: let's keep these tests as simple as possible, so we can tell what's going wrong when one fails without a lot of metaprogramming-debugging; and also so that we can be sure our tests are actually testing what we intend, and not being nerfed by some accidental bug in the metaprogramming.

95–101

See, this is a great test, because it's simple enough that I think I see what it's doing. ;)
Nits: indentation on line 95; prefer () over {} on line 97. But FWIW, I'd just write

{
  int a[] = {2, 3, 1, 3, 2};
  int *ret = std::ranges::min_element(a, std::greater());
  assert(ret == a + 1);
}
{
  const int a[] = {2, 3, 1, 3, 2};
  const int *ret = std::ranges::min_element(a, std::less());
  assert(ret == a + 2);
}

or something like that. I don't think we need sentinel_wrapper or subrange (or std::ranges::greater) if the goal is to test the comparator codepath specifically.

107

Nice example of a call where the answer would be different if the predicate weren't there!
I'd like to see one additional test where the projected type is not the same type as the range's value_type, e.g.

int a[] = {2, 1, 3};
int *ret = std::ranges::min_element(a, std::less<int*>(), [](int& i) { return &i; });
assert(ret == a);

128

Moot: , 0 is kind of a weird corner case; I'd make this , 10 or , 42.
But also, we need to test this behavior outside an unevaluated expression. I suggest

constexpr void test_dangling()
{
  int a[] = {2, 1, 3};
  int compares = 0;
  int projections = 0;
  auto comparator = [&](int a, int b) { compares += 1; return a < b; };
  auto projection = [&](int a) { projections += 1; return a; };
  std::same_as<std::ranges::dangling> auto r =
    std::ranges::min_element(r, comparator, projection);
  assert(compares == 2);
  assert(projections == 4);
}

[philnik]

• Address comments

[philnik]

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

71

The reason was that I didn't want to run test_range multiple times, and having a single fold expression doesn't strike me as very much meta-programming.
I prefer (x, ...) for the same reason I write fun(a, b) and not fun(a , b).

95–101

Why do you want to test std::less? It's tested literally every where else.

[• Quuxplusone]

Let's fix that variadic test function. It's cheap and easy to fix.

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

71

I prefer (x, ...) for the same reason I write fun(a, b) and not fun(a , b).

I would have said the same thing! ;) I write fun(a, b) and {1, 2} and so on because each of those commas represents the comma separator. But when I use the comma operator, at least in a fold-expression context where the reader might casually mistake it for the comma separator, I'll call out that unusual usage by formatting it like an operator.

75

95–101

Well, in general TDD terms, testing two different comparators "proves" that the implementation isn't just "if there's a comparator object then reverse all the comparisons" or something. But I don't mind just testing std::greater.
(I'd still prefer std::greater() over std::ranges::greater{}, purely for style: it's shorter and causes fewer dependencies. But whatever.)
No further action required here.

107

Here please use std::less<int*>() with the specific type int*, because I want to verify that the comparator doesn't need to be callable with the original element type — we want it to be callable (and called) only with the projected type.

128

You can remove line 128 (the static_assert) now, which will allow you to remove #include <array> (and eliminate the weirdness of std::array<T, 0>).

150–153

[philnik]

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

128

I'm still using std::array in line 140.

[philnik]

• Address comments

[• Quuxplusone]

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

72

I would like to see us test some ranges that are not std::array. Given the implementation, I guess it's not likely that anything could go wrong; but still, you could get vastly more mileage out of this test by making it something like

template<class It>
constexpr void test_one_case(std::initializer_list<int> a, int expected_idx) {
  int *first = a.begin();
  int *last = a.end();
  {
    std::same_as<It> auto it = std::ranges::min_element(It(first), It(last));
    assert(base(it) == first + expected_idx);
  }
  {
    using Sent = std::sentinel_wrapper<It>;
    std::same_as<It> auto it = std::ranges::min_element(It(first), Sent(It(last)));
    assert(base(it) == first + expected_idx);
  }
  {
    auto r = std::ranges::subrange(It(first), It(last));
    std::same_as<It> auto it = std::ranges::min_element(r);
    assert(base(it) == first + expected_idx);
  }
  {
    using Sent = std::sentinel_wrapper<It>;
    auto r = std::ranges::subrange(It(first), Sent(It(last)));
    std::same_as<It> auto it = std::ranges::min_element(r);
    assert(base(it) == first + expected_idx);
  }
}

template<class It>
constexpr void test_cases()
  test_one_case<It>({}, 0);
  test_one_case<It>({1}, 0);
  test_one_case<It>({1, 2, 1}, 0);
  test_one_case<It>({2, 1, 3}, 1);
  test_one_case<It>({3, 2, 1}, 2);
}

~~~
  test_cases<forward_iterator<int*>>();
  test_cases<bidirectional_iterator<int*>>();
  [etc.]

75

Throughout: s/Iters/Iter/ (or even It).
Lines 76-81: Is the first template parameter always just the length of the initializer-list?

[philnik]

• Address comments

[Mordante]

LGTM modulo one suggestion.

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

108

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

[philnik]

Thanks for the review @Mordante!

• Address comment

[• Quuxplusone]

LGTM assuming all comments have been addressed. Please make sure that you transfer all relevant improvements over to D117523, and vice versa if there are any comments on D117523 over to here.

[philnik]

• Rebased
• Fix CI

[philnik]

• Use _LIBCPP_HAS_NO_CONCEPTS

libcxx/docs/Status/RangesAlgorithms.csv

 Search,partition_point,Christopher Di Bella,`D105794 <https://llvm.org/D105794>`_,Under review
 Search,lower_bound,Christopher Di Bella,`D105795 <https://llvm.org/D105795>`_,Under review
 Search,upper_bound,Christopher Di Bella,`D105795 <https://llvm.org/D105795>`_,Under review
 Search,equal_range,Christopher Di Bella,n/a,Not started
 Search,binary_search,Christopher Di Bella,n/a,Not started
 Search,min,Not assigned,n/a,Not started
 Search,max,Not assigned,n/a,Not started
 Search,minmax,Not assigned,n/a,Not started
-Search,min_element,Not assigned,n/a,Not started
+Search,min_element,Nikolas Klauser,n/a,Complete
 Search,max_element,Not assigned,n/a,Not started
 Search,minmax_element,Not assigned,n/a,Not started
 Search,count,Not assigned,n/a,Not started
 Search,count_if,Not assigned,n/a,Not started
 Search,search,Not assigned,n/a,Not started
 Search,search_n,Not assigned,n/a,Not started
 Search,find_end,Not assigned,n/a,Not started
 Read-only,is_partitioned,Christopher Di Bella,`D105794 <https://llvm.org/D105794>`_,Under review

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_min_element.h
   __algorithm/remove.h
   __algorithm/remove_copy.h
   __algorithm/remove_copy_if.h
   __algorithm/remove_if.h
   __algorithm/replace.h
   __algorithm/replace_copy.h
   __algorithm/replace_copy_if.h
   __algorithm/replace_if.h

libcxx/include/__algorithm/ranges_min_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_MIN_ELEMENT_H
+#define _LIBCPP___ALGORITHM_RANGES_MIN_ELEMENT_H
+
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/projected.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/forward.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+#ifndef _LIBCPP_HAS_NO_RANGES
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __min_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 (bool(_VSTD::invoke(__comp, _VSTD::invoke(__proj, *__i), _VSTD::invoke(__proj, *__first))))
+        __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 __min_element
+
+inline namespace __cpo {
+  inline constexpr auto min_element = __min_element::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_HAS_NO_RANGES
+
+#endif // _LIBCPP___ALGORITHM_RANGES_MIN_ELEMENT_H

libcxx/include/algorithm

 #include <initializer_list>
 
 namespace std
 {
 
 namespace ranges {
   template <class I1, class I2>
     struct in_in_result; // since C++20
+
+  template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
+    indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>             // since C++20
+  constexpr I min_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> // since C++20
+  constexpr borrowed_iterator_t<R> min_element(R&& r, Comp comp = {}, Proj proj = {});
 }
 
 template <class InputIterator, class Predicate>
     constexpr bool     // constexpr in C++20
     all_of(InputIterator first, InputIterator last, Predicate pred);
 
 template <class InputIterator, class Predicate>
     constexpr bool     // constexpr in C++20

 #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_min_element.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>
 #include <__algorithm/replace_copy_if.h>
 #include <__algorithm/replace_if.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_min_element       { private header "__algorithm/ranges_min_element.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" }
       module replace_copy_if          { private header "__algorithm/replace_copy_if.h" }
       module replace_if               { private header "__algorithm/replace_if.h" }

libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_min_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_min_element.h'}}
+#include <__algorithm/ranges_min_element.h>

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min_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::min_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::min_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 MinElementCallable = requires (T i) { std::ranges::min_element(i); };
+
+struct NoLessThanOp {};
+struct NotTotallyOrdered {
+  int i;
+  bool operator<(const NotTotallyOrdered& o) const { return i < o.i; }
+};
+
+static_assert(MinElementCallable<std::array<int, 0>>);
+static_assert(!MinElementCallable<int>);
+static_assert(!MinElementCallable<NoLessThanOp>);
+static_assert(!MinElementCallable<NotTotallyOrdered>);
+
+template <class Iter>
+constexpr void test_iterators(Iter first, Iter last) {
+  std::same_as<Iter> auto it = std::ranges::min_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::min_element(std::forward<Range>(rng));
+  if (begin != end) {
+    for (Iter j = begin; j != end; ++j)
+      assert(!(*j < *it));
+  } else {
+    assert(it == begin);
+  }
+}
+
+template <size_t N, class... Iters>
+constexpr void test(std::array<int, N> a) {
+  (test_iterators(Iters(a.begin()), Iters(a.end())), ...);
+  test_range(a, a.begin(), a.end());
+}
+
+template <class... Iters>
+constexpr bool test() {
+  test<0, Iters...>({});
+  test<1, Iters...>({1});
+  test<2, Iters...>({1, 2});
+  test<2, Iters...>({2, 1});
+  test<3, Iters...>({2, 1, 2});
+  test<3, Iters...>({2, 1, 1});
+
+  return true;
+}
+
+constexpr void test_borrowed_range_and_sentinel() {
+  int a[] = {7, 6, 1, 3, 5, 1, 2, 4};
+
+  std::ranges::subrange sr {a, sentinel_wrapper(a + 8)};
+  int* ret = std::ranges::min_element(sr);
+  assert(ret == a + 2);
+}
+
+constexpr void test_comparator() {
+    int a[] = {7, 6, 9, 3, 5, 1, 2, 4};
+
+  std::ranges::subrange sr {a, sentinel_wrapper(a + 8)};
+  int* ret = std::ranges::min_element(sr, std::ranges::greater{});
+  assert(ret == a + 2);
+}
+
+constexpr void test_projection() {
+  int a[] = {7, 6, 9, 3, 5, 1, 2, 4};
+
+  std::ranges::subrange sr {a, sentinel_wrapper(a + 8)};
+  int* ret = std::ranges::min_element(sr, std::ranges::less{}, [](int i){ return i == 5 ? -100 : i; });
+  assert(ret == a + 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::min_element(arr) == arr);
+  assert(std::ranges::min_element(arr, arr + 3) == arr);
+}
+
+static_assert(std::is_same_v<std::ranges::dangling, decltype(std::ranges::min_element(std::array<int, 0>{}))>);
+
+constexpr bool test() {
+
+  test<forward_iterator<const int*>,
+       bidirectional_iterator<const int*>,
+       random_access_iterator<const int*>,
+       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();
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}