24 Algorithms library [algorithms]

24.7 Sorting and related operations [alg.sorting]

24.7.4 Partitions [alg.partitions]

template<class InputIterator, class Predicate> constexpr bool is_partitioned(InputIterator first, InputIterator last, Predicate pred); template<class ExecutionPolicy, class ForwardIterator, class Predicate> bool is_partitioned(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Predicate pred); namespace ranges { template<InputIterator I, Sentinel<I> S, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> constexpr bool is_partitioned(I first, S last, Pred pred, Proj proj = {}); template<InputRange R, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<R>, Proj>> Pred> constexpr bool is_partitioned(R&& r, Pred pred, Proj proj = {}); }
Let proj be identity{} for the overloads with no parameter named proj.
Returns: true if and only if the elements e of [first, last) are partitioned with respect to the expression bool(invoke(pred, invoke(proj, e))).
Complexity: Linear.
At most last - first applications of pred and proj.
template<class ForwardIterator, class Predicate> constexpr ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred); template<class ExecutionPolicy, class ForwardIterator, class Predicate> ForwardIterator partition(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Predicate pred); namespace ranges { template<Permutable I, Sentinel<I> S, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> constexpr I partition(I first, S last, Pred pred, Proj proj = {}); template<ForwardRange R, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<R>, Proj>> Pred> requires Permutable<iterator_t<R>> constexpr safe_iterator_t<R> partition(R&& r, Pred pred, Proj proj = {}); }
Let proj be identity{} for the overloads with no parameter named proj and let E(x) be bool(invoke(​pred, invoke(proj, x))).
Requires: For the overloads in namespace std, ForwardIterator shall meet the Cpp17ValueSwappable requirements ([swappable.requirements]).
Effects: Places all the elements e in [first, last) that satisfy E(e) before all the elements that do not.
Returns: An iterator i such that is true for every iterator j in [first, i) and false for every iterator j in [i, last).
Complexity: Let :
  • For the overload with no ExecutionPolicy, exactly N applications of the predicate and projection.
    At most swaps if the type of first meets the Cpp17BidirectionalIterator requirements for the overloads in namespace std or models BidirectionalIterator for the overloads in namespace ranges, and at most N swaps otherwise.
  • For the overload with an ExecutionPolicy, swaps and applications of the predicate.
template<class BidirectionalIterator, class Predicate> BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred); template<class ExecutionPolicy, class BidirectionalIterator, class Predicate> BidirectionalIterator stable_partition(ExecutionPolicy&& exec, BidirectionalIterator first, BidirectionalIterator last, Predicate pred); namespace ranges { template<BidirectionalIterator I, Sentinel<I> S, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> requires Permutable<I> I stable_partition(I first, S last, Pred pred, Proj proj = {}); template<BidirectionalRange R, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<R>, Proj>> Pred> requires Permutable<iterator_t<R>> safe_iterator_t<R> stable_partition(R&& r, Pred pred, Proj proj = {}); }
Let proj be identity{} for the overloads with no parameter named proj and let E(x) be bool(invoke(​pred, invoke(proj, x))).
Requires: For the overloads in namespace std, BidirectionalIterator shall meet the Cpp17ValueSwappable requirements ([swappable.requirements]) and the type of *first shall meet the Cpp17MoveConstructible (Table 26) and Cpp17MoveAssignable (Table 28) requirements.
Effects: Places all the elements e in [first, last) that satisfy E(e) before all the elements that do not.
The relative order of the elements in both groups is preserved.
Returns: An iterator i such that for every iterator j in [first, i), is true, and for every iterator j in the range [i, last), is false,
Complexity: Let N = last - first:
  • For the overloads with no ExecutionPolicy, at most swaps, but only swaps if there is enough extra memory.
    Exactly N applications of the predicate and projection.
  • For the overload with an ExecutionPolicy, swaps and applications of the predicate.
template<class InputIterator, class OutputIterator1, class OutputIterator2, class Predicate> constexpr pair<OutputIterator1, OutputIterator2> partition_copy(InputIterator first, InputIterator last, OutputIterator1 out_true, OutputIterator2 out_false, Predicate pred); template<class ExecutionPolicy, class ForwardIterator, class ForwardIterator1, class ForwardIterator2, class Predicate> pair<ForwardIterator1, ForwardIterator2> partition_copy(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, ForwardIterator1 out_true, ForwardIterator2 out_false, Predicate pred); namespace ranges { template<InputIterator I, Sentinel<I> S, WeaklyIncrementable O1, WeaklyIncrementable O2, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> requires IndirectlyCopyable<I, O1> && IndirectlyCopyable<I, O2> constexpr partition_copy_result<I, O1, O2> partition_copy(I first, S last, O1 out_true, O2 out_false, Pred pred, Proj proj = {}); template<InputRange R, WeaklyIncrementable O1, WeaklyIncrementable O2, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<R>, Proj>> Pred> requires IndirectlyCopyable<iterator_t<R>, O1> && IndirectlyCopyable<iterator_t<R>, O2> constexpr partition_copy_result<safe_iterator_t<R>, O1, O2> partition_copy(R&& r, O1 out_true, O2 out_false, Pred pred, Proj proj = {}); }
Let proj be identity{} for the overloads with no parameter named proj and let E(x) be bool(invoke(​pred, invoke(proj, x))).
Requires: The input range and output ranges shall not overlap.
For the overloads in namespace std, the expression *first shall be writable ([iterator.requirements.general]) to out_­true and out_­false.
[Note
:
For the overload with an ExecutionPolicy, there may be a performance cost if first's value type does not meet the Cpp17CopyConstructible requirements.
end note
]
Effects: For each iterator i in [first, last), copies *i to the output range beginning with out_­true if is true, or to the output range beginning with out_­false otherwise.
Returns: Let o1 be the end of the output range beginning at out_­true, and o2 the end of the output range beginning at out_­false.
Returns
  • {o1, o2} for the overloads in namespace std, or
  • {last, o1, o2} for the overloads in namespace ranges.
Complexity: Exactly last - first applications of pred and proj.
template<class ForwardIterator, class Predicate> constexpr ForwardIterator partition_point(ForwardIterator first, ForwardIterator last, Predicate pred); namespace ranges { template<ForwardIterator I, Sentinel<I> S, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> constexpr I partition_point(I first, S last, Pred pred, Proj proj = {}); template<ForwardRange R, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<R>, Proj>> Pred> constexpr safe_iterator_t<R> partition_point(R&& r, Pred pred, Proj proj = {}); }
Let proj be identity{} for the overloads with no parameter named proj and let E(x) be bool(invoke(​pred, invoke(proj, x))).
Requires: The elements e of [first, last) shall be partitioned with respect to E(e).
Returns: An iterator mid such that is true for all iterators i in [first, mid), and false for all iterators i in [mid, last)
Complexity: applications of pred and proj.