[libc++] Implement ranges::find_end, ranges::search{, _n}

[philnik]

• Fix some pre-C++20 code

[philnik]

• run file generation

[philnik]

• Try to fix CI

[var-const]

(Note: this is on my radar but I'll probably won't be able to get to it for a few days)

Is there a reason to combine these two algorithms in a single patch? Even on their own, each one is sizable, and they don't seem to be dependent on each other or even too closely related.

[philnik]

In D124079#3479104, @var-const wrote:

(Note: this is on my radar but I'll probably won't be able to get to it for a few days)

Is there a reason to combine these two algorithms in a single patch? Even on their own, each one is sizable, and they don't seem to be dependent on each other or even too closely related.

Which two do you mean? search and find_end are very similar. I'm even using the random access search implementation in find_end. If you mean search_n and the other two, they are relatively closely related still. Most of the algorithm is almost identical, although they don't share any code in the current implementation. But if you want I can put search_n into it's own PR.

[philnik]

• Fix CI

[philnik]

• Next try

[var-const]

I apologize this review took so long. Generally looks good but there are a few missing parts to address.

libcxx/include/__algorithm/ranges_find_end.h

46

Nit: move?

47

Same optional nit re. moving here.

libcxx/include/__algorithm/ranges_search.h

79

Should this be in an else block of the if constexpr?

[var-const]

libcxx/include/__algorithm/ranges_search.h

66

Question: would it be possible/worthwhile to do a similar optimization for the iterator + sentinel overload? It seems it should be possible to use std::size for the case where the sentinel is the same type as the iterator, or perhaps use subrange (presuming the overhead is negligible and easily optimizable).

69

Hmm, I'd like to double-check this. IIUC, the relevant section is

{i, i + (last2 - first2)}, where i is the first iterator in the range [first1, last1 - (last2 - first2)) such that for every non-negative integer n less than last2 - first2 the condition

bool(invoke(pred, invoke(proj1, *(i + n)), invoke(proj2, *(first2 + n)))) is true.

However, if last2 - first2 is zero, there exists no non-negative integer n less than that. It seems like it would mean that no such iterator i can exist and thus the algorithm should go to the next clause and return {last1, last1}.

libcxx/include/__algorithm/search.h

34

Hide from ABI?

58–64

Question: why is __m1 incremented? It was not incremented in the original.

149–151

Does this need to be in an else branch for this code to be guaranteed to be eliminated? Perhaps you might need to add another if constexpr (sized_sentinel_for<_Sent1, _Iter1> || sized_sentinel_for<_Sent2, _Iter2>) { condition to wrap up the optimizations?

186

Nit: consider moving the iterators.

libcxx/include/__algorithm/search_n.h

76

Can you remove the trailing underscore from the name? (I know it's a preexistent thing)

80

Can you use using?

151

Same comment as in search.h regarding whether this should be an else branch of the if constexpr.

170

Nit: unnecessary blank line.

libcxx/include/__iterator/advance.h

203

Should this work if _Sent is a different type from _Iter? If not, perhaps static assert?

libcxx/include/__iterator/next.h

90 ↗

(On Diff #431172)

Same question re. static_assert here.

libcxx/include/__iterator/reverse_iterator.h

334

I think I'd rather avoid adding these two functions. __make_begin_reverse_iterator seems to exist only for symmetry, but more importantly, the difference between language versions that is being abstracted away by __make_end_reverse_iterator is not specific to reverse iterators. How about something like

template <class _Iter, class _Sent>
decltype(auto) __end_iterator(const _Iter& __first, _Sent& __last) {
#if _LIBCPP_STD_VER > 17
    return ranges::next(__first, __last);
#else
    static_assert(is_same<_Iter, _Sent>::value, "Iterator and Sentinel have to be the same type pre-C++20");
    return __last;
#endif
}

and then use this function when creating the reverse iterators at the call site?

libcxx/include/algorithm

1300

Please update the synopsis.

libcxx/test/std/algorithms/alg.nonmodifying/alg.find.end/ranges.find_end.pass.cpp

10

Missing synopsis.

20

Please check SFINAE as well.

25

Consider a helper function to take care of both the iterator overload and the range overload (can be done in a follow-up if you prefer).

283

Should be find_end.

297

Nit: decltype(auto).

libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search_n.pass.cpp

250

Should be search_n.

[philnik]

• Address comments

libcxx/include/__algorithm/ranges_search.h

66

This was already done in search.h. I've moved it now here, since it would have broken the classic algorithms, as I now know.

69

Yes, the non-negative integers less than zero is the empty set. Normally "all of an empty set" is trivially true.

79

No. The stuff inside the if constexpr just checks if there even can be a match or if it's trivial because the size of __range2 is zero, which means the beginning is always a match.

libcxx/include/__algorithm/search.h

58–64

Yes, that was a bug in the original. The second element of pair was never used anywhere. I don't know why __search ever returned a pair.

149–151

An else branch would be required for the guarantee, but it makes the code a lot more complicated and clang eliminated dead code even at -O0, so I don't se much of an upside.

186

I would avoid moving anything in the classic algorithm parts. It probably doesn't do much and might be a portability pit-fall.

libcxx/include/__algorithm/search_n.h

151

Answer is also the same.

libcxx/include/__iterator/advance.h

203

Doesn't apply anymore because I'm now using _IterOps.

libcxx/include/__iterator/next.h

90 ↗

(On Diff #431172)

Again, doesn't apply anymore because of _IterOps.

libcxx/include/__iterator/reverse_iterator.h

334

Doesn't apply anymore, since we can't use reverse_iterator in classic algos.

libcxx/test/std/algorithms/alg.nonmodifying/alg.find.end/ranges.find_end.pass.cpp

25

I'll do it in a follow-up.

[huixie90]

libcxx/include/__algorithm/ranges_find_end.h

55–56

This looks a bug to me.

In general iterator_traits<_Iter1>::iterator_concept() doesn't exist. (this probably indicates lack of tests in this change)
There is a util in the spec ITER_CONCEPT https://eel.is/c++draft/iterator.concepts.general
but that is not even meant to use for checking the exact concept. It is only meant to be used as part of the real iterator concepts together with all syntactic constraints. Note the default is std::random_access_iterator_tag

In general, for c++20 code, use the real concepts instead of these tags.

https://godbolt.org/z/3b4hGo8h7

[philnik]

• Rebased
• Address comments

[huixie90]

libcxx/include/__algorithm/ranges_search.h

99

why <=? as the size is unsigned, is it just ==0?

libcxx/include/__iterator/advance.h

200

does it need to check _LIBCPP_HAS_NO_INCOMPLETE_RANGES too?

201

What if this line is called on C++20 mode with the classic algorithm/classic iterator?

C++20 sentinel_for requires the sentinel to be semiregular. But C++ 17's iterator are not required to be default constructible.

what happens if you call the classic algorithm with a classic iterator that is not default constructible?

[var-const]

LGTM with one remaining question.

libcxx/include/__algorithm/ranges_search.h

69

Hmm, I might be missing something (I wrote the original comment a while ago), but it seems that if last2 - first2 == 0, the current implementation would return {first1, first1}, whereas it should return {last1, last1} (assuming I'm correct that the "if no such iterator exists" cause applies). first1 isn't necessarily equal to last1 in this case, so returning {first1, first1} isn't equivalent to returning {last1, last1}, even if both are empty sets.

[philnik]

• Address comments

libcxx/include/__algorithm/ranges_search.h

69

I think you are wrong about the condition. IIUC the condition applies for every non-negative integer, because there are no non-negative integers less than zero. It's the same way that ∀x∈∅. ⊥ is true.

libcxx/include/__iterator/advance.h

201

Oops, this shouldn't have been here anymore.

[huixie90]

libcxx/include/__algorithm/ranges_search.h

48

nit: I think it might be better to just use operator- since you've already checked it is sized_sentinel_for. If somehow we forgot to check the sized_sentinel_for concept, operator- would result in a compile time error if the type does not model it, but ranges::distance would result in a runtime linear complexity computation

libcxx/include/__algorithm/ranges_search_n.h

65–70

It would be nice if you can restructure the code so that this block of code can be in an else block of if constexpr, in a way that only one of the two __search_n_random_access_impl and __search_n_forward_impl would be instantiated. IIUC, with this setup, even if the code path calls __search_n_random_access_impl, the __search_n_forward_impl has still need to be instantiated because it is not guarded by if constexpr

[philnik]

• Try to fix CI

libcxx/include/__algorithm/ranges_search.h

48

Not necessarily. You can disable_sized_sentinel_for and are still allowed to have operator-. If we forget the check in that case our algorithm wouldn't just be slow, it would be incorrect.

libcxx/include/__algorithm/ranges_search_n.h

65–70

Doing that would mean that I have to either duplicate the __search_n_forward_impl call or the size check. I don't think the added complexity is justified for that potentially small increase in compilation speed.

[h-vetinari]

libcxx/docs/Status/RangesAlgorithms.csv

26–27

This line can be set to done as well...

[philnik]

• Rebased
• Fix RangesAlgorithms
• Fix CI

[thakis]

This doesn't build over here: http://45.33.8.238/linux/81035/step_4.txt

Do you think that's a problem on my side, or is that a problem in the patch?

[philnik]

In D124079#3647854, @thakis wrote:

This doesn't build over here: http://45.33.8.238/linux/81035/step_4.txt

Do you think that's a problem on my side, or is that a problem in the patch?

That's a merge conflict in libc++. I'll revert for now.

[philnik]

• Try to fix CI

[bgraur]

Hi @philnik,

This commit breaks std::search_n().

Reproducer:

#include <algorithm>
#include <vector>

class A {
 public:
  A(int x, int y) : x_(x), y_(y) {}
  int x() const { return x_; }
  int y() const { return y_; }

 private:
  int x_;
  int y_;
};

bool search(const std::vector<A>& a, int value) {
  return std::search_n(a.begin(), a.end(), 1, value,
                       [](const A& l, int r) { return l.x() == r; }) == a.end();
}

Compile command:

clang  -std=gnu++17  -c /tmp/test.cc  -o /tmp/a.o

That should compile according to https://en.cppreference.com/w/cpp/algorithm/search_n but it no longer does after this commit.
It compiles correctly with the commit before.

[bgraur]

@philnik considering this commit breaks std::search_n() could you please revert?

[huixie90]

libcxx/include/__algorithm/iterator_operations.h

29

question: why do we need another alias for ranges::advance? we could have another overload for classic one with the same name

libcxx/include/__algorithm/search_n.h

165

re @bgraur's bug report. this line should be

static_assert(__is_callable<_BinaryPredicate, decltype(*__first),  const _Tp&>::value, "BinaryPredicate has to be callable");

[ldionne]

Let's not revert since we have a fix in D130124. Thanks a bunch @huixie90 for jumping on this.

[var-const]

@bgraur The fix has been merged: https://reviews.llvm.org/D130124

libcxx/docs/Status/RangesAlgorithms.csv

 Search,min,Nikolas Klauser,`D119589 <https://llvm.org/D119589>`_,✅
 Search,max,Nikolas Klauser,`D122002 <https://llvm.org/D122002>`_,✅
 Search,minmax,Nikolas Klauser,`D120637 <https://llvm.org/D120637>`_,✅
 Search,min_element,Nikolas Klauser,`D117025 <https://llvm.org/D117025>`_,✅
 Search,max_element,Nikolas Klauser,`D117523 <https://llvm.org/D117523>`_,✅
 Search,minmax_element,Nikolas Klauser,`D120637 <https://llvm.org/D120637>`_,✅
 Search,count,Nikolas Klauser,`D121523 <https://llvm.org/D121523>`_,✅
 Search,count_if,Nikolas Klauser,`D121523 <https://llvm.org/D121523>`_,✅
 Search,search,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,Under review
-Search,search_n,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,Under review
-Search,find_end,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,Under review
+Search,search_n,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,✅
+Search,find_end,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,✅
 Read-only,is_partitioned,Nikolas Klauser,`D124440 <https://llvm.org/D124440>`_,✅
 Read-only,is_sorted,Nikolas Klauser,`D125608 <https://llvm.org/D125608>`_,✅
 Read-only,is_sorted_unitl,Nikolas Klauser,`D125608 <https://llvm.org/D125608>`_,✅
 Read-only,includes,Nikolas Klauser,n/a,Not started
 Read-only,is_heap,Nikolas Klauser,n/a,Not started
 Read-only,is_heap_until,Nikolas Klauser,n/a,Not started
 Read-only,clamp,Nikolas Klauser,`D126193 <https://llvm.org/D126193>`_,Under review
 Read-only,is_permutation,Nikolas Klauser,`D127194 <https://llvm.org/D127194>`_,Under review

libcxx/include/CMakeLists.txt

set(files
   __algorithm/ranges_copy_if.h
   __algorithm/ranges_copy_n.h
   __algorithm/ranges_count.h
   __algorithm/ranges_count_if.h
   __algorithm/ranges_equal.h
   __algorithm/ranges_fill.h
   __algorithm/ranges_fill_n.h
   __algorithm/ranges_find.h
+  __algorithm/ranges_find_end.h
   __algorithm/ranges_find_first_of.h
   __algorithm/ranges_find_if.h
   __algorithm/ranges_find_if_not.h
   __algorithm/ranges_for_each.h
   __algorithm/ranges_for_each_n.h
   __algorithm/ranges_is_partitioned.h
   __algorithm/ranges_is_sorted.h
   __algorithm/ranges_is_sorted_until.h
   __algorithm/ranges_lexicographical_compare.h
   __algorithm/ranges_lower_bound.h
   __algorithm/ranges_max.h
   __algorithm/ranges_max_element.h
   __algorithm/ranges_merge.h
   __algorithm/ranges_min.h
   __algorithm/ranges_min_element.h
   __algorithm/ranges_minmax.h
   __algorithm/ranges_minmax_element.h
   __algorithm/ranges_mismatch.h
   __algorithm/ranges_move.h
   __algorithm/ranges_move_backward.h
   __algorithm/ranges_none_of.h
   __algorithm/ranges_replace.h
   __algorithm/ranges_replace_if.h
   __algorithm/ranges_reverse.h
+  __algorithm/ranges_search.h
+  __algorithm/ranges_search_n.h
   __algorithm/ranges_sort.h
   __algorithm/ranges_stable_sort.h
   __algorithm/ranges_swap_ranges.h
   __algorithm/ranges_transform.h
   __algorithm/ranges_upper_bound.h
   __algorithm/remove.h
   __algorithm/remove_copy.h
   __algorithm/remove_copy_if.h

libcxx/include/__algorithm/find_end.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_END_OF_H
 #define _LIBCPP___ALGORITHM_FIND_END_OF_H
 
 #include <__algorithm/comp.h>
+#include <__algorithm/iterator_operations.h>
+#include <__algorithm/search.h>
 #include <__config>
+#include <__functional/identity.h>
+#include <__iterator/advance.h>
 #include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
+#include <__iterator/reverse_iterator.h>
+#include <__utility/pair.h>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
-                                                           _ForwardIterator2 __first2, _ForwardIterator2 __last2,
-                                                           _BinaryPredicate __pred, forward_iterator_tag,
-                                                           forward_iterator_tag) {
+template <
+    class _IterOps,
+    class _Iter1,
+    class _Sent1,
+    class _Iter2,
+    class _Sent2,
+    class _Pred,
+    class _Proj1,
+    class _Proj2>
+_LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_Iter1, _Iter1> __find_end_impl(
+    _Iter1 __first1,
+    _Sent1 __last1,
+    _Iter2 __first2,
+    _Sent2 __last2,
+    _Pred& __pred,
+    _Proj1& __proj1,
+    _Proj2& __proj2,
+    forward_iterator_tag,
   // modeled after search algorithm
-  _ForwardIterator1 __r = __last1; // __last1 is the "default" answer
+  _Iter1 __match_first = _IterOps::next(__first1, __last1); // __last1 is the "default" answer
+  _Iter1 __match_last = __match_first;
   if (__first2 == __last2)
-    return __r;
+    return pair<_Iter1, _Iter1>(__match_last, __match_last);
   while (true) {
     while (true) {
-      if (__first1 == __last1) // if source exhausted return last correct answer
-        return __r;            //    (or __last1 if never found)
-      if (__pred(*__first1, *__first2))
+      if (__first1 == __last1) // if source exhausted return last correct answer (or __last1 if never found)
+        return pair<_Iter1, _Iter1>(__match_first, __match_last);
+      if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))
         break;
       ++__first1;
     }
     // *__first1 matches *__first2, now match elements after here
-    _ForwardIterator1 __m1 = __first1;
-    _ForwardIterator2 __m2 = __first2;
+    _Iter1 __m1 = __first1;
+    _Iter2 __m2 = __first2;
     while (true) {
       if (++__m2 == __last2) { // Pattern exhaused, record answer and search for another one
-        __r = __first1;
+        __match_first = __first1;
+        __match_last = ++__m1;
         ++__first1;
         break;
       }
       if (++__m1 == __last1) // Source exhausted, return last answer
-        return __r;
-      if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first
+        return pair<_Iter1, _Iter1>(__match_first, __match_last);
+       // mismatch, restart with a new __first
+      if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2)))
       {
         ++__first1;
         break;
       } // else there is a match, check next elements
     }
   }
 }
 
-template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator1 __find_end(
-    _BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2,
-    _BidirectionalIterator2 __last2, _BinaryPredicate __pred, bidirectional_iterator_tag, bidirectional_iterator_tag) {
+template <
+    class _IterOps,
+    class _Pred,
+    class _Iter1,
+    class _Sent1,
+    class _Iter2,
+    class _Sent2,
+    class _Proj1,
+    class _Proj2>
+_LIBCPP_CONSTEXPR_AFTER_CXX17 _Iter1 __find_end(
+    _Iter1 __first1,
+    _Sent1 __last1_,
+    _Iter2 __first2,
+    _Sent2 __last2_,
+    _Pred& __pred,
+    _Proj1& __proj1,
+    _Proj2& __proj2,
+    bidirectional_iterator_tag,
+    bidirectional_iterator_tag) {
+  auto __last1 = _IterOps::next(__first1, __last1_);
+  auto __last2 = _IterOps::next(__first2, __last2_);
   // modeled after search algorithm (in reverse)
   if (__first2 == __last2)
     return __last1; // Everything matches an empty sequence
-  _BidirectionalIterator1 __l1 = __last1;
-  _BidirectionalIterator2 __l2 = __last2;
+  _Iter1 __l1 = __last1;
+  _Iter2 __l2 = __last2;
   --__l2;
   while (true) {
     // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks
     while (true) {
       if (__first1 == __l1) // return __last1 if no element matches *__first2
         return __last1;
-      if (__pred(*--__l1, *__l2))
+      if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2)))
         break;
     }
     // *__l1 matches *__l2, now match elements before here
-    _BidirectionalIterator1 __m1 = __l1;
-    _BidirectionalIterator2 __m2 = __l2;
+    _Iter1 __m1 = __l1;
+    _Iter2 __m2 = __l2;
     while (true) {
       if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern)
         return __m1;
       if (__m1 == __first1) // Otherwise if source exhaused, pattern not found
         return __last1;
-      if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1
+
+      // if there is a mismatch, restart with a new __l1
+      if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(__proj2, *--__m2)))
       {
         break;
       } // else there is a match, check next elements
     }
   }
 }
 
