92 lines · c
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___ALGORITHM_PARTITION_H10#define _LIBCPP___ALGORITHM_PARTITION_H11 12#include <__algorithm/iterator_operations.h>13#include <__config>14#include <__iterator/iterator_traits.h>15#include <__type_traits/remove_cvref.h>16#include <__utility/move.h>17#include <__utility/pair.h>18 19#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)20# pragma GCC system_header21#endif22 23_LIBCPP_PUSH_MACROS24#include <__undef_macros>25 26_LIBCPP_BEGIN_NAMESPACE_STD27 28template <class _Predicate, class _AlgPolicy, class _ForwardIterator, class _Sentinel>29_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_ForwardIterator, _ForwardIterator>30__partition_impl(_ForwardIterator __first, _Sentinel __last, _Predicate __pred, forward_iterator_tag) {31 while (true) {32 if (__first == __last)33 return std::make_pair(__first, __first);34 if (!__pred(*__first))35 break;36 ++__first;37 }38 39 _ForwardIterator __p = __first;40 while (++__p != __last) {41 if (__pred(*__p)) {42 _IterOps<_AlgPolicy>::iter_swap(__first, __p);43 ++__first;44 }45 }46 return std::make_pair(std::move(__first), std::move(__p));47}48 49template <class _Predicate, class _AlgPolicy, class _BidirectionalIterator, class _Sentinel>50_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_BidirectionalIterator, _BidirectionalIterator>51__partition_impl(_BidirectionalIterator __first, _Sentinel __sentinel, _Predicate __pred, bidirectional_iterator_tag) {52 _BidirectionalIterator __original_last = _IterOps<_AlgPolicy>::next(__first, __sentinel);53 _BidirectionalIterator __last = __original_last;54 55 while (true) {56 while (true) {57 if (__first == __last)58 return std::make_pair(std::move(__first), std::move(__original_last));59 if (!__pred(*__first))60 break;61 ++__first;62 }63 do {64 if (__first == --__last)65 return std::make_pair(std::move(__first), std::move(__original_last));66 } while (!__pred(*__last));67 _IterOps<_AlgPolicy>::iter_swap(__first, __last);68 ++__first;69 }70}71 72template <class _AlgPolicy, class _ForwardIterator, class _Sentinel, class _Predicate, class _IterCategory>73inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_ForwardIterator, _ForwardIterator>74__partition(_ForwardIterator __first, _Sentinel __last, _Predicate&& __pred, _IterCategory __iter_category) {75 return std::__partition_impl<__remove_cvref_t<_Predicate>&, _AlgPolicy>(76 std::move(__first), std::move(__last), __pred, __iter_category);77}78 79template <class _ForwardIterator, class _Predicate>80inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator81partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {82 using _IterCategory = typename iterator_traits<_ForwardIterator>::iterator_category;83 auto __result = std::__partition<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __pred, _IterCategory());84 return __result.first;85}86 87_LIBCPP_END_NAMESPACE_STD88 89_LIBCPP_POP_MACROS90 91#endif // _LIBCPP___ALGORITHM_PARTITION_H92