std::partition

Template:cpp/algorithm/sidebar Template:ddcl list begin <tr class="t-dsc-header">

<td>

Defined in header <algorithm>

</td>

<td></td> <td></td> </tr> <tr class="t-dcl ">

<td >

template< class BidirectionalIterator, class UnaryPredicate >

BidirectionalIterator partition( BidirectionalIterator first, BidirectionalIterator last,
                                 UnaryPredicate p );
template< class ForwardIterator, class UnaryPredicate >
ForwardIterator partition( ForwardIterator first, ForwardIterator last,

                                 UnaryPredicate p );

</td>

<td class="t-dcl-nopad"> </td> <td > (until C++11)

(since C++11) </td> </tr> Template:ddcl list end

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.

Parameters

first, last	-	the range of elements to reorder
p	-	unary predicate which returns ​true if the element should be ordered before other elements. The expression p(v) must be convertible to bool for every argument v of type (possibly const) VT, where VT is the value type of ForwardIterator, regardless of value category, and must not modify v. Thus, a parameter type of VT&is not allowed, nor is VT unless for VT a move is equivalent to a copy(since C++11). ​

Return value

Iterator to the first element of the second group

Complexity

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

Example

Run this code

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>
 
bool is_even(int i) { return i % 2 == 0; }
 
int main()
{
    std::vector<int> v;
    for (int i = 0; i < 10; ++i) v.push_back(i);
 
    std::cout << "Original vector:\n    ";
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
 
    // Partition the vector
    std::vector<int>::iterator p =
        std::partition(v.begin(), v.end(), std::ptr_fun(is_even));
 
    std::cout << "\nPartitioned vector:\n    ";
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nBefore partition:\n    ";
    std::copy(v.begin(), p,       std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nAfter partition:\n    ";
    std::copy(p,         v.end(), std::ostream_iterator<int>(std::cout, " "));
}

Possible output:

Original vector:
    0 1 2 3 4 5 6 7 8 9 
Partitioned vector:
    0 8 2 6 4 5 3 7 1 9 
Before partition:
    0 8 2 6 4 
After partition:
    5 3 7 1 9

See also

Template:cpp/algorithm/dcl list is partitionedTemplate:cpp/algorithm/dcl list stable partition