[alg.partitions] (original) (raw)

25 Algorithms library [algorithms]

25.8 Sorting and related operations [alg.sorting]

25.8.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);template<input_­iterator I, sentinel_­for<I> S, class Proj = identity,indirect_­unary_­predicate<projected<I, Proj>> Pred> constexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {});template<input_­range R, class Proj = identity,indirect_­unary_­predicate<projected<iterator_t<R>, Proj>> Pred> constexpr bool ranges::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 expressionbool(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);template<permutable I, sentinel_­for<I> S, class Proj = identity,indirect_­unary_­predicate<projected<I, Proj>> Pred> constexpr subrange<I> ranges::partition(I first, S last, Pred pred, Proj proj = {});template<forward_­range R, class Proj = identity,indirect_­unary_­predicate<projected<iterator_t<R>, Proj>> Pred> requires permutable<iterator_t<R>> constexpr borrowed_subrange_t<R> ranges::partition(R&& r, Pred pred, Proj proj = {});

Let proj be identity{}for the overloads with no parameter named projand let E(x) be bool(invoke(​pred, invoke(proj, x))).

Preconditions:For the overloads in namespace std,ForwardIterator meets 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:Let i be an iterator such that istrue for every iterator j in [first, i) andfalse for every iterator j in [i, last).

Returns:

• i for the overloads in namespace std.
• {i, last} for the overloads in namespace ranges.

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 bidirectional_­iterator 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);template<bidirectional_­iterator I, sentinel_­for<I> S, class Proj = identity,indirect_­unary_­predicate<projected<I, Proj>> Pred> requires permutable<I> subrange<I> ranges::stable_partition(I first, S last, Pred pred, Proj proj = {});template<bidirectional_­range R, class Proj = identity,indirect_­unary_­predicate<projected<iterator_t<R>, Proj>> Pred> requires permutable<iterator_t<R>> borrowed_subrange_t<R> ranges::stable_partition(R&& r, Pred pred, Proj proj = {});

Let proj be identity{}for the overloads with no parameter named projand let E(x) be bool(invoke(​pred, invoke(proj, x))).

Preconditions:For the overloads in namespace std,BidirectionalIterator meets the Cpp17ValueSwappable requirements ([swappable.requirements]) and the type of *first meets the Cpp17MoveConstructible (Table 28) andCpp17MoveAssignable (Table 30) 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:Let i be an iterator such that for every iterator j in [first, i), is true, and for every iterator j in the range [i, last), is false.

Returns:

• i for the overloads in namespace std.
• {i, last} for the overloads in namespace ranges.

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);template<input_­iterator I, sentinel_­for<I> S, weakly_­incrementable O1, weakly_­incrementable O2,class Proj = identity, indirect_­unary_­predicate<projected<I, Proj>> Pred> requires indirectly_­copyable<I, O1> && indirectly_­copyable<I, O2> constexpr ranges::partition_copy_result<I, O1, O2> ranges::partition_copy(I first, S last, O1 out_true, O2 out_false, Pred pred, Proj proj = {});template<input_­range R, weakly_­incrementable O1, weakly_­incrementable O2,class Proj = identity,indirect_­unary_­predicate<projected<iterator_t<R>, Proj>> Pred> requires indirectly_­copyable<iterator_t<R>, O1> && indirectly_­copyable<iterator_t<R>, O2> constexpr ranges::partition_copy_result<borrowed_iterator_t<R>, O1, O2> ranges::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))).

Preconditions:The input range and output ranges do not overlap.

[ 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_­trueif 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.
• {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);template<forward_­iterator I, sentinel_­for<I> S, class Proj = identity,indirect_­unary_­predicate<projected<I, Proj>> Pred> constexpr I ranges::partition_point(I first, S last, Pred pred, Proj proj = {});template<forward_­range R, class Proj = identity,indirect_­unary_­predicate<projected<iterator_t<R>, Proj>> Pred> constexpr borrowed_iterator_t<R> ranges::partition_point(R&& r, Pred pred, Proj proj = {});

Let proj be identity{}for the overloads with no parameter named projand let E(x) be bool(invoke(​pred, invoke(proj, x))).

Preconditions:The elements e of [first, last)are partitioned with respect to E(e).

Returns:An iterator midsuch that is truefor all iterators i in [first, mid), andfalse for all iterators i in [mid, last).

Complexity: applications of pred and proj.