std::partition

From Cppreference

Reorders the elements in the range [first, last) in such a way that all elements for which the predicate p returns true precede the elements for which predicate p returns false. Relative order of the elements is not preserved.

[edit] Parameters

[edit] Return value

iterator to the first element of the second group

[edit] Complexity

Exactly last-first applications of the predicate and at most (last-first)/2 swaps if ForwardIterator meets the requirements of BidirectionalIterator, otherwise at most last-first swaps.

[edit] Equivalent function

template<class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator partition(BidirectionalIterator first,
                                BidirectionalIterator last,
                                UnaryPredicate p)
{
    while (1) {
        while ((first != last) && p(*first)) {
            ++first;
        }
        if (first == last--) break;
        while ((first != last) && !p(*last)) {
            --last;
        }
        if (first == last) break;
        std::swap (*first++,*last);
    }
    return first;
}

[edit] Example

[edit] See also