[libcxx][algorithms] adds ranges::find_if and ranges::find_if_not

[cjdb]

Summary

Implements part of http://wg21.link/p0896.
Implements part of [alg.find].

Depends on D105456.

[cjdb]

rebases to activate CI

[cjdb]

removes unnecessary complexity_iterator from find_if_not (you only need complexity_iterator if you're unable to use complexity_invocable)

[cjdb]

fixes test that broke when I removed complexity_iterator

[cjdb]

rebases to activate CI

libcxx/include/__algorithm/find_if.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // 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_FIND_IF_H
 #define _LIBCPP___ALGORITHM_FIND_IF_H
 
 #include <__config>
+#include <__function_like.h>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/reference_wrapper.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
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _InputIterator, class _Predicate>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _InputIterator
 find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) {
   for (; __first != __last; ++__first)
     if (__pred(*__first))
       break;
   return __first;
 }
 
+#if !defined(_LIBCPP_HAS_NO_RANGES)
+
+namespace ranges {
+  struct __find_if_fn final : __function_like {
+    constexpr explicit __find_if_fn(__tag __x) noexcept : __function_like(__x) {}
+
+    template<input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Proj = identity,
+             indirect_unary_predicate<projected<_Ip, _Proj>> _Pred>
+    _LIBCPP_NODISCARD_EXT constexpr
+    _Ip operator()(_Ip __first, const _Sp __last, _Pred __pred, _Proj __proj = {}) const {
+      for (; __first != __last; ++__first) {
+        if (_VSTD::invoke(__pred, _VSTD::invoke(__proj, *__first))) {
+          return __first;
+        }
+      }
+
+      return __first;
+    }
+
+    template<input_range _Rp, class _Proj = identity,
+             indirect_unary_predicate<projected<iterator_t<_Rp>, _Proj>> _Pred>
+    _LIBCPP_NODISCARD_EXT constexpr
+    borrowed_iterator_t<_Rp> operator()(_Rp&& __r, _Pred __pred, _Proj __proj = {}) const {
+      return (*this)(ranges::begin(__r), ranges::end(__r), _VSTD::ref(__pred), _VSTD::ref(__proj));
+    }
+  };
+
+  inline constexpr auto find_if = __find_if_fn(__function_like::__tag());
+} // namespace ranges
+
+#endif // !defined(_LIBCPP_HAS_NO_RANGES)
+
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ALGORITHM_FIND_IF_H

libcxx/include/__algorithm/find_if_not.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // 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_FIND_IF_NOT_H
 #define _LIBCPP___ALGORITHM_FIND_IF_NOT_H
 
 #include <__config>
+#include <__function_like.h>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/reference_wrapper.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
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _InputIterator, class _Predicate>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _InputIterator
 find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred) {
   for (; __first != __last; ++__first)
     if (!__pred(*__first))
       break;
   return __first;
 }
 
+#if !defined(_LIBCPP_HAS_NO_RANGES)
+
+namespace ranges {
+  struct __find_if_not_fn final : __function_like {
+    constexpr explicit __find_if_not_fn(__tag __x) noexcept : __function_like(__x) {}
+
+    template<input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Proj = identity,
+             indirect_unary_predicate<projected<_Ip, _Proj>> _Pred>
+    _LIBCPP_NODISCARD_EXT constexpr
+    _Ip operator()(_Ip __first, const _Sp __last, _Pred __pred, _Proj __proj = {}) const {
+      for (; __first != __last; ++__first) {
+        if (!_VSTD::invoke(__pred, _VSTD::invoke(__proj, *__first))) {
+          return __first;
+        }
+      }
+
+      return __first;
+    }
+
+    template<input_range _Rp, class _Proj = identity,
+             indirect_unary_predicate<projected<iterator_t<_Rp>, _Proj>> _Pred>
+    _LIBCPP_NODISCARD_EXT constexpr
+    borrowed_iterator_t<_Rp> operator()(_Rp&& __r, _Pred __pred, _Proj __proj = {}) const {
+      return (*this)(ranges::begin(__r), ranges::end(__r), _VSTD::ref(__pred), _VSTD::ref(__proj));
+    }
+  };
+
+  inline constexpr auto find_if_not = __find_if_not_fn(__function_like::__tag());
+} // namespace ranges
+
+#endif // !defined(_LIBCPP_HAS_NO_RANGES)
+
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ALGORITHM_FIND_IF_NOT_H

