28 Algorithms library [algorithms]

28.7 Sorting and related operations [alg.sorting]

28.7.4 Partitions [alg.partitions]

template <class InputIterator, class Predicate> 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);

1
#

Requires: For the overload with no ExecutionPolicy, InputIterator's value type shall be convertible to Predicate's argument type. For the overload with an ExecutionPolicy, ForwardIterator's value type shall be convertible to Predicate's argument type.

2
#

Returns: true if [first, last) is empty or if [first, last) is partitioned by pred, i.e. if all elements that satisfy pred appear before those that do not.

3
#

Complexity: Linear. At most last - first applications of pred.

template<class ForwardIterator, class Predicate> 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);

4
#

Requires: ForwardIterator shall satisfy the requirements of ValueSwappable.

5
#

Effects: Places all the elements in the range [first, last) that satisfy pred before all the elements that do not satisfy it.

6
#

Returns: An iterator i such that for every iterator j in the range [first, i) pred(*j) != false, and for every iterator k in the range [i, last), pred(*k) == false.

7
#

Complexity: Let N=last - first:

  • (7.1)

    For the overload with no ExecutionPolicy, exactly N applications of the predicate. At most N/2 swaps if ForwardIterator meets the BidirectionalIterator requirements and at most N swaps otherwise.

  • (7.2)

    For the overload with an ExecutionPolicy, O(NlogN) swaps and O(N) 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);

8
#

Requires: BidirectionalIterator shall satisfy the requirements of ValueSwappable. The type of *first shall satisfy the requirements of MoveConstructible and of MoveAssignable.

9
#

Effects: Places all the elements in the range [first, last) that satisfy pred before all the elements that do not satisfy it.

10
#

Returns: An iterator i such that for every iterator j in the range [first, i), pred(*j) != false, and for every iterator k in the range [i, last), pred(*k) == false. The relative order of the elements in both groups is preserved.

11
#

Complexity: Let N = last - first:

  • (11.1)

    For the overload with no ExecutionPolicy, at most NlogN swaps, but only O(N) swaps if there is enough extra memory. Exactly N applications of the predicate.

  • (11.2)

    For the overload with an ExecutionPolicy, O(NlogN) swaps and O(N) applications of the predicate.

template <class InputIterator, class OutputIterator1, class OutputIterator2, class Predicate> 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);

12
#

Requires:

  • (12.1)

    For the overload with no ExecutionPolicy, InputIterator's value type shall be CopyAssignable (Table 26), and shall be writable ([iterator.requirements.general]) to the out_­true and out_­false OutputIterators, and shall be convertible to Predicate's argument type.

  • (12.2)

    For the overload with an ExecutionPolicy, ForwardIterator's value type shall be CopyAssignable, and shall be writable to the out_­true and out_­false ForwardIterators, and shall be convertible to Predicate's argument type. [ Note: There may be a performance cost if ForwardIterator's value type is not CopyConstructible.  — end note ]

  • (12.3)

    For both overloads, the input range shall not overlap with either of the output ranges.

13
#

Effects: For each iterator i in [first, last), copies *i to the output range beginning with out_­true if pred(*i) is true, or to the output range beginning with out_­false otherwise.

14
#

Returns: A pair p such that p.first is the end of the output range beginning at out_­true and p.second is the end of the output range beginning at out_­false.

15
#

Complexity: Exactly last - first applications of pred.

template<class ForwardIterator, class Predicate> ForwardIterator partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);

16
#

Requires: ForwardIterator's value type shall be convertible to Predicate's argument type. [first, last) shall be partitioned by pred, i.e. all elements that satisfy pred shall appear before those that do not.

17
#

Returns: An iterator mid such that all_­of(first, mid, pred) and none_­of(mid, last, pred) are both true.

18
#

Complexity: O(log(last - first)) applications of pred.