include/__algorithm/stable_partition.h - llvm-project/libcxx - Git at Google

 //===----------------------------------------------------------------------===//
 //
 // 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_STABLE_PARTITION_H
 #define _LIBCPP___ALGORITHM_STABLE_PARTITION_H

 #include <__algorithm/iterator_operations.h>
 #include <__algorithm/rotate.h>
 #include <__config>
 #include <__cstddef/ptrdiff_t.h>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
 #include <__memory/destruct_n.h>
 #include <__memory/unique_ptr.h>
 #include <__memory/unique_temporary_buffer.h>
 #include <__type_traits/remove_cvref.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
 #include <new>

 #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 _AlgPolicy, class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
 _LIBCPP_HIDE_FROM_ABI _ForwardIterator __stable_partition_impl(
     _ForwardIterator __first,
     _ForwardIterator __last,
     _Predicate __pred,
     _Distance __len,
     _Pair __p,
     forward_iterator_tag __fit) {
   using _Ops = _IterOps<_AlgPolicy>;

   // *__first is known to be false
   // __len >= 1
   if (__len == 1)
     return __first;
   if (__len == 2) {
     _ForwardIterator __m = __first;
     if (__pred(*++__m)) {
       _Ops::iter_swap(__first, __m);
       return __m;
     }
     return __first;
   }
   if (__len <= __p.second) { // The buffer is big enough to use
     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
     __destruct_n __d(0);
     unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
     // Move the falses into the temporary buffer, and the trues to the front of the line
     // Update __first to always point to the end of the trues
     value_type* __t = __p.first;
     ::new ((void*)__t) value_type(_Ops::__iter_move(__first));
     __d.template __incr<value_type>();
     ++__t;
     _ForwardIterator __i = __first;
     while (++__i != __last) {
       if (__pred(*__i)) {
         *__first = _Ops::__iter_move(__i);
         ++__first;
       } else {
         ::new ((void*)__t) value_type(_Ops::__iter_move(__i));
         __d.template __incr<value_type>();
         ++__t;
       }
     }
     // All trues now at start of range, all falses in buffer
     // Move falses back into range, but don't mess up __first which points to first false
     __i = __first;
     for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void)++__i)
       *__i = _Ops::__iter_move(__t2);
     // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
     return __first;
   }
   // Else not enough buffer, do in place
   // __len >= 3
   _ForwardIterator __m = __first;
   _Distance __len2     = __len / 2; // __len2 >= 2
   _Ops::advance(__m, __len2);
   // recurse on [__first, __m), *__first know to be false
   // F?????????????????
   // f       m         l
   _ForwardIterator __first_false =
       std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__first, __m, __pred, __len2, __p, __fit);
   // TTTFFFFF??????????
   // f  ff   m         l
   // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
   _ForwardIterator __m1           = __m;
   _ForwardIterator __second_false = __last;
   _Distance __len_half            = __len - __len2;
   while (__pred(*__m1)) {
     if (++__m1 == __last)
       goto __second_half_done;
     --__len_half;
   }
   // TTTFFFFFTTTF??????
   // f  ff   m  m1     l
   __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__m1, __last, __pred, __len_half, __p, __fit);
 __second_half_done:
   // TTTFFFFFTTTTTFFFFF
   // f  ff   m    sf   l
   return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first;
   // TTTTTTTTFFFFFFFFFF
   //         |
 }

 template <class _AlgPolicy, class _Predicate, class _ForwardIterator>
 _LIBCPP_HIDE_FROM_ABI _ForwardIterator
 __stable_partition_impl(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag) {
   typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
   typedef typename iterator_traits<_ForwardIterator>::value_type value_type;

   const difference_type __alloc_limit = 3; // might want to make this a function of trivial assignment
   // Either prove all true and return __first or point to first false
   while (true) {
     if (__first == __last)
       return __first;
     if (!__pred(*__first))
       break;
     ++__first;
   }
   // We now have a reduced range [__first, __last)
   // *__first is known to be false
   difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last);
   __unique_temporary_buffer<value_type> __unique_buf;
   pair<value_type*, ptrdiff_t> __p(0, 0);
   if (__len >= __alloc_limit) {
     __unique_buf = std::__allocate_unique_temporary_buffer<value_type>(__len);
     __p.first    = __unique_buf.get();
     __p.second   = __unique_buf.get_deleter().__count_;
   }
   return std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
       std::move(__first), std::move(__last), __pred, __len, __p, forward_iterator_tag());
 }

 template <class _AlgPolicy, class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
 _BidirectionalIterator __stable_partition_impl(
     _BidirectionalIterator __first,
     _BidirectionalIterator __last,
     _Predicate __pred,
     _Distance __len,
     _Pair __p,
     bidirectional_iterator_tag __bit) {
   using _Ops = _IterOps<_AlgPolicy>;

   // *__first is known to be false
   // *__last is known to be true
   // __len >= 2
   if (__len == 2) {
     _Ops::iter_swap(__first, __last);
     return __last;
   }
   if (__len == 3) {
     _BidirectionalIterator __m = __first;
     if (__pred(*++__m)) {
       _Ops::iter_swap(__first, __m);
       _Ops::iter_swap(__m, __last);
       return __last;
     }
     _Ops::iter_swap(__m, __last);
     _Ops::iter_swap(__first, __m);
     return __m;
   }
   if (__len <= __p.second) { // The buffer is big enough to use
     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
     __destruct_n __d(0);
     unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
     // Move the falses into the temporary buffer, and the trues to the front of the line
     // Update __first to always point to the end of the trues
     value_type* __t = __p.first;
     ::new ((void*)__t) value_type(_Ops::__iter_move(__first));
     __d.template __incr<value_type>();
     ++__t;
     _BidirectionalIterator __i = __first;
     while (++__i != __last) {
       if (__pred(*__i)) {
         *__first = _Ops::__iter_move(__i);
         ++__first;
       } else {
         ::new ((void*)__t) value_type(_Ops::__iter_move(__i));
         __d.template __incr<value_type>();
         ++__t;
       }
     }
     // move *__last, known to be true
     *__first = _Ops::__iter_move(__i);
     __i      = ++__first;
     // All trues now at start of range, all falses in buffer
     // Move falses back into range, but don't mess up __first which points to first false
     for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void)++__i)
       *__i = _Ops::__iter_move(__t2);
     // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
     return __first;
   }
   // Else not enough buffer, do in place
   // __len >= 4
   _BidirectionalIterator __m = __first;
   _Distance __len2           = __len / 2; // __len2 >= 2
   _Ops::advance(__m, __len2);
   // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
   // F????????????????T
   // f       m        l
   _BidirectionalIterator __m1          = __m;
   _BidirectionalIterator __first_false = __first;
   _Distance __len_half                 = __len2;
   while (!__pred(*--__m1)) {
     if (__m1 == __first)
       goto __first_half_done;
     --__len_half;
   }
   // F???TFFF?????????T
   // f   m1  m        l
   __first_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__first, __m1, __pred, __len_half, __p, __bit);
 __first_half_done:
   // TTTFFFFF?????????T
   // f  ff   m        l
   // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
   __m1                                  = __m;
   _BidirectionalIterator __second_false = __last;
   ++__second_false;
   __len_half = __len - __len2;
   while (__pred(*__m1)) {
     if (++__m1 == __last)
       goto __second_half_done;
     --__len_half;
   }
   // TTTFFFFFTTTF?????T
   // f  ff   m  m1    l
   __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__m1, __last, __pred, __len_half, __p, __bit);
 __second_half_done:
   // TTTFFFFFTTTTTFFFFF
   // f  ff   m    sf  l
   return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first;
   // TTTTTTTTFFFFFFFFFF
   //         |
 }

 template <class _AlgPolicy, class _Predicate, class _BidirectionalIterator>
 _LIBCPP_HIDE_FROM_ABI _BidirectionalIterator __stable_partition_impl(
     _BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, bidirectional_iterator_tag) {
   typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
   typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
   const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment
   // Either prove all true and return __first or point to first false
   while (true) {
     if (__first == __last)
       return __first;
     if (!__pred(*__first))
       break;
     ++__first;
   }
   // __first points to first false, everything prior to __first is already set.
   // Either prove [__first, __last) is all false and return __first, or point __last to last true
   do {
     if (__first == --__last)
       return __first;
   } while (!__pred(*__last));
   // We now have a reduced range [__first, __last]
   // *__first is known to be false
   // *__last is known to be true
   // __len >= 2
   difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last) + 1;
   __unique_temporary_buffer<value_type> __unique_buf;
   pair<value_type*, ptrdiff_t> __p(0, 0);
   if (__len >= __alloc_limit) {
     __unique_buf = std::__allocate_unique_temporary_buffer<value_type>(__len);
     __p.first    = __unique_buf.get();
     __p.second   = __unique_buf.get_deleter().__count_;
   }
   return std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
       std::move(__first), std::move(__last), __pred, __len, __p, bidirectional_iterator_tag());
 }

 template <class _AlgPolicy, class _Predicate, class _ForwardIterator, class _IterCategory>
 _LIBCPP_HIDE_FROM_ABI _ForwardIterator __stable_partition(
     _ForwardIterator __first, _ForwardIterator __last, _Predicate&& __pred, _IterCategory __iter_category) {
   return std::__stable_partition_impl<_AlgPolicy, __remove_cvref_t<_Predicate>&>(
       std::move(__first), std::move(__last), __pred, __iter_category);
 }

 template <class _ForwardIterator, class _Predicate>
 inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator
 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
   using _IterCategory = typename iterator_traits<_ForwardIterator>::iterator_category;
   return std::__stable_partition<_ClassicAlgPolicy, _Predicate&>(
       std::move(__first), std::move(__last), __pred, _IterCategory());
 }

 _LIBCPP_END_NAMESPACE_STD

 _LIBCPP_POP_MACROS

 #endif // _LIBCPP___ALGORITHM_STABLE_PARTITION_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_STABLE_PARTITION_H
	#define _LIBCPP___ALGORITHM_STABLE_PARTITION_H

	#include <__algorithm/iterator_operations.h>
	#include <__algorithm/rotate.h>
	#include <__config>
	#include <__cstddef/ptrdiff_t.h>
	#include <__iterator/advance.h>
	#include <__iterator/distance.h>
	#include <__iterator/iterator_traits.h>
	#include <__memory/destruct_n.h>
	#include <__memory/unique_ptr.h>
	#include <__memory/unique_temporary_buffer.h>
	#include <__type_traits/remove_cvref.h>
	#include <__utility/move.h>
	#include <__utility/pair.h>
	#include <new>

	#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 _AlgPolicy, class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
	_LIBCPP_HIDE_FROM_ABI _ForwardIterator __stable_partition_impl(
	_ForwardIterator __first,
	_ForwardIterator __last,
	_Predicate __pred,
	_Distance __len,
	_Pair __p,
	forward_iterator_tag __fit) {
	using _Ops = _IterOps<_AlgPolicy>;

	// *__first is known to be false
	// __len >= 1
	if (__len == 1)
	return __first;
	if (__len == 2) {
	_ForwardIterator __m = __first;
	if (__pred(*++__m)) {
	_Ops::iter_swap(__first, __m);
	return __m;
	}
	return __first;
	}
	if (__len <= __p.second) { // The buffer is big enough to use
	typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
	__destruct_n __d(0);
	unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
	// Move the falses into the temporary buffer, and the trues to the front of the line
	// Update __first to always point to the end of the trues
	value_type* __t = __p.first;
	::new ((void*)__t) value_type(_Ops::__iter_move(__first));
	__d.template __incr<value_type>();
	++__t;
	_ForwardIterator __i = __first;
	while (++__i != __last) {
	if (__pred(*__i)) {
	*__first = _Ops::__iter_move(__i);
	++__first;
	} else {
	::new ((void*)__t) value_type(_Ops::__iter_move(__i));
	__d.template __incr<value_type>();
	++__t;
	}
	}
	// All trues now at start of range, all falses in buffer
	// Move falses back into range, but don't mess up __first which points to first false
	__i = __first;
	for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void)++__i)
	*__i = _Ops::__iter_move(__t2);
	// __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
	return __first;
	}
	// Else not enough buffer, do in place
	// __len >= 3
	_ForwardIterator __m = __first;
	_Distance __len2 = __len / 2; // __len2 >= 2
	_Ops::advance(__m, __len2);
	// recurse on [__first, __m), *__first know to be false
	// F?????????????????
	// f m l
	_ForwardIterator __first_false =
	std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__first, __m, __pred, __len2, __p, __fit);
	// TTTFFFFF??????????
	// f ff m l
	// recurse on [__m, __last], except increase __m until (__m) is false, __last know to be true
	_ForwardIterator __m1 = __m;
	_ForwardIterator __second_false = __last;
	_Distance __len_half = __len - __len2;
	while (__pred(*__m1)) {
	if (++__m1 == __last)
	goto __second_half_done;
	--__len_half;
	}
	// TTTFFFFFTTTF??????
	// f ff m m1 l
	__second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__m1, __last, __pred, __len_half, __p, __fit);
	__second_half_done:
	// TTTFFFFFTTTTTFFFFF
	// f ff m sf l
	return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first;
	// TTTTTTTTFFFFFFFFFF
	// \|
	}

	template <class _AlgPolicy, class _Predicate, class _ForwardIterator>
	_LIBCPP_HIDE_FROM_ABI _ForwardIterator
	__stable_partition_impl(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag) {
	typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
	typedef typename iterator_traits<_ForwardIterator>::value_type value_type;

	const difference_type __alloc_limit = 3; // might want to make this a function of trivial assignment
	// Either prove all true and return __first or point to first false
	while (true) {
	if (__first == __last)
	return __first;
	if (!__pred(*__first))
	break;
	++__first;
	}
	// We now have a reduced range [__first, __last)
	// *__first is known to be false
	difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last);
	__unique_temporary_buffer<value_type> __unique_buf;
	pair<value_type*, ptrdiff_t> __p(0, 0);
	if (__len >= __alloc_limit) {
	__unique_buf = std::__allocate_unique_temporary_buffer<value_type>(__len);
	__p.first = __unique_buf.get();
	__p.second = __unique_buf.get_deleter().__count_;
	}
	return std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
	std::move(__first), std::move(__last), __pred, __len, __p, forward_iterator_tag());
	}

	template <class _AlgPolicy, class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
	_BidirectionalIterator __stable_partition_impl(
	_BidirectionalIterator __first,
	_BidirectionalIterator __last,
	_Predicate __pred,
	_Distance __len,
	_Pair __p,
	bidirectional_iterator_tag __bit) {
	using _Ops = _IterOps<_AlgPolicy>;

	// *__first is known to be false
	// *__last is known to be true
	// __len >= 2
	if (__len == 2) {
	_Ops::iter_swap(__first, __last);
	return __last;
	}
	if (__len == 3) {
	_BidirectionalIterator __m = __first;
	if (__pred(*++__m)) {
	_Ops::iter_swap(__first, __m);
	_Ops::iter_swap(__m, __last);
	return __last;
	}
	_Ops::iter_swap(__m, __last);
	_Ops::iter_swap(__first, __m);
	return __m;
	}
	if (__len <= __p.second) { // The buffer is big enough to use
	typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
	__destruct_n __d(0);
	unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
	// Move the falses into the temporary buffer, and the trues to the front of the line
	// Update __first to always point to the end of the trues
	value_type* __t = __p.first;
	::new ((void*)__t) value_type(_Ops::__iter_move(__first));
	__d.template __incr<value_type>();
	++__t;
	_BidirectionalIterator __i = __first;
	while (++__i != __last) {
	if (__pred(*__i)) {
	*__first = _Ops::__iter_move(__i);
	++__first;
	} else {
	::new ((void*)__t) value_type(_Ops::__iter_move(__i));
	__d.template __incr<value_type>();
	++__t;
	}
	}
	// move *__last, known to be true
	*__first = _Ops::__iter_move(__i);
	__i = ++__first;
	// All trues now at start of range, all falses in buffer
	// Move falses back into range, but don't mess up __first which points to first false
	for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void)++__i)
	*__i = _Ops::__iter_move(__t2);
	// __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
	return __first;
	}
	// Else not enough buffer, do in place
	// __len >= 4
	_BidirectionalIterator __m = __first;
	_Distance __len2 = __len / 2; // __len2 >= 2
	_Ops::advance(__m, __len2);
	// recurse on [__first, __m-1], except reduce __m-1 until (__m-1) is true, __first know to be false
	// F????????????????T
	// f m l
	_BidirectionalIterator __m1 = __m;
	_BidirectionalIterator __first_false = __first;
	_Distance __len_half = __len2;
	while (!__pred(*--__m1)) {
	if (__m1 == __first)
	goto __first_half_done;
	--__len_half;
	}
	// F???TFFF?????????T
	// f m1 m l
	__first_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__first, __m1, __pred, __len_half, __p, __bit);
	__first_half_done:
	// TTTFFFFF?????????T
	// f ff m l
	// recurse on [__m, __last], except increase __m until (__m) is false, __last know to be true
	__m1 = __m;
	_BidirectionalIterator __second_false = __last;
	++__second_false;
	__len_half = __len - __len2;
	while (__pred(*__m1)) {
	if (++__m1 == __last)
	goto __second_half_done;
	--__len_half;
	}
	// TTTFFFFFTTTF?????T
	// f ff m m1 l
	__second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__m1, __last, __pred, __len_half, __p, __bit);
	__second_half_done:
	// TTTFFFFFTTTTTFFFFF
	// f ff m sf l
	return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first;
	// TTTTTTTTFFFFFFFFFF
	// \|
	}

	template <class _AlgPolicy, class _Predicate, class _BidirectionalIterator>
	_LIBCPP_HIDE_FROM_ABI _BidirectionalIterator __stable_partition_impl(
	_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, bidirectional_iterator_tag) {
	typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
	typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
	const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment
	// Either prove all true and return __first or point to first false
	while (true) {
	if (__first == __last)
	return __first;
	if (!__pred(*__first))
	break;
	++__first;
	}
	// __first points to first false, everything prior to __first is already set.
	// Either prove [__first, __last) is all false and return __first, or point __last to last true
	do {
	if (__first == --__last)
	return __first;
	} while (!__pred(*__last));
	// We now have a reduced range [__first, __last]
	// *__first is known to be false
	// *__last is known to be true
	// __len >= 2
	difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last) + 1;
	__unique_temporary_buffer<value_type> __unique_buf;
	pair<value_type*, ptrdiff_t> __p(0, 0);
	if (__len >= __alloc_limit) {
	__unique_buf = std::__allocate_unique_temporary_buffer<value_type>(__len);
	__p.first = __unique_buf.get();
	__p.second = __unique_buf.get_deleter().__count_;
	}
	return std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
	std::move(__first), std::move(__last), __pred, __len, __p, bidirectional_iterator_tag());
	}

	template <class _AlgPolicy, class _Predicate, class _ForwardIterator, class _IterCategory>
	_LIBCPP_HIDE_FROM_ABI _ForwardIterator __stable_partition(
	_ForwardIterator __first, _ForwardIterator __last, _Predicate&& __pred, _IterCategory __iter_category) {
	return std::__stable_partition_impl<_AlgPolicy, __remove_cvref_t<_Predicate>&>(
	std::move(__first), std::move(__last), __pred, __iter_category);
	}

	template <class _ForwardIterator, class _Predicate>
	inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator
	stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
	using _IterCategory = typename iterator_traits<_ForwardIterator>::iterator_category;
	return std::__stable_partition<_ClassicAlgPolicy, _Predicate&>(
	std::move(__first), std::move(__last), __pred, _IterCategory());
	}

	_LIBCPP_END_NAMESPACE_STD

	_LIBCPP_POP_MACROS

	#endif // _LIBCPP___ALGORITHM_STABLE_PARTITION_H