-template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
-_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1 __find_end(
-    _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
-    _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag) {
-  typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1;
-  typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2;
+template <
+    class _IterOps,
+    class _Pred,
+    class _Iter1,
+    class _Sent1,
+    class _Iter2,
+    class _Sent2,
+    class _Proj1,
+    class _Proj2>
+_LIBCPP_CONSTEXPR_AFTER_CXX11 _Iter1 __find_end(
+    _Iter1 __first1,
+    _Sent1 __last1_,
+    _Iter2 __first2,
+    _Sent2 __last2_,
+    _Pred& __pred,
+    _Proj1& __proj1,
+    _Proj2& __proj2,
+    random_access_iterator_tag,
+    random_access_iterator_tag) {
+  typedef typename iterator_traits<_Iter1>::difference_type _D1;
+  auto __last1 = _IterOps::next(__first1, __last1_);
+  auto __last2 = _IterOps::next(__first2, __last2_);
   // Take advantage of knowing source and pattern lengths.  Stop short when source is smaller than pattern
-  _D2 __len2 = __last2 - __first2;
+  auto __len2 = __last2 - __first2;
   if (__len2 == 0)
     return __last1;
-  _D1 __len1 = __last1 - __first1;
+  auto __len1 = __last1 - __first1;
   if (__len1 < __len2)
     return __last1;
-  const _RandomAccessIterator1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here
-  _RandomAccessIterator1 __l1 = __last1;
-  _RandomAccessIterator2 __l2 = __last2;
+  const _Iter1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here
+  _Iter1 __l1 = __last1;
+  _Iter2 __l2 = __last2;
   --__l2;
   while (true) {
     while (true) {
       if (__s == __l1)
         return __last1;
-      if (__pred(*--__l1, *__l2))
+      if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2)))
         break;
     }
-    _RandomAccessIterator1 __m1 = __l1;
-    _RandomAccessIterator2 __m2 = __l2;
+    _Iter1 __m1 = __l1;
+    _Iter2 __m2 = __l2;
     while (true) {
       if (__m2 == __first2)
         return __m1;
       // no need to check range on __m1 because __s guarantees we have enough source
-      if (!__pred(*--__m1, *--__m2)) {
+      if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(*--__m2))) {
         break;
       }
     }
   }
 }
 
 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
-_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1
-find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2,
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+_ForwardIterator1 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+                           _ForwardIterator2 __first2, _ForwardIterator2 __last2,
                            _BinaryPredicate __pred) {
-  return _VSTD::__find_end<_BinaryPredicate&>(
-      __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(),
-      typename iterator_traits<_ForwardIterator2>::iterator_category());
+  auto __proj = __identity();
+  return std::__find_end_impl<_StdIterOps>(
+             __first1,
+             __last1,
+             __first2,
+             __last2,
+             __pred,
+             __proj,
+             __proj,
+             typename iterator_traits<_ForwardIterator1>::iterator_category(),
+             typename iterator_traits<_ForwardIterator2>::iterator_category())
+      .first;
 }
 
 template <class _ForwardIterator1, class _ForwardIterator2>
-_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1
-find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) {
-  typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
-  typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
-  return _VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+_ForwardIterator1 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+                           _ForwardIterator2 __first2, _ForwardIterator2 __last2) {
+  using __v1 = typename iterator_traits<_ForwardIterator1>::value_type;
+  using __v2 = typename iterator_traits<_ForwardIterator2>::value_type;
+  return std::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_FIND_END_OF_H

libcxx/include/__algorithm/iterator_operations.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___ALGORIHTM_ITERATOR_OPERATIONS_H
 #define _LIBCPP___ALGORIHTM_ITERATOR_OPERATIONS_H
 
 #include <__config>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 struct _RangesIterOps {
   static constexpr auto advance = ranges::advance;
   static constexpr auto distance = ranges::distance;
+  static constexpr auto next = ranges::next;
 };
 #endif
 
 struct _StdIterOps {
 
   template <class _Iterator, class _Distance>
   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 void advance(_Iterator& __iter, _Distance __count) {
     return std::advance(__iter, __count);
   }
 
   template <class _Iterator>
   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
   typename iterator_traits<_Iterator>::difference_type distance(_Iterator __first, _Iterator __last) {
     return std::distance(__first, __last);
   }
 
+  template <class _Iterator>
+  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
+  _Iterator next(_Iterator, _Iterator __last) {
+    return __last;
+  }
+
 };
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORIHTM_ITERATOR_OPERATIONS_H

