Commit 92b69215e6

@@ -0,0 +1,51 @@
+// -*- 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_ADJACENT_FIND_H
+#define _LIBCPP___ALGORITHM_ADJACENT_FIND_H
+
+#include <__config>
+#include <__algorithm/comp.h>
+#include <__iterator/iterator_traits.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _ForwardIterator, class _BinaryPredicate>
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
+adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred) {
+  if (__first != __last) {
+    _ForwardIterator __i = __first;
+    while (++__i != __last) {
+      if (__pred(*__first, *__i))
+        return __first;
+      __first = __i;
+    }
+  }
+  return __last;
+}
+
+template <class _ForwardIterator>
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
+adjacent_find(_ForwardIterator __first, _ForwardIterator __last) {
+  typedef typename iterator_traits<_ForwardIterator>::value_type __v;
+  return _VSTD::adjacent_find(__first, __last, __equal_to<__v>());
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_ADJACENT_FIND_H

@@ -0,0 +1,37 @@
+// -*- 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_ALL_OF_H
+#define _LIBCPP___ALGORITHM_ALL_OF_H
+
+#include <__config>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _InputIterator, class _Predicate>
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) {
+  for (; __first != __last; ++__first)
+    if (!__pred(*__first))
+      return false;
+  return true;
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_ALL_OF_H

@@ -0,0 +1,37 @@
+// -*- 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_ANY_OF_H
+#define _LIBCPP___ALGORITHM_ANY_OF_H
+
+#include <__config>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _InputIterator, class _Predicate>
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) {
+  for (; __first != __last; ++__first)
+    if (__pred(*__first))
+      return true;
+  return false;
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_ANY_OF_H

@@ -0,0 +1,61 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_BINARY_SEARCH_H
+#define _LIBCPP___ALGORITHM_BINARY_SEARCH_H
+
+#include <__config>
+#include <__algorithm/comp.h>
+#include <__algorithm/lower_bound.h>
+#include <__algorithm/comp_ref_type.h>
+#include <__iterator/iterator_traits.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _Compare, class _ForwardIterator, class _Tp>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+bool
+__binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
+{
+    __first = _VSTD::__lower_bound<_Compare>(__first, __last, __value_, __comp);
+    return __first != __last && !__comp(__value_, *__first);
+}
+
+template <class _ForwardIterator, class _Tp, class _Compare>
+_LIBCPP_NODISCARD_EXT inline
+_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+bool
+binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
+{
+    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+    return _VSTD::__binary_search<_Comp_ref>(__first, __last, __value_, __comp);
+}
+
+template <class _ForwardIterator, class _Tp>
+_LIBCPP_NODISCARD_EXT inline
+_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+bool
+binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
+{
+    return _VSTD::binary_search(__first, __last, __value_,
+                             __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
+}
+
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_BINARY_SEARCH_H

@@ -0,0 +1,52 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_CLAMP_H
+#define _LIBCPP___ALGORITHM_CLAMP_H
+
+#include <__config>
+#include <__debug>
+#include <__algorithm/comp.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if _LIBCPP_STD_VER > 14
+// clamp
+template<class _Tp, class _Compare>
+_LIBCPP_NODISCARD_EXT inline
+_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
+const _Tp&
+clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi, _Compare __comp)
+{
+    _LIBCPP_ASSERT(!__comp(__hi, __lo), "Bad bounds passed to std::clamp");
+    return __comp(__v, __lo) ? __lo : __comp(__hi, __v) ? __hi : __v;
+
+}
+
+template<class _Tp>
+_LIBCPP_NODISCARD_EXT inline
+_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
+const _Tp&
+clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi)
+{
+    return _VSTD::clamp(__v, __lo, __hi, __less<_Tp>());
+}
+#endif
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_CLAMP_H

@@ -0,0 +1,97 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_COMP_H
+#define _LIBCPP___ALGORITHM_COMP_H
+
+#include <__config>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+// I'd like to replace these with _VSTD::equal_to<void>, but can't because:
+//   * That only works with C++14 and later, and
+//   * We haven't included <functional> here.
+template <class _T1, class _T2 = _T1>
+struct __equal_to
+{
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T2& __y) const {return __x == __y;}
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T1& __y) const {return __x == __y;}
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T2& __y) const {return __x == __y;}
+};
+
+template <class _T1>
+struct __equal_to<_T1, _T1>
+{
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
+    bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
+};
+
+template <class _T1>
+struct __equal_to<const _T1, _T1>
+{
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
+    bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
+};
+
+template <class _T1>
+struct __equal_to<_T1, const _T1>
+{
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
+    bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
+};
+
+template <class _T1, class _T2 = _T1>
+struct __less
+{
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
+    bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
+
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
+    bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;}
+
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
+    bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;}
+
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
+    bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;}
+};
+
+template <class _T1>
+struct __less<_T1, _T1>
+{
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
+    bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
+};
+
+template <class _T1>
+struct __less<const _T1, _T1>
+{
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
+    bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
+};
+
+template <class _T1>
+struct __less<_T1, const _T1>
+{
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
+    bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
+};
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_COMP_H

