23 Algorithms library [algorithms]

23.7 Sorting and related operations [alg.sorting]

23.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);
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 the elements e of [first, last) are partitioned with respect to the expression pred(e).
3
#
Complexity: Linear.
At most last - first applications of pred.
🔗
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);
4
#
Requires: ForwardIterator shall satisfy the Cpp17ValueSwappable requirements ([swappable.requirements]).
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 :
  • (7.1)
    For the overload with no ExecutionPolicy, exactly N applications of the predicate.
    At most swaps if ForwardIterator meets the Cpp17BidirectionalIterator requirements and at most N swaps otherwise.
  • (7.2)
    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);
8
#
Requires: BidirectionalIterator shall satisfy the Cpp17ValueSwappable requirements ([swappable.requirements]).
The type of *first shall satisfy the Cpp17MoveConstructible (Table 25) and Cpp17MoveAssignable (Table 27) requirements.
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 swaps, but only swaps if there is enough extra memory.
    Exactly N applications of the predicate.
  • (11.2)
    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);
12
#
Requires:
  • (12.1)
    For the overload with no ExecutionPolicy, InputIterator's value type shall be Cpp17CopyAssignable (Table 28), 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 Cpp17CopyAssignable, 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 Cpp17CopyConstructible.
    — 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> constexpr ForwardIterator partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
16
#
Requires: ForwardIterator's value type shall be convertible to Predicate's argument type.
The elements e of [first, last) shall be partitioned with respect to the expression pred(e).
17
#
Returns: An iterator mid such that all_­of(first, mid, pred) and none_­of(mid, last, pred) are both true.
18
#
Complexity: applications of pred.