libcxx/include/__algorithm/ranges_find_end.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_FIND_END_H
+#define _LIBCPP___ALGORITHM_RANGES_FIND_END_H
+
+#include <__algorithm/find_end.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/indirectly_comparable.h>
+#include <__iterator/iterator_traits.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/subrange.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _Iter>
+consteval auto __get_iterator_concept() {
+  if constexpr (contiguous_iterator<_Iter>)
+    return contiguous_iterator_tag();
+  else if constexpr (random_access_iterator<_Iter>)
+    return random_access_iterator_tag();
+  else if constexpr (bidirectional_iterator<_Iter>)
+    return bidirectional_iterator_tag();
+  else if constexpr (forward_iterator<_Iter>)
+    return forward_iterator_tag();
+  else if constexpr (input_iterator<_Iter>)
+    return input_iterator_tag();
+}
+
+template <class _Iter>
+using __iterator_concept = decltype(__get_iterator_concept<_Iter>());
+
+namespace ranges {
+namespace __find_end {
+struct __fn {
+  template <forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
+            forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
+            class _Pred = ranges::equal_to,
+            class _Proj1 = identity,
+            class _Proj2 = identity>
+    requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  subrange<_Iter1> operator()(_Iter1 __first1, _Sent1 __last1,
+                              _Iter2 __first2, _Sent2 __last2,
+                              _Pred __pred = {},
+                              _Proj1 __proj1 = {},
+                              _Proj2 __proj2 = {}) const {
+    auto __ret = std::__find_end_impl<_RangesIterOps>(
+        __first1,
+        __last1,
+        __first2,
+        __last2,
+        __pred,
+        __proj1,
+        __proj2,
+        __iterator_concept<_Iter1>(),
+        __iterator_concept<_Iter2>());
+    return {__ret.first, __ret.second};
+  }
+
+  template <forward_range _Range1,
+            forward_range _Range2,
+            class _Pred = ranges::equal_to,
+            class _Proj1 = identity,
+            class _Proj2 = identity>
+    requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, _Pred, _Proj1, _Proj2>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  borrowed_subrange_t<_Range1> operator()(_Range1&& __range1,
+                                          _Range2&& __range2,
+                                          _Pred __pred = {},
+                                          _Proj1 __proj1 = {},
+                                          _Proj2 __proj2 = {}) const {
+    auto __ret = std::__find_end_impl<_RangesIterOps>(
+        ranges::begin(__range1),
+        ranges::end(__range1),
+        ranges::begin(__range2),
+        ranges::end(__range2),
+        __pred,
+        __proj1,
+        __proj2,
+        __iterator_concept<iterator_t<_Range1>>(),
+        __iterator_concept<iterator_t<_Range2>>());
+    return {__ret.first, __ret.second};
+  }
+};
+} // namespace __find_end
+
+inline namespace __cpo {
+  inline constexpr auto find_end = __find_end::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_FIND_END_H

libcxx/include/__algorithm/ranges_search.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_SEARCH_H
+#define _LIBCPP___ALGORITHM_RANGES_SEARCH_H
+
+#include <__algorithm/search.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/advance.h>
+#include <__iterator/concepts.h>
+#include <__iterator/distance.h>
+#include <__iterator/indirectly_comparable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/size.h>
+#include <__ranges/subrange.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __search {
+struct __fn {
+  template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Pred, class _Proj1, class _Proj2>
+  _LIBCPP_HIDE_FROM_ABI static constexpr subrange<_Iter1> __ranges_search_impl(
+      _Iter1 __first1,
+      _Sent1 __last1,
+      _Iter2 __first2,
+      _Sent2 __last2,
+      _Pred& __pred,
+      _Proj1& __proj1,
+      _Proj2& __proj2) {
+    if constexpr (sized_sentinel_for<_Sent2, _Iter2>) {
+      auto __size2 = ranges::distance(__first2, __last2);
+      if (__size2 == 0)
+        return {__first1, __first1};
+
+      if constexpr (sized_sentinel_for<_Sent1, _Iter1>) {
+        auto __size1 = ranges::distance(__first1, __last1);
+        if (__size1 < __size2) {
+          ranges::advance(__first1, __last1);
+          return {__first1, __first1};
+        }
+
+        if constexpr (random_access_iterator<_Iter1> && random_access_iterator<_Iter2>) {
+          auto __ret = std::__search_random_access_impl(
+              __first1, __last1, __first2, __last2, __pred, __proj1, __proj2, __size1, __size2);
+          return {__ret.first, __ret.second};
+        }
+      }
+    }
+
+    auto __ret = std::__search_forward_impl(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2);
+    return {__ret.first, __ret.second};
+  }
+
+  template <forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
+            forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
+            class _Pred = ranges::equal_to,
+            class _Proj1 = identity,
+            class _Proj2 = identity>
+    requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  subrange<_Iter1> operator()(_Iter1 __first1, _Sent1 __last1,
+                              _Iter2 __first2, _Sent2 __last2,
+                              _Pred __pred = {},
+                              _Proj1 __proj1 = {},
+                              _Proj2 __proj2 = {}) const {
+    return __ranges_search_impl(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2);
+  }
+
+  template <forward_range _Range1,
+            forward_range _Range2,
+            class _Pred = ranges::equal_to,
+            class _Proj1 = identity,
+            class _Proj2 = identity>
+    requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, _Pred, _Proj1, _Proj2>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  borrowed_subrange_t<_Range1> operator()(_Range1&& __range1,
+                                          _Range2&& __range2,
+                                          _Pred __pred = {},
+                                          _Proj1 __proj1 = {},
+                                          _Proj2 __proj2 = {}) const {
+    auto __first1 = ranges::begin(__range1);
+    if constexpr (sized_range<_Range2>) {
+      auto __size2 = ranges::size(__range2);
+      if (__size2 <= 0)
+        return {__first1, __first1};
+      if constexpr (sized_range<_Range1>) {
+        auto __size1 = ranges::size(__range1);
+        if (__size1 < __size2) {
+          ranges::advance(__first1, ranges::end(__range1));
+          return {__first1, __first1};
+        }
+      }
+    }
+
+    return __ranges_search_impl(
+        ranges::begin(__range1),
+        ranges::end(__range1),
+        ranges::begin(__range2),
+        ranges::end(__range2),
+        __pred,
+        __proj1,
+        __proj2);
+  }
+
+};
+} // namespace __search
+
+inline namespace __cpo {
+  inline constexpr auto search = __search::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_SEARCH_H

libcxx/include/__algorithm/ranges_search_n.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_SEARCH_N_H
+#define _LIBCPP___ALGORITHM_RANGES_SEARCH_N_H
+
+#include <__algorithm/iterator_operations.h>
+#include <__algorithm/search_n.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/advance.h>
+#include <__iterator/concepts.h>
+#include <__iterator/incrementable_traits.h>
+#include <__iterator/indirectly_comparable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/size.h>
+#include <__ranges/subrange.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __search_n {
+struct __fn {
+
+  template <class _Iter1, class _Sent1, class _SizeT, class _Type, class _Pred, class _Proj>
+  _LIBCPP_HIDE_FROM_ABI static constexpr subrange<_Iter1> __ranges_search_n_impl(
+      _Iter1 __first, _Sent1 __last, _SizeT __count, const _Type& __value, _Pred& __pred, _Proj& __proj) {
+    if (__count == 0)
+      return {__first, __first};
+
+    if constexpr (sized_sentinel_for<_Sent1, _Iter1>) {
+      auto __size = ranges::distance(__first, __last);
+      if (__size < __count) {
+        ranges::advance(__first, __last);
+        return {__first, __first};
+      }
+
+      if constexpr (random_access_iterator<_Iter1>) {
+        auto __ret = __search_n_random_access_impl(__first, __last,
+                                                   __count,
+                                                   __value,
+                                                   __pred,
+                                                   __proj,
+                                                   __size);
+        return {std::move(__ret.first), std::move(__ret.second)};
+      }
+    }
+
+    auto __ret = std::__search_n_forward_impl(__first, __last,
+                                              __count,
+                                              __value,
+                                              __pred,
+                                              __proj);
+    return {std::move(__ret.first), std::move(__ret.second)};
+  }
+
+  template <forward_iterator _Iter, sentinel_for<_Iter> _Sent,
+            class _Type,
+            class _Pred = ranges::equal_to,
+            class _Proj = identity>
+    requires indirectly_comparable<_Iter, const _Type*, _Pred, _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  subrange<_Iter> operator()(_Iter __first, _Sent __last,
+                             iter_difference_t<_Iter> __count,
+                             const _Type& __value,
+                             _Pred __pred = {},
+                             _Proj __proj = _Proj{}) const {
+    return __ranges_search_n_impl(__first, __last, __count, __value, __pred, __proj);
+  }
+
+  template <forward_range _Range, class _Type, class _Pred = ranges::equal_to, class _Proj = identity>
+    requires indirectly_comparable<iterator_t<_Range>, const _Type*, _Pred, _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  borrowed_subrange_t<_Range> operator()(_Range&& __range,
+                                         range_difference_t<_Range> __count,
+                                         const _Type& __value,
+                                         _Pred __pred = {},
+                                         _Proj __proj = {}) const {
+    auto __first = ranges::begin(__range);
+    if (__count <= 0)
+      return {__first, __first};
+    if constexpr (sized_range<_Range>) {
+      auto __size1 = ranges::size(__range);
+      if (__size1 < static_cast<range_size_t<_Range>>(__count)) {
+        ranges::advance(__first, ranges::end(__range));
+        return {__first, __first};
+      }
+    }
+
+    return __ranges_search_n_impl(ranges::begin(__range), ranges::end(__range), __count, __value, __pred, __proj);
+  }
+};
+} // namespace __search_n
+
+inline namespace __cpo {
+  inline constexpr auto search_n = __search_n::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_SEARCH_N_H

libcxx/include/__algorithm/search.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_SEARCH_H
 #define _LIBCPP___ALGORITHM_SEARCH_H
 
 #include <__algorithm/comp.h>
 #include <__config>
+#include <__functional/identity.h>
+#include <__iterator/advance.h>
+#include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
+#include <__type_traits/is_callable.h>
 #include <__utility/pair.h>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
-pair<_ForwardIterator1, _ForwardIterator1>
-    _LIBCPP_CONSTEXPR_AFTER_CXX11 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
-                                           _ForwardIterator2 __first2, _ForwardIterator2 __last2,
-                                           _BinaryPredicate __pred, forward_iterator_tag, forward_iterator_tag) {
+template <class _Iter1, class _Sent1,
+          class _Iter2, class _Sent2,
+          class _Pred,
+          class _Proj1,
+          class _Proj2>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+pair<_Iter1, _Iter1> __search_forward_impl(_Iter1 __first1, _Sent1 __last1,
+                                           _Iter2 __first2, _Sent2 __last2,
+                                           _Pred& __pred,
+                                           _Proj1& __proj1,
+                                           _Proj2& __proj2) {
   if (__first2 == __last2)
-    return _VSTD::make_pair(__first1, __first1); // Everything matches an empty sequence
+    return std::make_pair(__first1, __first1); // Everything matches an empty sequence
   while (true) {
     // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks
     while (true) {
-      if (__first1 == __last1) // return __last1 if no element matches *__first2
-        return _VSTD::make_pair(__last1, __last1);
-      if (__pred(*__first1, *__first2))
+      if (__first1 == __last1) { // return __last1 if no element matches *__first2
+        std::__advance_to(__first1, __last1);
+        return std::make_pair(__first1, __first1);
+      }
+      if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))
         break;
       ++__first1;
     }
     // *__first1 matches *__first2, now match elements after here
-    _ForwardIterator1 __m1 = __first1;
-    _ForwardIterator2 __m2 = __first2;
+    _Iter1 __m1 = __first1;
+    _Iter2 __m2 = __first2;
     while (true) {
       if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern)
-        return _VSTD::make_pair(__first1, __m1);
-      if (++__m1 == __last1) // Otherwise if source exhaused, pattern not found
-        return _VSTD::make_pair(__last1, __last1);
-      if (!__pred(*__m1, *__m2)) // if there is a mismatch, restart with a new __first1
+        return std::make_pair(__first1, ++__m1);
+      if (++__m1 == __last1) { // Otherwise if source exhaused, pattern not found
+        return std::make_pair(__m1, __m1);
+      }
+
+      // if there is a mismatch, restart with a new __first1
+      if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2)))
       {
         ++__first1;
         break;
       } // else there is a match, check next elements
     }
   }
 }
 
-template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
-_LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_RandomAccessIterator1, _RandomAccessIterator1>
-__search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
-         _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag,
-         random_access_iterator_tag) {
-  typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1;
-  typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2;
-  // Take advantage of knowing source and pattern lengths.  Stop short when source is smaller than pattern
-  const _D2 __len2 = __last2 - __first2;
-  if (__len2 == 0)
-    return _VSTD::make_pair(__first1, __first1);
-  const _D1 __len1 = __last1 - __first1;
-  if (__len1 < __len2)
-    return _VSTD::make_pair(__last1, __last1);
-  const _RandomAccessIterator1 __s = __last1 - _D1(__len2 - 1); // Start of pattern match can't go beyond here
+template <class _Iter1, class _Sent1,
+          class _Iter2, class _Sent2,
+          class _Pred,
+          class _Proj1,
+          class _Proj2,
+          class _DiffT1,
+          class _DiffT2>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+pair<_Iter1, _Iter1> __search_random_access_impl(_Iter1 __first1, _Sent1 __last1,
+                                                 _Iter2 __first2, _Sent2 __last2,
+                                                 _Pred& __pred,
+                                                 _Proj1& __proj1,
+                                                 _Proj2& __proj2,
+                                                 _DiffT1 __size1,
+                                                 _DiffT2 __size2) {
+  const _Iter1 __s = __first1 + __size1 - _DiffT1(__size2 - 1); // Start of pattern match can't go beyond here
 
   while (true) {
     while (true) {
-      if (__first1 == __s)
-        return _VSTD::make_pair(__last1, __last1);
-      if (__pred(*__first1, *__first2))
+      if (__first1 == __s) {
+        std::__advance_to(__first1, __last1);
+        return std::make_pair(__first1, __first1);
+      }
+      if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))
         break;
       ++__first1;
     }
 
-    _RandomAccessIterator1 __m1 = __first1;
-    _RandomAccessIterator2 __m2 = __first2;
+    _Iter1 __m1 = __first1;
+    _Iter2 __m2 = __first2;
     while (true) {
       if (++__m2 == __last2)
-        return _VSTD::make_pair(__first1, __first1 + _D1(__len2));
+        return std::make_pair(__first1, __first1 + _DiffT1(__size2));
       ++__m1; // no need to check range on __m1 because __s guarantees we have enough source
-      if (!__pred(*__m1, *__m2)) {
+      if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) {
         ++__first1;
         break;
       }
     }
   }
 }
 