@@ -0,0 +1,87 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_COMP_REF_TYPE_H
+#define _LIBCPP___ALGORITHM_COMP_REF_TYPE_H
+
+#include <__config>
+#include <type_traits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#ifdef _LIBCPP_DEBUG
+
+template <class _Compare>
+struct __debug_less
+{
+    _Compare &__comp_;
+    _LIBCPP_CONSTEXPR_AFTER_CXX17
+    __debug_less(_Compare& __c) : __comp_(__c) {}
+
+    template <class _Tp, class _Up>
+    _LIBCPP_CONSTEXPR_AFTER_CXX17
+    bool operator()(const _Tp& __x,  const _Up& __y)
+    {
+        bool __r = __comp_(__x, __y);
+        if (__r)
+            __do_compare_assert(0, __y, __x);
+        return __r;
+    }
+
+    template <class _Tp, class _Up>
+    _LIBCPP_CONSTEXPR_AFTER_CXX17
+    bool operator()(_Tp& __x,  _Up& __y)
+    {
+        bool __r = __comp_(__x, __y);
+        if (__r)
+            __do_compare_assert(0, __y, __x);
+        return __r;
+    }
+
+    template <class _LHS, class _RHS>
+    _LIBCPP_CONSTEXPR_AFTER_CXX17
+    inline _LIBCPP_INLINE_VISIBILITY
+    decltype((void)declval<_Compare&>()(
+        declval<_LHS &>(), declval<_RHS &>()))
+    __do_compare_assert(int, _LHS & __l, _RHS & __r) {
+        _LIBCPP_ASSERT(!__comp_(__l, __r),
+            "Comparator does not induce a strict weak ordering");
+    }
+
+    template <class _LHS, class _RHS>
+    _LIBCPP_CONSTEXPR_AFTER_CXX17
+    inline _LIBCPP_INLINE_VISIBILITY
+    void __do_compare_assert(long, _LHS &, _RHS &) {}
+};
+
+#endif // _LIBCPP_DEBUG
+
+template <class _Comp>
+struct __comp_ref_type {
+  // Pass the comparator by lvalue reference. Or in debug mode, using a
+  // debugging wrapper that stores a reference.
+#ifndef _LIBCPP_DEBUG
+  typedef typename add_lvalue_reference<_Comp>::type type;
+#else
+  typedef __debug_less<_Comp> type;
+#endif
+};
+
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_COMP_REF_TYPE_H

