Difference between revisions of "cpp/algorithm/partition"
m (Shorten template names. Use {{lc}} where appropriate.) |
m (Update links.) |
||
| Line 97: | Line 97: | ||
===See also=== | ===See also=== | ||
{{dsc begin}} | {{dsc begin}} | ||
| − | {{dsc inc | cpp/algorithm/ | + | {{dsc inc | cpp/algorithm/dsc is_partitioned}} |
| − | {{dsc inc | cpp/algorithm/ | + | {{dsc inc | cpp/algorithm/dsc stable_partition}} |
{{dsc end}} | {{dsc end}} | ||
Revision as of 21:45, 31 May 2013
| Defined in header <algorithm>
|
||
| template< class BidirIt, class UnaryPredicate > BidirectionalIterator partition( BidirIt first, BidirIt last, |
(until C++11) (since C++11) |
|
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.
Contents |
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 |
| Type requirements
Template:par req concept Template:par req concept Template:par req concept | ||
Return value
Iterator to the first element of the second group.
Complexity
Exactly last-first applications of the predicate and at most last-first swaps. If ForwardIt meets the requirements of Template:concept at most (last-first)/2 swaps are done.
Possible implementation
template<class BidirIt, class UnaryPredicate> BidirIt partition(BidirIt first, BidirIt 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; } |
Example
#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 9See also
| (C++11) |
determines if the range is partitioned by the given predicate (function template) |
| divides elements into two groups while preserving their relative order (function template) |