+template <class _Iter1, class _Sent1,
+          class _Iter2, class _Sent2,
+          class _Pred,
+          class _Proj1,
+          class _Proj2>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+pair<_Iter1, _Iter1> __search_impl(_Iter1 __first1, _Sent1 __last1,
+                                   _Iter2 __first2, _Sent2 __last2,
+                                   _Pred& __pred,
+                                   _Proj1& __proj1,
+                                   _Proj2& __proj2,
+                                   __enable_if_t<__is_cpp17_random_access_iterator<_Iter1>::value
+                                              && __is_cpp17_random_access_iterator<_Iter2>::value>* = nullptr) {
+
+  auto __size2 = __last2 - __first2;
+  if (__size2 == 0)
+    return std::make_pair(__first1, __first1);
+
+  auto __size1 = __last1 - __first1;
+  if (__size1 < __size2) {
+    return std::make_pair(__last1, __last1);
+  }
+
+  return std::__search_random_access_impl(__first1, __last1,
+                                          __first2, __last2,
+                                          __pred,
+                                          __proj1,
+                                          __proj2,
+                                          __size1,
+                                          __size2);
+}
+
+template <class _Iter1, class _Sent1,
+          class _Iter2, class _Sent2,
+          class _Pred,
+          class _Proj1,
+          class _Proj2>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+pair<_Iter1, _Iter1> __search_impl(_Iter1 __first1, _Sent1 __last1,
+                                   _Iter2 __first2, _Sent2 __last2,
+                                   _Pred& __pred,
+                                   _Proj1& __proj1,
+                                   _Proj2& __proj2,
+                                   __enable_if_t<__is_cpp17_forward_iterator<_Iter1>::value
+                                              && __is_cpp17_forward_iterator<_Iter2>::value
+                                              && !(__is_cpp17_random_access_iterator<_Iter1>::value
+                                                && __is_cpp17_random_access_iterator<_Iter2>::value)>* = nullptr) {
+  return std::__search_forward_impl(__first1, __last1,
+                                    __first2, __last2,
+                                    __pred,
+                                    __proj1,
+                                    __proj2);
+}
+
 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
-_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1
-search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2,
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+_ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+                         _ForwardIterator2 __first2, _ForwardIterator2 __last2,
                          _BinaryPredicate __pred) {
-  return _VSTD::__search<_BinaryPredicate&>(
-             __first1, __last1, __first2, __last2, __pred,
-             typename iterator_traits<_ForwardIterator1>::iterator_category(),
-             typename iterator_traits<_ForwardIterator2>::iterator_category()).first;
+  static_assert(__is_callable<_BinaryPredicate, decltype(*__first1), decltype(*__first2)>::value,
+                "BinaryPredicate has to be callable");
+  auto __proj = __identity();
+  return std::__search_impl(__first1, __last1, __first2, __last2, __pred, __proj, __proj).first;
 }
 
 template <class _ForwardIterator1, class _ForwardIterator2>
-_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1
-search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) {
-  typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
-  typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
-  return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+_ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+                         _ForwardIterator2 __first2, _ForwardIterator2 __last2) {
+  using __v1 = typename iterator_traits<_ForwardIterator1>::value_type;
+  using __v2 = typename iterator_traits<_ForwardIterator2>::value_type;
+  return std::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
 }
 
 #if _LIBCPP_STD_VER > 14
 template <class _ForwardIterator, class _Searcher>
 _LIBCPP_NODISCARD_EXT _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
 search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher& __s) {
   return __s(__f, __l).first;
 }
 
 #endif
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SEARCH_H

libcxx/include/__algorithm/search_n.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_SEARCH_N_H
 #define _LIBCPP___ALGORITHM_SEARCH_N_H
 
 #include <__algorithm/comp.h>
 #include <__config>