@@ -0,0 +1,82 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_COPY_H
+#define _LIBCPP___ALGORITHM_COPY_H
+
+#include <__config>
+#include <__algorithm/unwrap_iter.h>
+#include <__iterator/iterator_traits.h>
+#include <cstring>
+#include <type_traits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+// copy
+
+template <class _InputIterator, class _OutputIterator>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+_OutputIterator
+__copy_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
+{
+    for (; __first != __last; ++__first, (void) ++__result)
+        *__result = *__first;
+    return __result;
+}
+
+template <class _InputIterator, class _OutputIterator>
+inline _LIBCPP_INLINE_VISIBILITY
+_OutputIterator
+__copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
+{
+    return _VSTD::__copy_constexpr(__first, __last, __result);
+}
+
+template <class _Tp, class _Up>
+inline _LIBCPP_INLINE_VISIBILITY
+typename enable_if
+<
+    is_same<typename remove_const<_Tp>::type, _Up>::value &&
+    is_trivially_copy_assignable<_Up>::value,
+    _Up*
+>::type
+__copy(_Tp* __first, _Tp* __last, _Up* __result)
+{
+    const size_t __n = static_cast<size_t>(__last - __first);
+    if (__n > 0)
+        _VSTD::memmove(__result, __first, __n * sizeof(_Up));
+    return __result + __n;
+}
+
+template <class _InputIterator, class _OutputIterator>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+_OutputIterator
+copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
+{
+    if (__libcpp_is_constant_evaluated()) {
+        return _VSTD::__copy_constexpr(__first, __last, __result);
+    } else {
+        return _VSTD::__rewrap_iter(__result,
+            _VSTD::__copy(_VSTD::__unwrap_iter(__first),
+                          _VSTD::__unwrap_iter(__last),
+                          _VSTD::__unwrap_iter(__result)));
+    }
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_COPY_H

@@ -0,0 +1,84 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_COPY_BACKWARD_H
+#define _LIBCPP___ALGORITHM_COPY_BACKWARD_H
+
+#include <__config>
+#include <__algorithm/unwrap_iter.h>
+#include <__iterator/iterator_traits.h>
+#include <cstring>
+#include <type_traits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _BidirectionalIterator, class _OutputIterator>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+_OutputIterator
+__copy_backward_constexpr(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
+{
+    while (__first != __last)
+        *--__result = *--__last;
+    return __result;
+}
+
+template <class _BidirectionalIterator, class _OutputIterator>
+inline _LIBCPP_INLINE_VISIBILITY
+_OutputIterator
+__copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
+{
+    return _VSTD::__copy_backward_constexpr(__first, __last, __result);
+}
+
+template <class _Tp, class _Up>
+inline _LIBCPP_INLINE_VISIBILITY
+typename enable_if
+<
+    is_same<typename remove_const<_Tp>::type, _Up>::value &&
+    is_trivially_copy_assignable<_Up>::value,
+    _Up*
+>::type
+__copy_backward(_Tp* __first, _Tp* __last, _Up* __result)
+{
+    const size_t __n = static_cast<size_t>(__last - __first);
+    if (__n > 0)
+    {
+        __result -= __n;
+        _VSTD::memmove(__result, __first, __n * sizeof(_Up));
+    }
+    return __result;
+}
+
+template <class _BidirectionalIterator1, class _BidirectionalIterator2>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+_BidirectionalIterator2
+copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
+              _BidirectionalIterator2 __result)
+{
+    if (__libcpp_is_constant_evaluated()) {
+        return _VSTD::__copy_backward_constexpr(__first, __last, __result);
+    } else {
+        return _VSTD::__rewrap_iter(__result,
+            _VSTD::__copy_backward(_VSTD::__unwrap_iter(__first),
+                                   _VSTD::__unwrap_iter(__last),
+                                   _VSTD::__unwrap_iter(__result)));
+    }
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_COPY_BACKWARD_H

@@ -0,0 +1,48 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_COPY_IF_H
+#define _LIBCPP___ALGORITHM_COPY_IF_H
+
+#include <__config>
+#include <__algorithm/unwrap_iter.h>
+#include <__iterator/iterator_traits.h>
+#include <cstring>
+#include <type_traits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template<class _InputIterator, class _OutputIterator, class _Predicate>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+_OutputIterator
+copy_if(_InputIterator __first, _InputIterator __last,
+        _OutputIterator __result, _Predicate __pred)
+{
+    for (; __first != __last; ++__first)
+    {
+        if (__pred(*__first))
+        {
+            *__result = *__first;
+            ++__result;
+        }
+    }
+    return __result;
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_COPY_IF_H

@@ -0,0 +1,72 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_COPY_N_H
+#define _LIBCPP___ALGORITHM_COPY_N_H
+
+#include <__config>
+#include <__algorithm/copy.h>
+#include <__algorithm/unwrap_iter.h>
+#include <__iterator/iterator_traits.h>
+#include <cstring>
+#include <type_traits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template<class _InputIterator, class _Size, class _OutputIterator>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+typename enable_if
+<
+    __is_cpp17_input_iterator<_InputIterator>::value &&
+   !__is_cpp17_random_access_iterator<_InputIterator>::value,
+    _OutputIterator
+>::type
+copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
+{
+    typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize;
+    _IntegralSize __n = __orig_n;
+    if (__n > 0)
+    {
+        *__result = *__first;
+        ++__result;
+        for (--__n; __n > 0; --__n)
+        {
+            ++__first;
+            *__result = *__first;
+            ++__result;
+        }
+    }
+    return __result;
+}
+
+template<class _InputIterator, class _Size, class _OutputIterator>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+typename enable_if
+<
+    __is_cpp17_random_access_iterator<_InputIterator>::value,
+    _OutputIterator
+>::type
+copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
+{
+    typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize;
+    _IntegralSize __n = __orig_n;
+    return _VSTD::copy(__first, __first + __n, __result);
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_COPY_N_H

@@ -0,0 +1,40 @@
+// -*- 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_COUNT_H
+#define _LIBCPP___ALGORITHM_COUNT_H
+
+#include <__config>
+#include <__iterator/iterator_traits.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _InputIterator, class _Tp>
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+    typename iterator_traits<_InputIterator>::difference_type
+    count(_InputIterator __first, _InputIterator __last, const _Tp& __value_) {
+  typename iterator_traits<_InputIterator>::difference_type __r(0);
+  for (; __first != __last; ++__first)
+    if (*__first == __value_)
+      ++__r;
+  return __r;
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_COUNT_H

@@ -0,0 +1,40 @@
+// -*- 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_COUNT_IF_H
+#define _LIBCPP___ALGORITHM_COUNT_IF_H
+
+#include <__config>
+#include <__iterator/iterator_traits.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _InputIterator, class _Predicate>
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+    typename iterator_traits<_InputIterator>::difference_type
+    count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) {
+  typename iterator_traits<_InputIterator>::difference_type __r(0);
+  for (; __first != __last; ++__first)
+    if (__pred(*__first))
+      ++__r;
+  return __r;
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_COUNT_IF_H

@@ -0,0 +1,90 @@
+// -*- 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_EQUAL_H
+#define _LIBCPP___ALGORITHM_EQUAL_H
+
+#include <__config>
+#include <__algorithm/comp.h>
+#include <__iterator/iterator_traits.h>
+#include <iterator> // FIXME: replace with <__iterator/distance.h> when it lands
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) {
+  for (; __first1 != __last1; ++__first1, (void)++__first2)
+    if (!__pred(*__first1, *__first2))
+      return false;
+  return true;
+}
+
+template <class _InputIterator1, class _InputIterator2>
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2) {
+  typedef typename iterator_traits<_InputIterator1>::value_type __v1;
+  typedef typename iterator_traits<_InputIterator2>::value_type __v2;
+  return _VSTD::equal(__first1, __last1, __first2, __equal_to<__v1, __v2>());
+}
+
+#if _LIBCPP_STD_VER > 11
+template <class _BinaryPredicate, class _InputIterator1, class _InputIterator2>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+__equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
+        _BinaryPredicate __pred, input_iterator_tag, input_iterator_tag) {
+  for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void)++__first2)
+    if (!__pred(*__first1, *__first2))
+      return false;
+  return __first1 == __last1 && __first2 == __last2;
+}
+
+template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+__equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
+        _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag,
+        random_access_iterator_tag) {
+  if (_VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
+    return false;
+  return _VSTD::equal<_RandomAccessIterator1, _RandomAccessIterator2,
+                      typename add_lvalue_reference<_BinaryPredicate>::type>(__first1, __last1, __first2, __pred);
+}
+
+template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
+      _BinaryPredicate __pred) {
+  return _VSTD::__equal<typename add_lvalue_reference<_BinaryPredicate>::type>(
+      __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_InputIterator1>::iterator_category(),
+      typename iterator_traits<_InputIterator2>::iterator_category());
+}
+
+template <class _InputIterator1, class _InputIterator2>
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) {
+  typedef typename iterator_traits<_InputIterator1>::value_type __v1;
+  typedef typename iterator_traits<_InputIterator2>::value_type __v2;
+  return _VSTD::__equal(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(),
+                        typename iterator_traits<_InputIterator1>::iterator_category(),
+                        typename iterator_traits<_InputIterator2>::iterator_category());
+}
+#endif
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_EQUAL_H