libcxx/include/algorithm

template<input_range R, class T, class Proj = identity>
   requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
   constexpr borrowed_iterator_t<R>
     ranges::find(R&& r, const T& value, Proj proj = {}); // since C++20
 
 template <class InputIterator, class Predicate>
     constexpr InputIterator     // constexpr in C++20
     find_if(InputIterator first, InputIterator last, Predicate pred);
 
+template<input_iterator I, sentinel_for<I> S, class Proj = identity,
+         indirect_unary_predicate<projected<I, Proj>> Pred>
+  constexpr I ranges::find_if(I first, S last, Pred pred, Proj proj = {});      // since C++20
+
+template<input_range R, class Proj = identity,
+         indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+  constexpr borrowed_iterator_t<R>
+    ranges::find_if(R&& r, Pred pred, Proj proj = {});                          // since C++20
+
 template<class InputIterator, class Predicate>
     constexpr InputIterator     // constexpr in C++20
     find_if_not(InputIterator first, InputIterator last, Predicate pred);
 
+template<input_iterator I, sentinel_for<I> S, class Proj = identity,
+         indirect_unary_predicate<projected<I, Proj>> Pred>
+  constexpr I ranges::find_if_not(I first, S last, Pred pred, Proj proj = {});  // since C++20
+
+template<input_range R, class Proj = identity,
+         indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+  constexpr borrowed_iterator_t<R>
+    ranges::find_if_not(R&& r, Pred pred, Proj proj = {});                      // since C++20
+
 template <class ForwardIterator1, class ForwardIterator2>
     constexpr ForwardIterator1  // constexpr in C++20
     find_end(ForwardIterator1 first1, ForwardIterator1 last1,
              ForwardIterator2 first2, ForwardIterator2 last2);
 
 template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
     constexpr ForwardIterator1  // constexpr in C++20
     find_end(ForwardIterator1 first1, ForwardIterator1 last1,

libcxx/include/module.modulemap

module __algorithm {
       module fill                     { header "__algorithm/fill.h" }
       module fill_n                   { header "__algorithm/fill_n.h" }
       module find {
         header "__algorithm/find.h"
         export __function_like
       }
       module find_end                 { header "__algorithm/find_end.h" }
       module find_first_of            { header "__algorithm/find_first_of.h" }
-      module find_if                  { header "__algorithm/find_if.h" }
-      module find_if_not              { header "__algorithm/find_if_not.h" }
+      module find_if {
+        header "__algorithm/find_if.h"
+        export __function_like
+      }
+      module find_if_not {
+        header "__algorithm/find_if_not.h"
+        export __function_like
+      }
       module for_each                 { header "__algorithm/for_each.h" }
       module for_each_n               { header "__algorithm/for_each_n.h" }
       module generate                 { header "__algorithm/generate.h" }
       module generate_n               { header "__algorithm/generate_n.h" }
       module half_positive            { header "__algorithm/half_positive.h" }
       module includes                 { header "__algorithm/includes.h" }
       module inplace_merge            { header "__algorithm/inplace_merge.h" }
       module is_heap                  { header "__algorithm/is_heap.h" }

libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.pass.cpp

 
 int main(int, char**) {
   auto arr = std::array{0, 1, 2, 3, 4, 5};
   namespace ranges = std::ranges;
 
   ranges::find(ranges::begin(arr), ranges::end(arr), 1);
   ranges::find(arr, 1);
 
+  ranges::find_if(ranges::begin(arr), ranges::end(arr), [](auto) { return true; });
+  ranges::find_if(arr, [](auto) { return true; });
+
+  ranges::find_if_not(ranges::begin(arr), ranges::end(arr), [](auto) { return true; });
+  ranges::find_if_not(arr, [](auto) { return true; });
+
   return 0;
 }

libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.verify.cpp

int main()
   auto arr = std::array{0, 1, 2, 3, 4, 5};
   namespace ranges = std::ranges;
 
   // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
   ranges::find(ranges::begin(arr), ranges::end(arr), 1);
 
   // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
   ranges::find(arr, 1);
+
+  // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
+  ranges::find_if(ranges::begin(arr), ranges::end(arr), [](auto) { return true; });
+
+  // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
+  ranges::find_if(arr, [](auto) { return true; });
+
+  // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
+  ranges::find_if_not(ranges::begin(arr), ranges::end(arr), [](auto) { return true; });
+
+  // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
+  ranges::find_if_not(arr, [](auto) { return true; });
 }

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find_if/ranges_find_if.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// <algorithm>
+
+// ranges::find_if
+
+#include <algorithm>
+
+#include <array>
+#include <cassert>
+#include <concepts>
+#include <ranges>
+#include <utility>
+#include <vector>
+
+#include "test_algorithm.h"
+#include "test_macros.h"
+#include "test_iterators.h"
+#include "test_range.h"
+
+namespace ranges = std::ranges;
+
+template<template<class...> class I>
+constexpr bool check_find_if()
+{
+
+  auto range = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+  auto successor = [](auto const x) { return x + 1; };
+
+  {
+    auto pred = complexity_invocable([](int const x) { return x == 6; });
+    constexpr auto expected_complexity = 7;
+    auto const expected_result = range.begin() + 6;
+    {
+      auto input = ranges::subrange(I(range.begin()), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if(input.begin(), input.end(), std::ref(pred));
+      assert(result.base() == expected_result);
+    }
+    {
+      auto input = ranges::subrange(I(range.begin()), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if(input, std::ref(pred));
+      assert(result.base() == expected_result);
+    }
+    assert(pred.count() == 2 * expected_complexity);
+  }
+  {
+    auto pred = complexity_invocable([](double const x) { return x == 3.0; });
+    constexpr auto expected_complexity = 4;
+    auto const expected_result = range.begin() + 3;
+    {
+      auto input = ranges::subrange(I(range.begin()), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if(input.begin(), input.end(), std::ref(pred));
+      assert(result.base() == expected_result);
+    }
+    {
+      auto input = ranges::subrange(I(range.begin()), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if(input, std::ref(pred));
+      assert(result.base() == expected_result);
+    }
+    assert(pred.count() == 2 * expected_complexity);
+  }
+  {
+    auto pred = complexity_invocable([](double const x) { return x == 3.7; });
+    constexpr auto expected_complexity = ranges::ssize(range);
+    auto const expected_result = range.begin() + expected_complexity;
+    {
+      auto input = ranges::subrange(I(range.begin()), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if(input.begin(), input.end(), std::ref(pred));
+      assert(result.base() == expected_result);
+    }
+    {
+      auto input = ranges::subrange(I(range.begin()), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if(input, std::ref(pred));
+      assert(result.base() == expected_result);
+    }
+    assert(pred.count() == 2 * expected_complexity);
+  }
+  {
+    auto pred = complexity_invocable([](int const x) { return x == 6; });
+    auto proj = complexity_invocable(successor);
+    constexpr auto expected_complexity = 6;
+    auto const expected_result = range.begin() + 5;
+    {
+      auto input = ranges::subrange(I(range.begin()), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if(input.begin(), input.end(), std::ref(pred), std::ref(proj));
+      assert(result.base() == expected_result);
+    }
+    {
+      auto input = ranges::subrange(I(range.begin()), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if(input, std::ref(pred), std::ref(proj));
+      assert(result.base() == expected_result);
+    }
+    assert(pred.count() == 2 * expected_complexity);
+    assert(proj.count() == 2 * expected_complexity);
+  }
+  {
+    auto pred = complexity_invocable([](double const x) { return x == 3.0; });
+    auto proj = complexity_invocable(successor);
+    constexpr auto expected_complexity = 3;
+    auto const expected_result = range.begin() + 2;
+    {
+      auto input = ranges::subrange(I(range.begin()), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if(input.begin(), input.end(), std::ref(pred), std::ref(proj));
+      assert(result.base() == expected_result);
+    }
+    {
+      auto input = ranges::subrange(I(range.begin()), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if(input, std::ref(pred), std::ref(proj));
+      assert(result.base() == expected_result);
+    }
+    assert(pred.count() == 2 * expected_complexity);
+    assert(proj.count() == 2 * expected_complexity);
+  }
+  {
+    auto pred = complexity_invocable([](double const x) { return x == 3.7; });
+    auto proj = complexity_invocable(successor);
+    constexpr auto expected_complexity = ranges::ssize(range);
+    auto const expected_result = range.begin() + expected_complexity;
+    {
+      auto input = ranges::subrange(I(range.begin()), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if(input.begin(), input.end(), std::ref(pred), std::ref(proj));
+      assert(result.base() == expected_result);
+    }
+    {
+      auto input = ranges::subrange(I(range.begin()), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if(input, std::ref(pred), std::ref(proj));
+      assert(result.base() == expected_result);
+    }
+    assert(pred.count() == 2 * expected_complexity);
+    assert(proj.count() == 2 * expected_complexity);
+  }
+
+  return true;
+}
+
+int main(int, char**)
+{
+  static_assert(check_find_if<cpp17_input_iterator>());
+  check_find_if<cpp17_input_iterator>();
+
+  static_assert(check_find_if<cpp20_input_iterator>());
+  check_find_if<cpp20_input_iterator>();
+
+  static_assert(check_find_if<forward_iterator>());
+  check_find_if<forward_iterator>();
+
+  static_assert(check_find_if<bidirectional_iterator>());
+  check_find_if<bidirectional_iterator>();
+
+  static_assert(check_find_if<random_access_iterator>());
+  check_find_if<random_access_iterator>();
+
+  static_assert(check_find_if<contiguous_iterator>());
+  check_find_if<contiguous_iterator>();
+
+  auto f = [](auto){ return true; };
+  ASSERT_SAME_TYPE(decltype(ranges::find_if(std::vector<int>(10), f)),
+                   ranges::dangling);
+
+  ASSERT_SAME_TYPE(decltype(ranges::find_if(std::vector<int>(10), f, {})),
+                   ranges::dangling);
+
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find_if/special_function.compile.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// ranges::find_if
+
+#include <algorithm>
+
+#include <array>
+#include <iterator>
+#include <ranges>
+#include <utility>
+
+#include "test_range.h"
+#include "test_standard_function.h"
+
+static_assert(is_function_like<decltype(std::ranges::find_if)>());
+
+namespace ranges = std::ranges;
+
+namespace std::ranges {
+  template<class T>
+  class basic_istream_view {
+    struct iterator;
+  public:
+    iterator begin();
+    default_sentinel_t end() const;
+  };
+} // namespace std::ranges
+
+auto f = [](auto) { return true; };
+
+// The entities defined in the std::ranges namespace in this Clause are not found by argument-dependent
+// name lookup ([basic.lookup.argdep]). When found by unqualified ([basic.lookup.unqual]) name lookup for
+// the postfix-expression in a function call ([expr.call]), they inhibit argument-dependent name lookup.
+template <class T>
+constexpr bool no_unqualified_lookup() {
+  auto identity = ranges::basic_istream_view<T>();
+  static_assert(!requires(T value) { find_if(ranges::begin(identity), ranges::end(identity), f); });
+  static_assert(!requires(T value) { find_if(ranges::begin(identity), ranges::end(identity), f, &T::first); });
+  static_assert(!requires(T value) { find_if(identity, f); });
+  static_assert(!requires(T value) { find_if(identity, f, &T::first); });
+  return true;
+};
+
+static_assert(no_unqualified_lookup<std::pair<int, int>>());
+
+namespace test {
+template <class>
+struct iterator {
+  using value_type = std::pair<int, int>;
+  using difference_type = std::ptrdiff_t;
+  using iterator_category = std::forward_iterator_tag;
+
+  iterator() = default;
+
+  value_type operator*() const;
+  iterator& operator++();
+  iterator operator++(int);
+
+  bool operator==(iterator const&) const = default;
+};
+
+template<class>
+struct range {
+  std::pair<int, int> const* begin() const;
+  std::pair<int, int> const* end() const;
+};
+
+template <class I>
+void find_if(iterator<I>, iterator<I>, auto) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class I>
+void find_if(iterator<I>, iterator<I>, auto, auto) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class R>
+void find_if(R&&, auto) {
+  static_assert(std::same_as<R, R*>);
+}
+
+template <class R>
+void find_if(R&&, auto, auto) {
+  static_assert(std::same_as<R, R*>);
+}
+} // namespace test
+
+// When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a
+// function call ([expr.call]), they inhibit argument-dependent name lookup.
+void adl_inhibition() {
+  using std::ranges::find_if;
+
+  test::iterator<std::pair<int, int>*> x;
+  (void)find_if(x, x, f);
+  (void)find_if(x, x, f, &std::pair<int, int>::first);
+
+  test::range<int*> r;
+  (void)find_if(r, f);
+  (void)find_if(r, f, &std::pair<int, int>::first);
+}

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find_if_not/ranges_find_if_not.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// <algorithm>
+
+// ranges::find_if_not_not
+
+#include <algorithm>
+
+#include <array>
+#include <cassert>
+#include <concepts>
+#include <ranges>
+#include <utility>
+#include <vector>
+
+#include "test_algorithm.h"
+#include "test_macros.h"
+#include "test_iterators.h"
+#include "test_range.h"
+
+namespace ranges = std::ranges;
+
+template<template<class...> class I>
+constexpr bool check_find_if_not()
+{
+
+  auto range = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+  auto successor = [](auto const x) { return x + 1; };
+
+  {
+    auto pred = complexity_invocable([](int const x) { return x != 6; });
+    constexpr auto expected_complexity = 7;
+    auto const expected_result = range.begin() + 6;
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if_not(input.begin(), input.end(), std::ref(pred));
+      assert(result.base().base() == expected_result);
+    }
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if_not(input, std::ref(pred));
+      assert(result.base().base() == expected_result);
+    }
+    assert(pred.count() == 2 * expected_complexity);
+  }
+  {
+    auto pred = complexity_invocable([](double const x) { return x != 3.0; });
+    constexpr auto expected_complexity = 4;
+    auto const expected_result = range.begin() + 3;
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if_not(input.begin(), input.end(), std::ref(pred));
+      assert(result.base().base() == expected_result);
+    }
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if_not(input, std::ref(pred));
+      assert(result.base().base() == expected_result);
+    }
+    assert(pred.count() == 2 * expected_complexity);
+  }
+  {
+    auto pred = complexity_invocable([](double const x) { return x != 3.7; });
+    constexpr auto expected_complexity = ranges::ssize(range);
+    auto const expected_result = range.begin() + expected_complexity;
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if_not(input.begin(), input.end(), std::ref(pred));
+      assert(result.base().base() == expected_result);
+    }
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if_not(input, std::ref(pred));
+      assert(result.base().base() == expected_result);
+    }
+    assert(pred.count() == 2 * expected_complexity);
+  }
+  {
+    auto pred = complexity_invocable([](int const x) { return x != 6; });
+    auto proj = complexity_invocable(successor);
+    constexpr auto expected_complexity = 6;
+    auto const expected_result = range.begin() + 5;
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if_not(input.begin(), input.end(), std::ref(pred), std::ref(proj));
+      assert(result.base().base() == expected_result);
+    }
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if_not(input, std::ref(pred), std::ref(proj));
+      assert(result.base().base() == expected_result);
+    }
+    assert(pred.count() == 2 * expected_complexity);
+    assert(proj.count() == 2 * expected_complexity);
+  }
+  {
+    auto pred = complexity_invocable([](double const x) { return x != 3.0; });
+    auto proj = complexity_invocable(successor);
+    constexpr auto expected_complexity = 3;
+    auto const expected_result = range.begin() + 2;
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if_not(input.begin(), input.end(), std::ref(pred), std::ref(proj));
+      assert(result.base().base() == expected_result);
+    }
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if_not(input, std::ref(pred), std::ref(proj));
+      assert(result.base().base() == expected_result);
+    }
+    assert(pred.count() == 2 * expected_complexity);
+    assert(proj.count() == 2 * expected_complexity);
+  }
+  {
+    auto pred = complexity_invocable([](double const x) { return x != 3.7; });
+    auto proj = complexity_invocable(successor);
+    constexpr auto expected_complexity = ranges::ssize(range);
+    auto const expected_result = range.begin() + expected_complexity;
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if_not(input.begin(), input.end(), std::ref(pred), std::ref(proj));
+      assert(result.base().base() == expected_result);
+    }
+    {
+      auto input = ranges::subrange(complexity_iterator(I(range.begin())), sentinel_wrapper(range.end()));
+      auto const result = ranges::find_if_not(input, std::ref(pred), std::ref(proj));
+      assert(result.base().base() == expected_result);
+    }
+      assert(pred.count() == 2 * expected_complexity);
+      assert(proj.count() == 2 * expected_complexity);
+  }
+
+  return true;
+}
+
+int main(int, char**)
+{
+  static_assert(check_find_if_not<cpp17_input_iterator>());
+  check_find_if_not<cpp17_input_iterator>();
+
+  static_assert(check_find_if_not<cpp20_input_iterator>());
+  check_find_if_not<cpp20_input_iterator>();
+
+  static_assert(check_find_if_not<forward_iterator>());
+  check_find_if_not<forward_iterator>();
+
+  static_assert(check_find_if_not<bidirectional_iterator>());
+  check_find_if_not<bidirectional_iterator>();
+
+  static_assert(check_find_if_not<random_access_iterator>());
+  check_find_if_not<random_access_iterator>();
+
+  static_assert(check_find_if_not<contiguous_iterator>());
+  check_find_if_not<contiguous_iterator>();
+
+  auto f = [](auto){ return true; };
+  ASSERT_SAME_TYPE(decltype(ranges::find_if_not(std::vector<int>(10), f)),
+                   ranges::dangling);
+
+  ASSERT_SAME_TYPE(decltype(ranges::find_if_not(std::vector<int>(10), f, {})),
+                   ranges::dangling);
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges_find_if_not/special_function.compile.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// ranges::find_if_not
+
+#include <algorithm>
+
+#include <array>
+#include <iterator>
+#include <ranges>
+#include <utility>
+
+#include "test_standard_function.h"
+
+static_assert(is_function_like<decltype(std::ranges::find_if_not)>());
+
+namespace ranges = std::ranges;
+
+namespace std::ranges {
+  template<class T>
+  class basic_istream_view {
+    struct iterator;
+  public:
+    iterator begin();
+    default_sentinel_t end() const;
+  };
+} // namespace std::ranges
+
+auto f = [](auto) { return true; };
+
+// The entities defined in the std::ranges namespace in this Clause are not found by argument-dependent
+// name lookup ([basic.lookup.argdep]). When found by unqualified ([basic.lookup.unqual]) name lookup for
+// the postfix-expression in a function call ([expr.call]), they inhibit argument-dependent name lookup.
+template <class T>
+constexpr bool no_unqualified_lookup() {
+  auto identity = ranges::basic_istream_view<T>();
+  static_assert(!requires(T value) { find_if_not(ranges::begin(identity), ranges::end(identity), f); });
+  static_assert(!requires(T value) { find_if_not(ranges::begin(identity), ranges::end(identity), f, &T::first); });
+  static_assert(!requires(T value) { find_if_not(identity, f); });
+  static_assert(!requires(T value) { find_if_not(identity, f, &T::first); });
+  return true;
+};
+
+static_assert(no_unqualified_lookup<std::pair<int, int>>());
+
+namespace test {
+template <class>
+struct iterator {
+  using value_type = std::pair<int, int>;
+  using difference_type = std::ptrdiff_t;
+  using iterator_category = std::forward_iterator_tag;
+
+  iterator() = default;
+
+  value_type operator*() const;
+  iterator& operator++();
+  iterator operator++(int);
+
+  bool operator==(iterator const&) const = default;
+};
+
+template<class>
+struct range {
+  std::pair<int, int> const* begin() const;
+  std::pair<int, int> const* end() const;
+};
+
+template <class I>
+void find_if_not(iterator<I>, iterator<I>, auto) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class I>
+void find_if_not(iterator<I>, iterator<I>, auto, auto) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class R>
+void find_if_not(R&&, auto) {
+  static_assert(std::same_as<R, R*>);
+}
+
+template <class R>
+void find_if_not(R&&, auto, auto) {
+  static_assert(std::same_as<R, R*>);
+}
+} // namespace test
+
+// When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a
+// function call ([expr.call]), they inhibit argument-dependent name lookup.
+void adl_inhibition() {
+  using std::ranges::find_if_not;
+
+  test::iterator<std::pair<int, int>*> x;
+  (void)find_if_not(x, x, f);
+  (void)find_if_not(x, x, f, &std::pair<int, int>::first);
+
+  test::range<int*> r;
+  (void)find_if_not(r, f);
+  (void)find_if_not(r, f, &std::pair<int, int>::first);
+}