```
template <class InputIterator, class Predicate>
bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);
```

*Requires:* InputIterator's value type shall be convertible to Predicate's argument type.

*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.

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

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

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

*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.

*Requires:*
ForwardIterator shall satisfy the requirements of
ValueSwappable ([swappable.requirements]).

*Complexity:* If ForwardIterator meets the requirements for a BidirectionalIterator, at most
(last - first) / 2 swaps are done; otherwise at most last - first swaps
are done. Exactly last - first applications of the predicate are done.

```
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator
stable_partition(BidirectionalIterator first,
BidirectionalIterator last, Predicate pred);
```

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

*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.

*Requires:*
BidirectionalIterator shall satisfy the requirements of
ValueSwappable ([swappable.requirements]). The type
of *first shall satisfy the requirements of
MoveConstructible (Table [moveconstructible]) and of
MoveAssignable (Table [moveassignable]).

*Complexity:*
At most
(last - first) * log(last - first)
swaps, but only linear number of swaps if there is enough extra memory.
Exactly
last - first
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);
```

*Requires:* InputIterator's value type shall be CopyAssignable, and shall be
writable to the out_true and out_false OutputIterators, and shall be
convertible to Predicate's argument type. The input range shall not overlap with
either of the output ranges.

*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.

*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.

*Complexity:* Exactly last - first applications of pred.

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

*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.

*Returns:* An iterator mid such that all_of(first, mid, pred) and none_of(mid, last, pred) are both true.

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