@@ -0,0 +1,87 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_EQUAL_RANGE_H
+#define _LIBCPP___ALGORITHM_EQUAL_RANGE_H
+
+#include <__config>
+#include <__algorithm/comp.h>
+#include <__algorithm/comp_ref_type.h>
+#include <__algorithm/half_positive.h>
+#include <__algorithm/lower_bound.h>
+#include <__algorithm/upper_bound.h>
+#include <iterator>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _Compare, class _ForwardIterator, class _Tp>
+_LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator>
+__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
+{
+    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
+    difference_type __len = _VSTD::distance(__first, __last);
+    while (__len != 0)
+    {
+        difference_type __l2 = _VSTD::__half_positive(__len);
+        _ForwardIterator __m = __first;
+        _VSTD::advance(__m, __l2);
+        if (__comp(*__m, __value_))
+        {
+            __first = ++__m;
+            __len -= __l2 + 1;
+        }
+        else if (__comp(__value_, *__m))
+        {
+            __last = __m;
+            __len = __l2;
+        }
+        else
+        {
+            _ForwardIterator __mp1 = __m;
+            return pair<_ForwardIterator, _ForwardIterator>
+                   (
+                      _VSTD::__lower_bound<_Compare>(__first, __m, __value_, __comp),
+                      _VSTD::__upper_bound<_Compare>(++__mp1, __last, __value_, __comp)
+                   );
+        }
+    }
+    return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
+}
+
+template <class _ForwardIterator, class _Tp, class _Compare>
+_LIBCPP_NODISCARD_EXT inline
+_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+pair<_ForwardIterator, _ForwardIterator>
+equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
+{
+    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+    return _VSTD::__equal_range<_Comp_ref>(__first, __last, __value_, __comp);
+}
+
+template <class _ForwardIterator, class _Tp>
+_LIBCPP_NODISCARD_EXT inline
+_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+pair<_ForwardIterator, _ForwardIterator>
+equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
+{
+    return _VSTD::equal_range(__first, __last, __value_,
+                             __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_EQUAL_RANGE_H

@@ -0,0 +1,55 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_FILL_H
+#define _LIBCPP___ALGORITHM_FILL_H
+
+#include <__config>
+#include <__algorithm/fill_n.h>
+#include <__iterator/iterator_traits.h>
+#include <type_traits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _ForwardIterator, class _Tp>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+void
+__fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag)
+{
+    for (; __first != __last; ++__first)
+        *__first = __value_;
+}
+
+template <class _RandomAccessIterator, class _Tp>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+void
+__fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag)
+{
+    _VSTD::fill_n(__first, __last - __first, __value_);
+}
+
+template <class _ForwardIterator, class _Tp>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+void
+fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
+{
+    _VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_category());
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_FILL_H