+#include <__functional/identity.h>
+#include <__iterator/advance.h>
+#include <__iterator/concepts.h>
+#include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
+#include <__ranges/concepts.h>
+#include <__utility/pair.h>
 #include <type_traits>  // __convert_to_integral
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator __search_n(_ForwardIterator __first, _ForwardIterator __last,
-                                                          _Size __count, const _Tp& __value_, _BinaryPredicate __pred,
-                                                          forward_iterator_tag) {
+template <class _Pred, class _Iter, class _Sent, class _SizeT, class _Type, class _Proj>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+pair<_Iter, _Iter> __search_n_forward_impl(_Iter __first, _Sent __last,
+                                           _SizeT __count,
+                                           const _Type& __value,
+                                           _Pred& __pred,
+                                           _Proj& __proj) {
   if (__count <= 0)
-    return __first;
+    return std::make_pair(__first, __first);
   while (true) {
-    // Find first element in sequence that matchs __value_, with a mininum of loop checks
+    // Find first element in sequence that matchs __value, with a mininum of loop checks
     while (true) {
-      if (__first == __last) // return __last if no element matches __value_
-        return __last;
-      if (__pred(*__first, __value_))
+      if (__first == __last) { // return __last if no element matches __value
+        std::__advance_to(__first, __last);
+        return std::make_pair(__first, __first);
+      }
+      if (std::__invoke(__pred, std::__invoke(__proj, *__first), __value))
         break;
       ++__first;
     }
-    // *__first matches __value_, now match elements after here
-    _ForwardIterator __m = __first;
-    _Size __c(0);
+    // *__first matches __value, now match elements after here
+    _Iter __m = __first;
+    _SizeT __c(0);
     while (true) {
       if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
-        return __first;
-      if (++__m == __last) // Otherwise if source exhaused, pattern not found
-        return __last;
-      if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
+        return std::make_pair(__first, ++__m);
+      if (++__m == __last) { // Otherwise if source exhaused, pattern not found
+        std::__advance_to(__first, __last);
+        return std::make_pair(__first, __first);
+      }
+
+      // if there is a mismatch, restart with a new __first
+      if (!std::__invoke(__pred, std::__invoke(__proj, *__m), __value))
       {
         __first = __m;
         ++__first;
         break;
       } // else there is a match, check next elements
     }
   }
 }
 
-template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator __search_n(_RandomAccessIterator __first,
-                                                               _RandomAccessIterator __last, _Size __count,
-                                                               const _Tp& __value_, _BinaryPredicate __pred,
-                                                               random_access_iterator_tag) {
-  typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
+template <class _Pred, class _Iter, class _Sent, class _SizeT, class _Type, class _Proj, class _DiffT>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+std::pair<_Iter, _Iter> __search_n_random_access_impl(_Iter __first, _Sent __last,
+                                                      _SizeT __count,
+                                                      const _Type& __value,
+                                                      _Pred& __pred,
+                                                      _Proj& __proj,
+                                                      _DiffT __size1) {
+  using difference_type = typename iterator_traits<_Iter>::difference_type;
   if (__count <= 0)
-    return __first;
-  _Size __len = static_cast<_Size>(__last - __first);
-  if (__len < __count)
-    return __last;
-  const _RandomAccessIterator __s = __last - difference_type(__count - 1); // Start of pattern match can't go beyond here
-  while (true) {
-    // Find first element in sequence that matchs __value_, with a mininum of loop checks
-    while (true) {
-      if (__first >= __s) // return __last if no element matches __value_
-        return __last;
-      if (__pred(*__first, __value_))
+    return std::make_pair(__first, __first);
+  if (__size1 < __count) {
+    std::__advance_to(__first, __last);
+    return std::make_pair(__first, __first);
+  }
+
+  const auto __s = __first + __size1 - difference_type(__count - 1); // Start of pattern match can't go beyond here
+    // Find first element in sequence that matchs __value, with a mininum of loop checks
+    while (true) {
+      if (__first >= __s) { // return __last if no element matches __value
+        std::__advance_to(__first, __last);
+        return std::make_pair(__first, __first);
+      }
+      if (std::__invoke(__pred, std::__invoke(__proj, *__first), __value))
         break;
       ++__first;
     }
     // *__first matches __value_, now match elements after here
-    _RandomAccessIterator __m = __first;
-    _Size __c(0);
+    auto __m = __first;
+    _SizeT __c(0);
     while (true) {
       if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
-        return __first;
-      ++__m;                       // no need to check range on __m because __s guarantees we have enough source
-      if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
+        return std::make_pair(__first, __first + _DiffT(__count));
+      ++__m; // no need to check range on __m because __s guarantees we have enough source
+
+      // if there is a mismatch, restart with a new __first
+      if (!std::__invoke(__pred, std::__invoke(__proj, *__m), __value))
       {
         __first = __m;
         ++__first;
         break;
       } // else there is a match, check next elements
     }
   }
 }
 
+template <class _Iter, class _Sent,
+          class _DiffT,
+          class _Type,
+          class _Pred,
+          class _Proj>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+pair<_Iter, _Iter> __search_n_impl(_Iter __first, _Sent __last,
+                                   _DiffT __count,
+                                   const _Type& __value,
+                                   _Pred& __pred,
+                                   _Proj& __proj,
+                                   __enable_if_t<__is_cpp17_random_access_iterator<_Iter>::value>* = nullptr) {
+  return std::__search_n_random_access_impl(__first, __last,
+                                            __count,
+                                            __value,
+                                            __pred,
+                                            __proj,
+                                            __last - __first);
+}
+
+template <class _Iter1, class _Sent1,
+          class _DiffT,
+          class _Type,
+          class _Pred,
+          class _Proj>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+pair<_Iter1, _Iter1> __search_n_impl(_Iter1 __first, _Sent1 __last,
+                                     _DiffT __count,
+                                     const _Type& __value,
+                                     _Pred& __pred,
+                                     _Proj& __proj,
+                                     __enable_if_t<__is_cpp17_forward_iterator<_Iter1>::value
+                                               && !__is_cpp17_random_access_iterator<_Iter1>::value>* = nullptr) {
+  return std::__search_n_forward_impl(__first, __last,
+                                      __count,
+                                      __value,
+                                      __pred,
+                                      __proj);
+}
+
 template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
-_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator search_n(
-    _ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_, _BinaryPredicate __pred) {
-  return _VSTD::__search_n<_BinaryPredicate&>(
-      __first, __last, _VSTD::__convert_to_integral(__count), __value_, __pred,
-      typename iterator_traits<_ForwardIterator>::iterator_category());
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+_ForwardIterator search_n(_ForwardIterator __first, _ForwardIterator __last,
+                          _Size __count,
+                          const _Tp& __value_,
+                          _BinaryPredicate __pred) {
+  static_assert(__is_callable<_BinaryPredicate, decltype(*__first), decltype(*__last)>::value,
+                "BinaryPredicate has to be callable");
+  auto __proj = __identity();
+  return std::__search_n_impl(__first, __last, std::__convert_to_integral(__count), __value_, __pred, __proj).first;
 }
 
 template <class _ForwardIterator, class _Size, class _Tp>
-_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
-search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_) {
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+_ForwardIterator search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_) {
   typedef typename iterator_traits<_ForwardIterator>::value_type __v;
-  return _VSTD::search_n(__first, __last, _VSTD::__convert_to_integral(__count), __value_, __equal_to<__v, _Tp>());
+  return std::search_n(__first, __last, std::__convert_to_integral(__count), __value_, __equal_to<__v, _Tp>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SEARCH_N_H

libcxx/include/__functional/default_searcher.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___FUNCTIONAL_DEFAULT_SEARCHER_H
 #define _LIBCPP___FUNCTIONAL_DEFAULT_SEARCHER_H
 
 #include <__algorithm/search.h>
 #include <__config>
+#include <__functional/identity.h>
 #include <__functional/operations.h>
 #include <__iterator/iterator_traits.h>
 #include <__utility/pair.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
default_searcher(_ForwardIterator __f, _ForwardIterator __l,
                        _BinaryPredicate __p = _BinaryPredicate())
         : __first_(__f), __last_(__l), __pred_(__p) {}
 
     template <typename _ForwardIterator2>
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
     pair<_ForwardIterator2, _ForwardIterator2>
     operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const
     {
-        return _VSTD::__search(__f, __l, __first_, __last_, __pred_,
-            typename iterator_traits<_ForwardIterator>::iterator_category(),
-            typename iterator_traits<_ForwardIterator2>::iterator_category());
+        auto __proj = __identity();
+        return std::__search_impl(__f, __l, __first_, __last_, __pred_, __proj, __proj);
     }
 
 private:
     _ForwardIterator __first_;
     _ForwardIterator __last_;
     _BinaryPredicate __pred_;
-    };
 
 #endif // _LIBCPP_STD_VER > 14
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___FUNCTIONAL_DEFAULT_SEARCHER_H

libcxx/include/__iterator/advance.h

 
 inline namespace __cpo {
   inline constexpr auto advance = __advance::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
+template <class _Iter, class _Sent>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+void __advance_to(_Iter& __iter, _Sent& __to) {
+#if _LIBCPP_STD_VER > 17
+  ranges::advance(__iter, __to);
+#else
+  __iter = std::move(__to);
+#endif
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ITERATOR_ADVANCE_H

libcxx/include/__iterator/iterator_traits.h

: public integral_constant<bool,
         !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value> {};
 
 template <class _Tp>
 struct __is_exactly_cpp17_forward_iterator
     : public integral_constant<bool,
          __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value &&
         !__has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value> {};
 
+template <class _Tp>
+struct __is_exactly_cpp17_bidirectional_iterator
+    : public integral_constant<bool,
+         __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value &&
+        !__has_iterator_category_convertible_to<_Tp, random_access_iterator_tag>::value> {};
+
 template<class _InputIterator>
 using __iter_value_type = typename iterator_traits<_InputIterator>::value_type;
 
 template<class _InputIterator>
 using __iter_key_type = typename remove_const<typename iterator_traits<_InputIterator>::value_type::first_type>::type;
 
 template<class _InputIterator>
 using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type;

libcxx/include/__iterator/reverse_iterator.h

 #ifndef _LIBCPP___ITERATOR_REVERSE_ITERATOR_H
 #define _LIBCPP___ITERATOR_REVERSE_ITERATOR_H
 
 #include <__algorithm/unwrap_iter.h>
 #include <__compare/compare_three_way_result.h>
 #include <__compare/three_way_comparable.h>
 #include <__concepts/convertible_to.h>
 #include <__config>
+#include <__iterator/advance.h>
 #include <__iterator/concepts.h>
 #include <__iterator/incrementable_traits.h>
 #include <__iterator/iter_move.h>
 #include <__iterator/iter_swap.h>
 #include <__iterator/iterator.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/prev.h>
 #include <__iterator/readable_traits.h>

 template <class _Iter>
 using _ReverseWrapper = reverse_iterator<reverse_iterator<_Iter> >;
 
 template <class _Iter, bool __b>
 struct __unwrap_iter_impl<_ReverseWrapper<_Iter>, __b> {
   static _LIBCPP_CONSTEXPR decltype(std::__unwrap_iter(std::declval<_Iter>()))
   __apply(_ReverseWrapper<_Iter> __i) _NOEXCEPT {
     return std::__unwrap_iter(__i.base().base());
   }
 };
 
 template <class _OrigIter, class _UnwrappedIter>
 struct __rewrap_iter_impl<_ReverseWrapper<_OrigIter>, _UnwrappedIter> {
   template <class _Iter>
   struct _ReverseWrapperCount {
     static _LIBCPP_CONSTEXPR const size_t value = 1;
   };

libcxx/include/__string/char_traits.h

 __str_rfind(const _CharT *__p, _SizeT __sz,
         const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
 {
     __pos = _VSTD::min(__pos, __sz);
     if (__n < __sz - __pos)
         __pos += __n;
     else
         __pos = __sz;
-    const _CharT* __r = _VSTD::__find_end(
-                  __p, __p + __pos, __s, __s + __n, _Traits::eq,
-                        random_access_iterator_tag(), random_access_iterator_tag());
+    const _CharT* __r = std::find_end(__p, __p + __pos, __s, __s + __n, _Traits::eq);
     if (__n > 0 && __r == __p + __pos)
         return __npos;
     return static_cast<_SizeT>(__r - __p);
 }
 
 // __str_find_first_of
 template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
 inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY

libcxx/include/algorithm

template<input_range R1, input_range R2, class Pred = ranges::equal_to,
 
   template<input_range R1, input_range R2, weakly_incrementable O, class Comp = ranges::less,
            class Proj1 = identity, class Proj2 = identity>
     requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
     constexpr merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
       merge(R1&& r1, R2&& r2, O result,
             Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                                    // since C++20
 
+  template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
+           sentinel_for<I2> S2, class Pred = ranges::equal_to,
+           class Proj1 = identity, class Proj2 = identity>
+    requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
+    constexpr subrange<I1>
+      ranges::search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
+                     Proj1 proj1 = {}, Proj2 proj2 = {});                                           // since C++20
+
+  template<forward_range R1, forward_range R2, class Pred = ranges::equal_to,
+           class Proj1 = identity, class Proj2 = identity>
+    requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
+    constexpr borrowed_subrange_t<R1>
+      ranges::search(R1&& r1, R2&& r2, Pred pred = {},
+                     Proj1 proj1 = {}, Proj2 proj2 = {});                                           // since C++20
+
+  template<forward_iterator I, sentinel_for<I> S, class T,
+           class Pred = ranges::equal_to, class Proj = identity>
+    requires indirectly_comparable<I, const T*, Pred, Proj>
+    constexpr subrange<I>
+      ranges::search_n(I first, S last, iter_difference_t<I> count,
+                       const T& value, Pred pred = {}, Proj proj = {});                             // since C++20
+
+  template<forward_range R, class T, class Pred = ranges::equal_to,
+           class Proj = identity>
+    requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj>
+    constexpr borrowed_subrange_t<R>
+      ranges::search_n(R&& r, range_difference_t<R> count,
+                       const T& value, Pred pred = {}, Proj proj = {});                             // since C++20
+
+  template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2,
+           class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+    requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
+    constexpr subrange<I1>
+      ranges::find_end(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
+                       Proj1 proj1 = {}, Proj2 proj2 = {});                                         // since C++20
+
+  template<forward_range R1, forward_range R2,
+           class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+    requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
+    constexpr borrowed_subrange_t<R1>
+      ranges::find_end(R1&& r1, R2&& r2, Pred pred = {},
+                       Proj1 proj1 = {}, Proj2 proj2 = {});                                         // since C++20
+
 }
 
     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
     any_of(InputIterator first, InputIterator last, Predicate pred);

 #include <__algorithm/ranges_copy_if.h>
 #include <__algorithm/ranges_copy_n.h>
 #include <__algorithm/ranges_count.h>
 #include <__algorithm/ranges_count_if.h>
 #include <__algorithm/ranges_equal.h>
 #include <__algorithm/ranges_fill.h>
 #include <__algorithm/ranges_fill_n.h>
 #include <__algorithm/ranges_find.h>
+#include <__algorithm/ranges_find_end.h>
 #include <__algorithm/ranges_find_first_of.h>
 #include <__algorithm/ranges_find_if.h>
 #include <__algorithm/ranges_find_if_not.h>
 #include <__algorithm/ranges_for_each.h>
 #include <__algorithm/ranges_for_each_n.h>
 #include <__algorithm/ranges_is_partitioned.h>
 #include <__algorithm/ranges_is_sorted.h>
 #include <__algorithm/ranges_is_sorted_until.h>
 #include <__algorithm/ranges_lexicographical_compare.h>
 #include <__algorithm/ranges_lower_bound.h>
 #include <__algorithm/ranges_max.h>
 #include <__algorithm/ranges_max_element.h>
 #include <__algorithm/ranges_merge.h>
 #include <__algorithm/ranges_min.h>
 #include <__algorithm/ranges_min_element.h>
 #include <__algorithm/ranges_minmax.h>
 #include <__algorithm/ranges_minmax_element.h>
 #include <__algorithm/ranges_mismatch.h>
 #include <__algorithm/ranges_move.h>
 #include <__algorithm/ranges_move_backward.h>
 #include <__algorithm/ranges_none_of.h>
 #include <__algorithm/ranges_replace.h>
 #include <__algorithm/ranges_replace_if.h>
 #include <__algorithm/ranges_reverse.h>
+#include <__algorithm/ranges_search.h>
+#include <__algorithm/ranges_search_n.h>
 #include <__algorithm/ranges_sort.h>
 #include <__algorithm/ranges_stable_sort.h>
 #include <__algorithm/ranges_swap_ranges.h>
 #include <__algorithm/ranges_transform.h>
 #include <__algorithm/ranges_upper_bound.h>
 #include <__algorithm/remove.h>
 #include <__algorithm/remove_copy.h>
 #include <__algorithm/remove_copy_if.h>

libcxx/include/experimental/functional

inline namespace fundamentals_v1 {
   } // namespace experimental
 
 } // namespace std
 
 */
 
 #include <__assert> // all public C++ headers provide the assertion handler
 #include <__debug>
+#include <__functional/identity.h>
 #include <__memory/uses_allocator.h>
 #include <array>
 #include <experimental/__config>
 #include <functional>
 #include <type_traits>
 #include <unordered_map>
 #include <vector>
 
default_searcher(_ForwardIterator __f, _ForwardIterator __l,
                        _BinaryPredicate __p = _BinaryPredicate())
         : __first_(__f), __last_(__l), __pred_(__p) {}
 
     template <typename _ForwardIterator2>
     _LIBCPP_INLINE_VISIBILITY
     pair<_ForwardIterator2, _ForwardIterator2>
     operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const
     {
-        return _VSTD::__search(__f, __l, __first_, __last_, __pred_,
-            typename iterator_traits<_ForwardIterator>::iterator_category(),
-            typename iterator_traits<_ForwardIterator2>::iterator_category());
+        auto __proj = __identity();
+        return std::__search_impl(__f, __l, __first_, __last_, __pred_, __proj, __proj);
     }
 
 private:
     _ForwardIterator __first_;
     _ForwardIterator __last_;
     _BinaryPredicate __pred_;
     };
 

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp

 {
     void *a[10] = {};
     void *b[10] = {};
     void *half[5] = {};
     void **first = a;
     void **mid = a+5;
     void **last = a+10;
     void **first2 = b;
-    //void **mid2 = b+5;
+    void **mid2 = b+5;
     void **last2 = b+10;
     void *value = nullptr;
     int count = 1;
 
     int copies = 0;
     (void)std::ranges::adjacent_find(first, last, Equal(&copies)); assert(copies == 0);
     (void)std::ranges::adjacent_find(a, Equal(&copies)); assert(copies == 0);
     (void)std::ranges::all_of(first, last, UnaryTrue(&copies)); assert(copies == 0);
constexpr bool all_the_algorithms()
     (void)std::ranges::copy_if(a, first2, UnaryTrue(&copies)); assert(copies == 0);
 #if TEST_STD_VER > 20
     //(void)std::ranges::ends_with(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
 #endif
     (void)std::ranges::equal(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
     (void)std::ranges::equal(a, b, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::equal_range(first, last, value, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::equal_range(a, value, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::find_end(first, last, first2, mid2, Equal(&copies)); assert(copies == 0);
-    //(void)std::ranges::find_end(a, b, Equal(&copies)); assert(copies == 0);
+    (void)std::ranges::find_end(first, last, first2, mid2, Equal(&copies)); assert(copies == 0);
+    (void)std::ranges::find_end(a, b, Equal(&copies)); assert(copies == 0);
     (void)std::ranges::find_first_of(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
     (void)std::ranges::find_first_of(a, b, Equal(&copies)); assert(copies == 0);
     (void)std::ranges::find_if(first, last, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::find_if(a, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::find_if_not(first, last, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::find_if_not(a, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::for_each(first, last, UnaryVoid(&copies)); assert(copies == 1); copies = 0;
     (void)std::ranges::for_each(a, UnaryVoid(&copies)); assert(copies == 1); copies = 0;
#endif
     //(void)std::ranges::remove_copy_if(first, last, first2, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy_if(a, first2, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_if(first, last, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_if(a, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::replace_copy_if(first, last, first2, UnaryTrue(&copies), value); assert(copies == 0);
     //(void)std::ranges::replace_copy_if(a, first2, UnaryTrue(&copies), value); assert(copies == 0);
     (void)std::ranges::replace_if(first, last, UnaryTrue(&copies), value); assert(copies == 0);
     (void)std::ranges::replace_if(a, UnaryTrue(&copies), value); assert(copies == 0);
-    //(void)std::ranges::search(first, last, first2, mid2, Equal(&copies)); assert(copies == 0);
-    //(void)std::ranges::search(a, b, Equal(&copies)); assert(copies == 0);
-    //(void)std::ranges::search_n(first, last, count, value, Equal(&copies)); assert(copies == 0);
-    //(void)std::ranges::search_n(a, count, value, Equal(&copies)); assert(copies == 0);
+    (void)std::ranges::search(first, last, first2, mid2, Equal(&copies)); assert(copies == 0);
+    (void)std::ranges::search(a, b, Equal(&copies)); assert(copies == 0);
+    (void)std::ranges::search_n(first, last, count, value, Equal(&copies)); assert(copies == 0);
+    (void)std::ranges::search_n(a, count, value, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::set_difference(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_difference(a, b, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_intersection(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_intersection(a, b, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_symmetric_difference(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_symmetric_difference(a, b, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_union(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_union(a, b, first2, Less(&copies)); assert(copies == 0);

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/ranges_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_if.h'}}
 #include <__algorithm/ranges_copy_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_n.h'}}
 #include <__algorithm/ranges_count.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count.h'}}
 #include <__algorithm/ranges_count_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count_if.h'}}
 #include <__algorithm/ranges_equal.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_equal.h'}}
 #include <__algorithm/ranges_fill.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_fill.h'}}
 #include <__algorithm/ranges_fill_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_fill_n.h'}}
 #include <__algorithm/ranges_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find.h'}}
+#include <__algorithm/ranges_find_end.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_end.h'}}
 #include <__algorithm/ranges_find_first_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_first_of.h'}}
 #include <__algorithm/ranges_find_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if.h'}}
 #include <__algorithm/ranges_find_if_not.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if_not.h'}}
 #include <__algorithm/ranges_for_each.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_for_each.h'}}
 #include <__algorithm/ranges_for_each_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_for_each_n.h'}}
 #include <__algorithm/ranges_is_partitioned.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_partitioned.h'}}
 #include <__algorithm/ranges_is_sorted.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_sorted.h'}}
 #include <__algorithm/ranges_is_sorted_until.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_sorted_until.h'}}
 #include <__algorithm/ranges_lexicographical_compare.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_lexicographical_compare.h'}}
 #include <__algorithm/ranges_lower_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_lower_bound.h'}}
 #include <__algorithm/ranges_max.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max.h'}}
 #include <__algorithm/ranges_max_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max_element.h'}}
 #include <__algorithm/ranges_merge.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_merge.h'}}
 #include <__algorithm/ranges_min.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min.h'}}
 #include <__algorithm/ranges_min_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min_element.h'}}
 #include <__algorithm/ranges_minmax.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax.h'}}
 #include <__algorithm/ranges_minmax_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax_element.h'}}
 #include <__algorithm/ranges_mismatch.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_mismatch.h'}}
 #include <__algorithm/ranges_move.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move.h'}}
 #include <__algorithm/ranges_move_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move_backward.h'}}
 #include <__algorithm/ranges_none_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_none_of.h'}}
 #include <__algorithm/ranges_replace.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace.h'}}
 #include <__algorithm/ranges_replace_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace_if.h'}}
 #include <__algorithm/ranges_reverse.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse.h'}}
+#include <__algorithm/ranges_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_search.h'}}
+#include <__algorithm/ranges_search_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_search_n.h'}}
 #include <__algorithm/ranges_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_sort.h'}}
 #include <__algorithm/ranges_stable_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_stable_sort.h'}}
 #include <__algorithm/ranges_swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_swap_ranges.h'}}
 #include <__algorithm/ranges_transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_transform.h'}}
 #include <__algorithm/ranges_upper_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_upper_bound.h'}}
 #include <__algorithm/remove.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove.h'}}
 #include <__algorithm/remove_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_copy.h'}}
 #include <__algorithm/remove_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_copy_if.h'}}

libcxx/test/std/algorithms/alg.nonmodifying/alg.find.end/ranges.find_end.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-has-no-incomplete-ranges
+
+// template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2,
+//          class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+//   requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
+//   constexpr subrange<I1>
+//     ranges::find_end(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
+//                      Proj1 proj1 = {}, Proj2 proj2 = {});
+// template<forward_range R1, forward_range R2,
+//          class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+//   requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
+//   constexpr borrowed_subrange_t<R1>
+//     ranges::find_end(R1&& r1, R2&& r2, Pred pred = {},
+//                      Proj1 proj1 = {}, Proj2 proj2 = {});
+
+#include <algorithm>
+#include <array>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "test_iterators.h"
+
+template <class Iter1, class Sent1 = Iter1, class Iter2 = int*, class Sent2 = Iter2>
+concept HasFindEndIt = requires (Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) {
+  std::ranges::find_end(first1, last1, first2, last2);
+};
+
+static_assert(HasFindEndIt<int*>);
+static_assert(!HasFindEndIt<ForwardIteratorNotDerivedFrom>);
+static_assert(!HasFindEndIt<ForwardIteratorNotIncrementable>);
+static_assert(!HasFindEndIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasFindEndIt<int*, int*, int**>); // not indirectly comparable
+static_assert(!HasFindEndIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasFindEndIt<int*, int*, ForwardIteratorNotDerivedFrom>);
+static_assert(!HasFindEndIt<int*, int*, ForwardIteratorNotIncrementable>);
+static_assert(!HasFindEndIt<int*, int*, int*, SentinelForNotSemiregular>);
+static_assert(!HasFindEndIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
+
+template <class Range1, class Range2 = UncheckedRange<int*>>
+concept HasFindEndR = requires (Range1 range1, Range2 range2) {
+  std::ranges::find_end(range1, range2);
+};
+
+static_assert(HasFindEndR<UncheckedRange<int*>>);
+static_assert(!HasFindEndR<ForwardRangeNotDerivedFrom>);
+static_assert(!HasFindEndR<ForwardIteratorNotIncrementable>);
+static_assert(!HasFindEndR<ForwardRangeNotSentinelSemiregular>);
+static_assert(!HasFindEndR<ForwardRangeNotSentinelEqualityComparableWith>);
+static_assert(!HasFindEndR<UncheckedRange<int*>, UncheckedRange<int**>>); // not indirectly comparable
+static_assert(!HasFindEndR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>);
+static_assert(!HasFindEndR<UncheckedRange<int*>, ForwardRangeNotIncrementable>);
+static_assert(!HasFindEndR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>);
+static_assert(!HasFindEndR<UncheckedRange<int*>, ForwardRangeNotSentinelEqualityComparableWith>);
+
+template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2>
+constexpr void test_iterators() {
+  { // simple test
+    {
+      int a[] = {1, 2, 3, 4, 5, 6};
+      int p[] = {3, 4};
+      std::same_as<std::ranges::subrange<Iter1, Iter1>> decltype(auto) ret =
+          std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 2)));
+      assert(base(ret.begin()) == a + 2);
+      assert(base(ret.end()) == a + 4);
+    }
+    {
+      int a[] = {1, 2, 3, 4, 5, 6};
+      int p[] = {3, 4};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2)));
+      std::same_as<std::ranges::subrange<Iter1, Iter1>> decltype(auto) ret = std::ranges::find_end(range1, range2);
+      assert(base(ret.begin()) == a + 2);
+      assert(base(ret.end()) == a + 4);
+    }
+  }
+
+  { // matching part begins at the front
+    {
+      int a[] = {7, 5, 3, 7, 3, 6};
+      int p[] = {7, 5, 3};
+      auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 3)));
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 3);
+    }
+    {
+      int a[] = {7, 5, 3, 7, 3, 6};
+      int p[] = {7, 5, 3};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
+      auto ret = std::ranges::find_end(range1, range2);
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 3);
+    }
+  }
+
+  { // matching part ends at the back
+    {
+      int a[] = {9, 3, 6, 4, 8};
+      int p[] = {4, 8};
+      auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 5)), Iter2(p), Sent2(Iter2(p + 2)));
+      assert(base(ret.begin()) == a + 3);
+      assert(base(ret.end()) == a + 5);
+    }
+    {
+      int a[] = {9, 3, 6, 4, 8};
+      int p[] = {4, 8};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2)));
+      auto ret = std::ranges::find_end(range1, range2);
+      assert(base(ret.begin()) == a + 3);
+      assert(base(ret.end()) == a + 5);
+    }
+  }
+
+  { // pattern does not match
+    {
+      int a[] = {9, 3, 6, 4, 8};
+      int p[] = {1};
+      auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 5)), Iter2(p), Sent2(Iter2(p + 1)));
+      assert(base(ret.begin()) == a + 5);
+      assert(base(ret.end()) == a + 5);
+    }
+    {
+      int a[] = {9, 3, 6, 4, 8};
+      int p[] = {1};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 1)));
+      auto ret = std::ranges::find_end(range1, range2);
+      assert(base(ret.begin()) == a + 5);
+      assert(base(ret.end()) == a + 5);
+    }
+  }
+
+  { // range and pattern are identical
+    {
+      int a[] = {6, 7, 8, 9};
+      int p[] = {6, 7, 8, 9};
+      auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 4)), Iter2(p), Sent2(Iter2(p + 4)));
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 4);
+    }
+    {
+      int a[] = {6, 7, 8, 9};
+      int p[] = {6, 7, 8, 9};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 4)));
+      auto ret = std::ranges::find_end(range1, range2);
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 4);
+    }
+  }
+
+  { // pattern is longer than range
+    {
+      int a[] = {6, 7, 8};
+      int p[] = {6, 7, 8, 9};
+      auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 3)), Iter2(p), Sent2(Iter2(p + 4)));
+      assert(base(ret.begin()) == a + 3);
+      assert(base(ret.end()) == a + 3);
+    }
+    {
+      int a[] = {6, 7, 8};
+      int p[] = {6, 7, 8, 9};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 4)));
+      auto ret = std::ranges::find_end(range1, range2);
+      assert(base(ret.begin()) == a + 3);
+      assert(base(ret.end()) == a + 3);
+    }
+  }
+
+  { // pattern has zero length
+    {
+      int a[] = {6, 7, 8};
+      int p[] = {};
+      auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 3)), Iter2(p), Sent2(Iter2(p)));
+      assert(base(ret.begin()) == a + 3);
+      assert(base(ret.end()) == a + 3);
+    }
+    {
+      int a[] = {6, 7, 8};
+      int p[] = {};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p)));
+      auto ret = std::ranges::find_end(range1, range2);
+      assert(base(ret.begin()) == a + 3);
+      assert(base(ret.end()) == a + 3);
+    }
+  }
+
+  { // range has zero length
+    {
+      int a[] = {};
+      int p[] = {6, 7, 8};
+      auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a)), Iter2(p), Sent2(Iter2(p + 3)));
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a);
+    }
+    {
+      int a[] = {};
+      int p[] = {6, 7, 8};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
+      auto ret = std::ranges::find_end(range1, range2);
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a);
+    }
+  }
+
+  { // check that the first match is returned
+    {
+      int a[] = {6, 7, 8, 6, 7, 8, 6, 7, 8};
+      int p[] = {6, 7, 8};
+      auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 9)), Iter2(p), Sent2(Iter2(p + 3)));
+      assert(base(ret.begin()) == a + 6);
+      assert(base(ret.end()) == a + 9);
+    }
+    {
+      int a[] = {6, 7, 8, 6, 7, 8, 6, 7, 8};
+      int p[] = {6, 7, 8};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 9)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
+      auto ret = std::ranges::find_end(range1, range2);
+      assert(base(ret.begin()) == a + 6);
+      assert(base(ret.end()) == a + 9);
+    }
+  }
+
+  { // check that the predicate is used
+    {
+      int a[] = {1, 2, 8, 1, 5, 6};
+      int p[] = {7, 0, 4};
+      auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 6)),
+                                       Iter2(p), Sent2(Iter2(p + 3)),
+                                       [](int l, int r) { return l > r; });
+      assert(base(ret.begin()) == a + 2);
+      assert(base(ret.end()) == a + 5);
+    }
+    {
+      int a[] = {1, 2, 8, 1, 5, 6};
+      int p[] = {7, 0, 4};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
+      auto ret = std::ranges::find_end(range1, range2, [](int l, int r) { return l > r; });
+      assert(base(ret.begin()) == a + 2);
+      assert(base(ret.end()) == a + 5);
+    }
+  }
+
+  { // check that the projections are used
+    {
+      int a[] = {1, 3, 5, 1, 5, 6};
+      int p[] = {2, 3, 4};
+      auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 6)),
+                                       Iter2(p), Sent2(Iter2(p + 3)),
+                                       {},
+                                       [](int i) { return i + 3; },
+                                       [](int i) { return i * 2; });
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 3);
+    }
+    {
+      int a[] = {1, 3, 5, 1, 5, 6};
+      int p[] = {2, 3, 4};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
+      auto ret = std::ranges::find_end(range1,
+                                       range2,
+                                       {},
+                                       [](int i) { return i + 3; },
+                                       [](int i) { return i * 2; });
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 3);
+    }
+  }
+}
+
+template <class Iter1, class Sent1 = Iter1>
+constexpr void test_iterators2() {
+  test_iterators<Iter1, Sent1, forward_iterator<int*>>();
+  test_iterators<Iter1, Sent1, forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>();
+  test_iterators<Iter1, Sent1, bidirectional_iterator<int*>>();
+  test_iterators<Iter1, Sent1, bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>();
+  test_iterators<Iter1, Sent1, random_access_iterator<int*>>();
+  test_iterators<Iter1, Sent1, random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>();
+  test_iterators<Iter1, Sent1, contiguous_iterator<int*>>();
+  test_iterators<Iter1, Sent1, contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>();
+  test_iterators<Iter1, Sent1, int*>();
+}
+
+constexpr bool test() {
+  test_iterators2<forward_iterator<int*>>();
+  test_iterators2<forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>();
+  test_iterators2<bidirectional_iterator<int*>>();
+  test_iterators2<bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>();
+  test_iterators2<random_access_iterator<int*>>();
+  test_iterators2<random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>();
+  test_iterators2<contiguous_iterator<int*>>();
+  test_iterators2<contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>();
+  test_iterators2<int*>();
+
+  { // check that std::invoke is used
+    struct S {
+      int i;
+
+      constexpr S identity() {
+        return *this;
+      }
+
+      constexpr bool compare(const S& s) {
+        return i == s.i;
+      }
+    };
+    {
+      S a[] = {{1}, {2}, {3}, {4}};
+      S p[] = {{2}, {3}};
+      auto ret = std::ranges::find_end(a, a + 4, p, p + 2, &S::compare, &S::identity, &S::identity);
+      assert(ret.begin() == a + 1);
+      assert(ret.end() == a + 3);
+    }
+    {
+      S a[] = {{1}, {2}, {3}, {4}};
+      S p[] = {{2}, {3}};
+      auto ret = std::ranges::find_end(a, p, &S::compare, &S::identity, &S::identity);
+      assert(ret.begin() == a + 1);
+      assert(ret.end() == a + 3);
+    }
+  }
+
+  { // check that std::ranges::dangling is returned
+    [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
+        std::ranges::find_end(std::array {1, 2, 3, 4}, std::array {2, 3});
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search.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-has-no-incomplete-ranges
+
+// template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
+//          sentinel_for<I2> S2, class Pred = ranges::equal_to,
+//          class Proj1 = identity, class Proj2 = identity>
+//   requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
+//   constexpr subrange<I1>
+//     ranges::search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
+//                    Proj1 proj1 = {}, Proj2 proj2 = {});
+// template<forward_range R1, forward_range R2, class Pred = ranges::equal_to,
+//          class Proj1 = identity, class Proj2 = identity>
+//   requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
+//   constexpr borrowed_subrange_t<R1>
+//     ranges::search(R1&& r1, R2&& r2, Pred pred = {},
+//                    Proj1 proj1 = {}, Proj2 proj2 = {});
+
+#include <algorithm>
+#include <array>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "test_iterators.h"
+
+template <class Iter1, class Sent1 = Iter1, class Iter2 = int*, class Sent2 = Iter2>
+concept HasSearchIt = requires (Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) {
+  std::ranges::search(first1, last1, first2, last2);
+};
+
+static_assert(HasSearchIt<int*>);
+static_assert(!HasSearchIt<ForwardIteratorNotDerivedFrom>);
+static_assert(!HasSearchIt<ForwardIteratorNotIncrementable>);
+static_assert(!HasSearchIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasSearchIt<int*, int*, int**>); // not indirectly comparable
+static_assert(!HasSearchIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasSearchIt<int*, int*, ForwardIteratorNotDerivedFrom>);
+static_assert(!HasSearchIt<int*, int*, ForwardIteratorNotIncrementable>);
+static_assert(!HasSearchIt<int*, int*, int*, SentinelForNotSemiregular>);
+static_assert(!HasSearchIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
+
+template <class Range1, class Range2 = UncheckedRange<int*>>
+concept HasSearchR = requires (Range1 range1, Range2 range2) {
+  std::ranges::search(range1, range2);
+};
+
+static_assert(HasSearchR<UncheckedRange<int*>>);
+static_assert(!HasSearchR<ForwardRangeNotDerivedFrom>);
+static_assert(!HasSearchR<ForwardIteratorNotIncrementable>);
+static_assert(!HasSearchR<ForwardRangeNotSentinelSemiregular>);
+static_assert(!HasSearchR<ForwardRangeNotSentinelEqualityComparableWith>);
+static_assert(!HasSearchR<UncheckedRange<int*>, UncheckedRange<int**>>); // not indirectly comparable
+static_assert(!HasSearchR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>);
+static_assert(!HasSearchR<UncheckedRange<int*>, ForwardRangeNotIncrementable>);
+static_assert(!HasSearchR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>);
+static_assert(!HasSearchR<UncheckedRange<int*>, ForwardRangeNotSentinelEqualityComparableWith>);
+
+template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2>
+constexpr void test_iterators() {
+  { // simple test
+    {
+      int a[] = {1, 2, 3, 4, 5, 6};
+      int p[] = {3, 4};
+      std::same_as<std::ranges::subrange<Iter1, Iter1>> decltype(auto) ret =
+          std::ranges::search(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 2)));
+      assert(base(ret.begin()) == a + 2);
+      assert(base(ret.end()) == a + 4);
+    }
+    {
+      int a[] = {1, 2, 3, 4, 5, 6};
+      int p[] = {3, 4};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2)));
+      std::same_as<std::ranges::subrange<Iter1, Iter1>> decltype(auto) ret = std::ranges::search(range1, range2);
+      assert(base(ret.begin()) == a + 2);
+      assert(base(ret.end()) == a + 4);
+    }
+  }
+
+  { // matching part begins at the front
+    {
+      int a[] = {7, 5, 3, 7, 3, 6};
+      int p[] = {7, 5, 3};
+      auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 3)));
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 3);
+    }
+    {
+      int a[] = {7, 5, 3, 7, 3, 6};
+      int p[] = {7, 5, 3};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
+      auto ret = std::ranges::search(range1, range2);
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 3);
+    }
+  }
+
+  { // matching part ends at the back
+    {
+      int a[] = {9, 3, 6, 4, 8};
+      int p[] = {4, 8};
+      auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 5)), Iter2(p), Sent2(Iter2(p + 2)));
+      assert(base(ret.begin()) == a + 3);
+      assert(base(ret.end()) == a + 5);
+    }
+    {
+      int a[] = {9, 3, 6, 4, 8};
+      int p[] = {4, 8};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2)));
+      auto ret = std::ranges::search(range1, range2);
+      assert(base(ret.begin()) == a + 3);
+      assert(base(ret.end()) == a + 5);
+    }
+  }
+
+  { // pattern does not match
+    {
+      int a[] = {9, 3, 6, 4, 8};
+      int p[] = {1};
+      auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 5)), Iter2(p), Sent2(Iter2(p + 1)));
+      assert(base(ret.begin()) == a + 5);
+      assert(base(ret.end()) == a + 5);
+    }
+    {
+      int a[] = {9, 3, 6, 4, 8};
+      int p[] = {1};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 1)));
+      auto ret = std::ranges::search(range1, range2);
+      assert(base(ret.begin()) == a + 5);
+      assert(base(ret.end()) == a + 5);
+    }
+  }
+
+  { // range and pattern are identical
+    {
+      int a[] = {6, 7, 8, 9};
+      int p[] = {6, 7, 8, 9};
+      auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 4)), Iter2(p), Sent2(Iter2(p + 4)));
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 4);
+    }
+    {
+      int a[] = {6, 7, 8, 9};
+      int p[] = {6, 7, 8, 9};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 4)));
+      auto ret = std::ranges::search(range1, range2);
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 4);
+    }
+  }
+
+  { // pattern is longer than range
+    {
+      int a[] = {6, 7, 8};
+      int p[] = {6, 7, 8, 9};
+      auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 3)), Iter2(p), Sent2(Iter2(p + 4)));
+      assert(base(ret.begin()) == a + 3);
+      assert(base(ret.end()) == a + 3);
+    }
+    {
+      int a[] = {6, 7, 8};
+      int p[] = {6, 7, 8, 9};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 4)));
+      auto ret = std::ranges::search(range1, range2);
+      assert(base(ret.begin()) == a + 3);
+      assert(base(ret.end()) == a + 3);
+    }
+  }
+
+  { // pattern has zero length
+    {
+      int a[] = {6, 7, 8};
+      int p[] = {};
+      auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 3)), Iter2(p), Sent2(Iter2(p)));
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a);
+    }
+    {
+      int a[] = {6, 7, 8};
+      int p[] = {};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p)));
+      auto ret = std::ranges::search(range1, range2);
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a);
+    }
+  }
+
+  { // range has zero length
+    {
+      int a[] = {};
+      int p[] = {6, 7, 8};
+      auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a)), Iter2(p), Sent2(Iter2(p + 3)));
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a);
+    }
+    {
+      int a[] = {};
+      int p[] = {6, 7, 8};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
+      auto ret = std::ranges::search(range1, range2);
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a);
+    }
+  }
+
+  { // check that the first match is returned
+    {
+      int a[] = {6, 7, 8, 6, 7, 8, 6, 7, 8};
+      int p[] = {6, 7, 8};
+      auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 9)), Iter2(p), Sent2(Iter2(p + 3)));
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 3);
+    }
+    {
+      int a[] = {6, 7, 8, 6, 7, 8, 6, 7, 8};
+      int p[] = {6, 7, 8};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 9)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
+      auto ret = std::ranges::search(range1, range2);
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 3);
+    }
+  }
+
+  { // check that the predicate is used
+    {
+      int a[] = {1, 2, 8, 1, 5, 6};
+      int p[] = {7, 0, 4};
+      auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 6)),
+                                     Iter2(p), Sent2(Iter2(p + 3)),
+                                     [](int l, int r) { return l > r; });
+      assert(base(ret.begin()) == a + 2);
+      assert(base(ret.end()) == a + 5);
+    }
+    {
+      int a[] = {1, 2, 8, 1, 5, 6};
+      int p[] = {7, 0, 4};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
+      auto ret = std::ranges::search(range1, range2, [](int l, int r) { return l > r; });
+      assert(base(ret.begin()) == a + 2);
+      assert(base(ret.end()) == a + 5);
+    }
+  }
+
+  { // check that the projections are used
+    {
+      int a[] = {1, 3, 5, 1, 5, 6};
+      int p[] = {2, 3, 4};
+      auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 6)),
+                                     Iter2(p), Sent2(Iter2(p + 3)),
+                                     {},
+                                     [](int i) { return i + 3; },
+                                     [](int i) { return i * 2; });
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 3);
+    }
+    {
+      int a[] = {1, 3, 5, 1, 5, 6};
+      int p[] = {2, 3, 4};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
+      auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
+      auto ret = std::ranges::search(range1,
+                                     range2,
+                                     {},
+                                     [](int i) { return i + 3; },
+                                     [](int i) { return i * 2; });
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 3);
+    }
+  }
+}
+
+template <class Iter1, class Sent1 = Iter1>
+constexpr void test_iterators2() {
+  test_iterators<Iter1, Sent1, forward_iterator<int*>>();
+  test_iterators<Iter1, Sent1, forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>();
+  test_iterators<Iter1, Sent1, bidirectional_iterator<int*>>();
+  test_iterators<Iter1, Sent1, bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>();
+  test_iterators<Iter1, Sent1, random_access_iterator<int*>>();
+  test_iterators<Iter1, Sent1, random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>();
+  test_iterators<Iter1, Sent1, contiguous_iterator<int*>>();
+  test_iterators<Iter1, Sent1, contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>();
+  test_iterators<Iter1, Sent1, int*>();
+}
+
+constexpr bool test() {
+  test_iterators2<forward_iterator<int*>>();
+  test_iterators2<forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>();
+  test_iterators2<bidirectional_iterator<int*>>();
+  test_iterators2<bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>();
+  test_iterators2<random_access_iterator<int*>>();
+  test_iterators2<random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>();
+  test_iterators2<contiguous_iterator<int*>>();
+  test_iterators2<contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>();
+  test_iterators2<int*>();
+
+  { // check that std::invoke is used
+    struct S {
+      int i;
+
+      constexpr S identity() {
+        return *this;
+      }
+
+      constexpr bool compare(const S& s) {
+        return i == s.i;
+      }
+    };
+    {
+      S a[] = {{1}, {2}, {3}, {4}};
+      S p[] = {{2}, {3}};
+      auto ret = std::ranges::search(a, a + 4, p, p + 2, &S::compare, &S::identity, &S::identity);
+      assert(ret.begin() == a + 1);
+      assert(ret.end() == a + 3);
+    }
+    {
+      S a[] = {{1}, {2}, {3}, {4}};
+      S p[] = {{2}, {3}};
+      auto ret = std::ranges::search(a, p, &S::compare, &S::identity, &S::identity);
+      assert(ret.begin() == a + 1);
+      assert(ret.end() == a + 3);
+    }
+  }
+
+  { // check that std::ranges::dangling is returned
+    [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
+        std::ranges::search(std::array {1, 2, 3, 4}, std::array {2, 3});
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search_n.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-has-no-incomplete-ranges
+
+// template<forward_iterator I, sentinel_for<I> S, class T,
+//          class Pred = ranges::equal_to, class Proj = identity>
+//   requires indirectly_comparable<I, const T*, Pred, Proj>
+//   constexpr subrange<I>
+//     ranges::search_n(I first, S last, iter_difference_t<I> count,
+//                      const T& value, Pred pred = {}, Proj proj = {});
+// template<forward_range R, class T, class Pred = ranges::equal_to,
+//          class Proj = identity>
+//   requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj>
+//   constexpr borrowed_subrange_t<R>
+//     ranges::search_n(R&& r, range_difference_t<R> count,
+//                      const T& value, Pred pred = {}, Proj proj = {});
+
+#include <algorithm>
+#include <array>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "test_iterators.h"
+
+template <class Iter1, class Sent1 = Iter1>
+concept HasSearchNIt = requires (Iter1 first1, Sent1 last1) {
+  std::ranges::search_n(first1, last1, 0, 0);
+};
+
+static_assert(HasSearchNIt<int*>);
+static_assert(!HasSearchNIt<ForwardIteratorNotDerivedFrom>);
+static_assert(!HasSearchNIt<ForwardIteratorNotIncrementable>);
+static_assert(!HasSearchNIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasSearchNIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasSearchNIt<int**, int**>); // not indirectly comparable
+
+template <class Range1, class Range2 = UncheckedRange<int*>>
+concept HasSearchNR = requires (Range1 range) {
+  std::ranges::search_n(range, 0, 0);
+};
+
+static_assert(HasSearchNR<UncheckedRange<int*>>);
+static_assert(!HasSearchNR<ForwardRangeNotDerivedFrom>);
+static_assert(!HasSearchNR<ForwardIteratorNotIncrementable>);
+static_assert(!HasSearchNR<ForwardRangeNotSentinelSemiregular>);
+static_assert(!HasSearchNR<ForwardRangeNotSentinelEqualityComparableWith>);
+static_assert(!HasSearchNR<UncheckedRange<int**>>); // not indirectly comparable
+
+template <class Iter, class Sent = Iter>
+constexpr void test_iterators() {
+  { // simple test
+    {
+      int a[] = {1, 2, 3, 4, 5, 6};
+      std::same_as<std::ranges::subrange<Iter, Iter>> decltype(auto) ret =
+          std::ranges::search_n(Iter(a), Sent(Iter(a + 6)), 1, 3);
+      assert(base(ret.begin()) == a + 2);
+      assert(base(ret.end()) == a + 3);
+    }
+    {
+      int a[] = {1, 2, 3, 4, 5, 6};
+      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6)));
+      std::same_as<std::ranges::subrange<Iter, Iter>> decltype(auto) ret = std::ranges::search_n(range, 1, 3);
+      assert(base(ret.begin()) == a + 2);
+      assert(base(ret.end()) == a + 3);
+    }
+  }
+
+  { // matching part begins at the front
+    {
+      int a[] = {7, 7, 3, 7, 3, 6};
+      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 6)), 2, 7);
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 2);
+    }
+    {
+      int a[] = {7, 7, 3, 7, 3, 6};
+      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6)));
+      auto ret = std::ranges::search_n(range, 2, 7);
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 2);
+    }
+  }
+
+  { // matching part ends at the back
+    {
+      int a[] = {9, 3, 6, 4, 4};
+      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 5)), 2, 4);
+      assert(base(ret.begin()) == a + 3);
+      assert(base(ret.end()) == a + 5);
+    }
+    {
+      int a[] = {9, 3, 6, 4, 4};
+      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 5)));
+      auto ret = std::ranges::search_n(range, 2, 4);
+      assert(base(ret.begin()) == a + 3);
+      assert(base(ret.end()) == a + 5);
+    }
+  }
+
+  { // pattern does not match
+    {
+      int a[] = {9, 3, 6, 4, 8};
+      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 5)), 1, 1);
+      assert(base(ret.begin()) == a + 5);
+      assert(base(ret.end()) == a + 5);
+    }
+    {
+      int a[] = {9, 3, 6, 4, 8};
+      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 5)));
+      auto ret = std::ranges::search_n(range, 1, 1);
+      assert(base(ret.begin()) == a + 5);
+      assert(base(ret.end()) == a + 5);
+    }
+  }
+
+  { // range and pattern are identical
+    {
+      int a[] = {1, 1, 1, 1};
+      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 4)), 4, 1);
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 4);
+    }
+    {
+      int a[] = {1, 1, 1, 1};
+      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 4)));
+      auto ret = std::ranges::search_n(range, 4, 1);
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 4);
+    }
+  }
+
+  { // pattern is longer than range
+    {
+      int a[] = {3, 3, 3};
+      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 3)), 4, 3);
+      assert(base(ret.begin()) == a + 3);
+      assert(base(ret.end()) == a + 3);
+    }
+    {
+      int a[] = {3, 3, 3};
+      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 3)));
+      auto ret = std::ranges::search_n(range, 4, 3);
+      assert(base(ret.begin()) == a + 3);
+      assert(base(ret.end()) == a + 3);
+    }
+  }
+
+  { // pattern has zero length
+    {
+      int a[] = {6, 7, 8};
+      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 3)), 0, 7);
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a);
+    }
+    {
+      int a[] = {6, 7, 8};
+      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 3)));
+      auto ret = std::ranges::search_n(range, 0, 7);
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a);
+    }
+  }
+
+  { // range has zero length
+    {
+      int a[] = {};
+      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a)), 1, 1);
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a);
+    }
+    {
+      int a[] = {};
+      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a)));
+      auto ret = std::ranges::search_n(range, 1, 1);
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a);
+    }
+  }
+
+  { // check that the first match is returned
+    {
+      int a[] = {6, 6, 8, 6, 6, 8, 6, 6, 8};
+      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 9)), 2, 6);
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 2);
+    }
+    {
+      int a[] = {6, 6, 8, 6, 6, 8, 6, 6, 8};
+      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 9)));
+      auto ret = std::ranges::search_n(range, 2, 6);
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 2);
+    }
+  }
+
+  { // check that the predicate is used
+    {
+      int a[] = {1, 4, 4, 3, 6, 1};
+      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 6)),
+                                       3,
+                                       4,
+                                       [](int l, int r) { return l == r || l == 1; });
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 3);
+    }
+    {
+      int a[] = {1, 4, 4, 3, 6, 1};
+      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6)));
+      auto ret = std::ranges::search_n(range, 3, 4, [](int l, int r) { return l == r || l == 1; });
+      assert(base(ret.begin()) == a);
+      assert(base(ret.end()) == a + 3);
+    }
+  }
+
+  { // check that the projections are used
+    {
+      int a[] = {1, 3, 1, 6, 5, 6};
+      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 6)),
+                                       3,
+                                       6,
+                                       {},
+                                       [](int i) { return i % 2 == 0 ? i : i + 1; });
+      assert(base(ret.begin()) == a + 3);
+      assert(base(ret.end()) == a + 6);
+    }
+    {
+      int a[] = {1, 3, 1, 6, 5, 6};
+      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6)));
+      auto ret = std::ranges::search_n(range,
+                                       3,
+                                       6,
+                                       {},
+                                       [](int i) { return i % 2 == 0 ? i : i + 1; });
+      assert(base(ret.begin()) == a + 3);
+      assert(base(ret.end()) == a + 6);
+    }
+  }
+}
+constexpr bool test() {
+  test_iterators<forward_iterator<int*>>();
+  test_iterators<forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>();
+  test_iterators<bidirectional_iterator<int*>>();
+  test_iterators<bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>();
+  test_iterators<random_access_iterator<int*>>();
+  test_iterators<random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>();
+  test_iterators<contiguous_iterator<int*>>();
+  test_iterators<contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>();
+  test_iterators<int*>();
+
+  { // check that std::invoke is used
+    struct S {
+      int i;
+
+      constexpr S identity() {
+        return *this;
+      }
+
+      constexpr bool compare(int o) {
+        return i == o;
+      }
+    };
+    {
+      S a[] = {{1}, {2}, {3}, {4}};
+      auto ret = std::ranges::search_n(a, a + 4, 1, 2, &S::compare, &S::identity);
+      assert(ret.begin() == a + 1);
+      assert(ret.end() == a + 2);
+    }
+    {
+      S a[] = {{1}, {2}, {3}, {4}};
+      auto ret = std::ranges::search_n(a, 1, 2, &S::compare, &S::identity);
+      assert(ret.begin() == a + 1);
+      assert(ret.end() == a + 2);
+    }
+  }
+
+  { // check that std::ranges::dangling is returned
+    [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
+        std::ranges::search_n(std::array {1, 2, 3, 4}, 1, 0);
+  }
+
+  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::count, a, 42));
 static_assert(test(std::ranges::count_if, a, odd));
 //static_assert(test(std::ranges::ends_with, a, a));
 static_assert(test(std::ranges::equal, a, a));
 //static_assert(test(std::ranges::equal_range, a, 42));
 static_assert(test(std::ranges::fill, a, 42));
 static_assert(test(std::ranges::fill_n, a, 10, 42));
 static_assert(test(std::ranges::find, a, 42));
