|
partition
function template
<algorithm>
template <class BidirectionalIterator, class Predicate>
BidirectionalIterator partition ( BidirectionalIterator first,
BidirectionalIterator last, Predicate pred );
Partition range in two
Rearranges the elements in the range [first,last), in such a way that all the elements for which pred returns true precede all those for which it returns false. The iterator returned points to the first element of the second group.
The relative ordering within each group is not necessarily the same as before the call. See function stable_partition for a function with a similar behavior and stability in the the ordering.
The behavior of this function template is equivalent to:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
template <class BidirectionalIterator, class Predicate>
BidirectionalIterator partition ( BidirectionalIterator first,
BidirectionalIterator last, Predicate pred )
{
while (true)
{
while (first!=last && pred(*first)) ++first;
if (first==last--) break;
while (first!=last && !pred(*last)) --last;
if (first==last) break;
swap (*first++,*last);
}
return first;
}
|
Parameters
- first, last
- Bidirectional iterators to the initial and final positions of the sequence to be partitioned. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
- pred
- Unary predicate taking an element in the range as argument, and returning a value indicating the falsehood (with false, or a zero value) or truth (true, or non-zero) of some condition applied to it. This can either be a pointer to a function or an object whose class overloads operator().
Return value
An iterator that points to the first element of the second group of elements. For all the elements in this second group, pred return false.
Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
// partition algorithm example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool IsOdd (int i) { return (i%2)==1; }
int main () {
vector<int> myvector;
vector<int>::iterator it, bound;
// set some values:
for (int i=1; i<10; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9
bound = partition (myvector.begin(), myvector.end(), IsOdd);
// print out content:
cout << "odd members:";
for (it=myvector.begin(); it!=bound; ++it)
cout << " " << *it;
cout << "\neven members:";
for (it=bound; it!=myvector.end(); ++it)
cout << " " << *it;
cout << endl;
return 0;
}
|
A possible output:
odd members: 1 9 3 7 5
even members: 6 4 8 2
|
Complexity
As many applications of pred as the length of the range [first,last) plus up to half as many swap operations (worst-case).
See also
| reverse | Reverse range (function template) |
| rotate | Rotate elements in range (function template) |
| find_if | Find element in range (function template) |
| swap | Exchange values of two objects (function template) |
|