@@ -0,0 +1,47 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_FILL_N_H
+#define _LIBCPP___ALGORITHM_FILL_N_H
+
+#include <__config>
+#include <__iterator/iterator_traits.h>
+#include <type_traits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _OutputIterator, class _Size, class _Tp>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+_OutputIterator
+__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
+{
+    for (; __n > 0; ++__first, (void) --__n)
+        *__first = __value_;
+    return __first;
+}
+
+template <class _OutputIterator, class _Size, class _Tp>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+_OutputIterator
+fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
+{
+   return _VSTD::__fill_n(__first, _VSTD::__convert_to_integral(__n), __value_);
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_FILL_N_H

@@ -0,0 +1,37 @@
+// -*- 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_H
+#define _LIBCPP___ALGORITHM_FIND_H
+
+#include <__config>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _InputIterator, class _Tp>
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _InputIterator
+find(_InputIterator __first, _InputIterator __last, const _Tp& __value_) {
+  for (; __first != __last; ++__first)
+    if (*__first == __value_)
+      break;
+  return __first;
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_FIND_H

@@ -0,0 +1,154 @@
+// -*- 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 <__config>
+#include <__algorithm/comp.h>
+#include <__iterator/iterator_traits.h>
+#include <type_traits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _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) {
+  // modeled after search algorithm
+  _ForwardIterator1 __r = __last1; // __last1 is the "default" answer
+  if (__first2 == __last2)
+    return __r;
+  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))
+        break;
+      ++__first1;
+    }
+    // *__first1 matches *__first2, now match elements after here
+    _ForwardIterator1 __m1 = __first1;
+    _ForwardIterator2 __m2 = __first2;
+    while (true) {
+      if (++__m2 == __last2) { // Pattern exhaused, record answer and search for another one
+        __r = __first1;
+        ++__first1;
+        break;
+      }
+      if (++__m1 == __last1) // Source exhausted, return last answer
+        return __r;
+      if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first
+      {
+        ++__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) {
+  // modeled after search algorithm (in reverse)
+  if (__first2 == __last2)
+    return __last1; // Everything matches an empty sequence
+  _BidirectionalIterator1 __l1 = __last1;
+  _BidirectionalIterator2 __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))
+        break;
+    }
+    // *__l1 matches *__l2, now match elements before here
+    _BidirectionalIterator1 __m1 = __l1;
+    _BidirectionalIterator2 __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
+      {
+        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) {
+  // Take advantage of knowing source and pattern lengths.  Stop short when source is smaller than pattern
+  typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2;
+  if (__len2 == 0)
+    return __last1;
+  typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1;
+  if (__len1 < __len2)
+    return __last1;
+  const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here
+  _RandomAccessIterator1 __l1 = __last1;
+  _RandomAccessIterator2 __l2 = __last2;
+  --__l2;
+  while (true) {
+    while (true) {
+      if (__s == __l1)
+        return __last1;
+      if (__pred(*--__l1, *__l2))
+        break;
+    }
+    _RandomAccessIterator1 __m1 = __l1;
+    _RandomAccessIterator2 __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)) {
+        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,
+         _BinaryPredicate __pred) {
+  return _VSTD::__find_end<typename add_lvalue_reference<_BinaryPredicate>::type>(
+      __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(),
+      typename iterator_traits<_ForwardIterator2>::iterator_category());
+}
+
+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_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_FIND_END_OF_H