-//static_assert(test(std::ranges::find_end, a, a));
+static_assert(test(std::ranges::find_end, a, a));
 //static_assert(test(std::ranges::find_first_of, a, a));
 static_assert(test(std::ranges::find_if, a, odd));
 static_assert(test(std::ranges::find_if_not, a, odd));
 static_assert(test(std::ranges::for_each, a, odd));
 static_assert(test(std::ranges::for_each_n, a, 10, odd));
 //static_assert(test(std::ranges::generate, a, 42));
 //static_assert(test(std::ranges::generate_n, a, 10, 42));
 //static_assert(test(std::ranges::includes, a, a));

 //static_assert(test(std::ranges::replace_copy, a, a, 42, 43));
 //static_assert(test(std::ranges::replace_copy_if, a, a, odd, 43));
 static_assert(test(std::ranges::replace_if, a, odd, 43));
 static_assert(test(std::ranges::reverse, a));
 //static_assert(test(std::ranges::reverse_copy, a, a));
 //static_assert(test(std::ranges::rotate, a, a+5));
 //static_assert(test(std::ranges::rotate_copy, a, a+5, a));
 //static_assert(test(std::ranges::sample, a, a, 5));
-//static_assert(test(std::ranges::search, a, a));
-//static_assert(test(std::ranges::search_n, a, 10, 42));
+static_assert(test(std::ranges::search, a, a));
+static_assert(test(std::ranges::search_n, a, 10, 42));
 //static_assert(test(std::ranges::set_difference, a, a, a));
 //static_assert(test(std::ranges::set_intersection, a, a, a));
 //static_assert(test(std::ranges::set_symmetric_difference, a, a, a));
 //static_assert(test(std::ranges::set_union, a, a, a));
 //static_assert(test(std::ranges::shuffle, a, g));
 static_assert(test(std::ranges::sort, a));
 //static_assert(test(std::ranges::sort_heap, a));
 //static_assert(test(std::ranges::stable_partition, a, odd));