Difference between revisions of "cpp/algorithm/partition"
From cppreference.com
Lukequaint (Talk | contribs) m (Change function to lambda and add std::iota) |
(one example per page (merged the two that were here), slightly shorten) |
||
| Line 54: | Line 54: | ||
}} | }} | ||
| − | ===Example | + | ===Example=== |
{{example | {{example | ||
| | | | ||
| code= | | code= | ||
#include <algorithm> | #include <algorithm> | ||
| − | |||
#include <iostream> | #include <iostream> | ||
#include <iterator> | #include <iterator> | ||
#include <vector> | #include <vector> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
#include <forward_list> | #include <forward_list> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
template <class ForwardIt> | template <class ForwardIt> | ||
| Line 113: | Line 68: | ||
{ | { | ||
if(first == last) return; | if(first == last) return; | ||
| − | + | auto pivot = *std::next(first, std::distance(first,last)/2); | |
| − | auto pivot = * | + | |
| − | + | ||
ForwardIt middle1 = std::partition(first, last, | ForwardIt middle1 = std::partition(first, last, | ||
[pivot](const auto& em){ return em < pivot; }); | [pivot](const auto& em){ return em < pivot; }); | ||
ForwardIt middle2 = std::partition(middle1, last, | ForwardIt middle2 = std::partition(middle1, last, | ||
[pivot](const auto& em){ return !(pivot < em); }); | [pivot](const auto& em){ return !(pivot < em); }); | ||
| − | |||
quicksort(first, middle1); | quicksort(first, middle1); | ||
quicksort(middle2, last); | quicksort(middle2, last); | ||
} | } | ||
| − | + | ||
| − | + | ||
int main() | int main() | ||
{ | { | ||
| − | std::forward_list<int> fl = {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92}; | + | std::vector<int> v = {0,1,2,3,4,5,6,7,8,9}; |
| − | + | std::cout << "Original vector:\n "; | |
| − | quicksort(std::begin(fl), std::end(fl)); | + | for (int elem : v) std::cout << elem << ' '; |
| − | + | ||
| − | + | auto it = std::partition(v.begin(), v.end(), [](int i){return i % 2 == 0;}); | |
| − | + | ||
| + | std::cout << "\nPartitioned vector:\n "; | ||
| + | std::copy(std::begin(v), it, std::ostream_iterator<int>(std::cout, " ")); | ||
| + | std::cout << " * "; | ||
| + | std::copy(it, std::end(v), std::ostream_iterator<int>(std::cout, " ")); | ||
| + | |||
| + | std::forward_list<int> fl = {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92}; | ||
| + | std::cout << "\nUnsorted list:\n "; | ||
| + | for(int n : fl) std::cout << n << ' '; | ||
| + | std::cout << '\n'; | ||
| + | |||
| + | quicksort(std::begin(fl), std::end(fl)); | ||
| + | std::cout << "Sorted using quicksort:\n "; | ||
| + | for(int fi : fl) std::cout << fi << ' '; | ||
| + | std::cout << '\n'; | ||
} | } | ||
| output = | | output = | ||
| − | -8 -5 -4 -4 1 1 1 2 3 5 6 30 64 92 | + | Original vector: |
| + | 0 1 2 3 4 5 6 7 8 9 | ||
| + | Partitioned vector: | ||
| + | 0 8 2 6 4 * 5 3 7 1 9 | ||
| + | Unsorted list: | ||
| + | 1 30 -4 3 5 -4 1 6 -8 2 -5 64 1 92 | ||
| + | Sorted using quicksort: | ||
| + | -8 -5 -4 -4 1 1 1 2 3 5 6 30 64 92 | ||
}} | }} | ||
Revision as of 02:52, 14 May 2015
| Defined in header <algorithm>
|
||
| template< class BidirIt, class UnaryPredicate > BidirIt partition( BidirIt first, BidirIt last, UnaryPredicate p ); |
(until C++11) | |
| template< class ForwardIt, class UnaryPredicate > ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p ); |
(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 std::distance(first,last) applications of the predicate and at most std::distance(first,last) swaps. If ForwardIt meets the requirements of Template:concept at most std::distance(first,last)/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::iter_swap(first++, last); } return first; } |
Example
Run this code
#include <algorithm> #include <iostream> #include <iterator> #include <vector> #include <forward_list> template <class ForwardIt> void quicksort(ForwardIt first, ForwardIt last) { if(first == last) return; auto pivot = *std::next(first, std::distance(first,last)/2); ForwardIt middle1 = std::partition(first, last, [pivot](const auto& em){ return em < pivot; }); ForwardIt middle2 = std::partition(middle1, last, [pivot](const auto& em){ return !(pivot < em); }); quicksort(first, middle1); quicksort(middle2, last); } int main() { std::vector<int> v = {0,1,2,3,4,5,6,7,8,9}; std::cout << "Original vector:\n "; for (int elem : v) std::cout << elem << ' '; auto it = std::partition(v.begin(), v.end(), [](int i){return i % 2 == 0;}); std::cout << "\nPartitioned vector:\n "; std::copy(std::begin(v), it, std::ostream_iterator<int>(std::cout, " ")); std::cout << " * "; std::copy(it, std::end(v), std::ostream_iterator<int>(std::cout, " ")); std::forward_list<int> fl = {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92}; std::cout << "\nUnsorted list:\n "; for(int n : fl) std::cout << n << ' '; std::cout << '\n'; quicksort(std::begin(fl), std::end(fl)); std::cout << "Sorted using quicksort:\n "; for(int fi : fl) std::cout << fi << ' '; std::cout << '\n'; }
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
Unsorted list:
1 30 -4 3 5 -4 1 6 -8 2 -5 64 1 92
Sorted using quicksort:
-8 -5 -4 -4 1 1 1 2 3 5 6 30 64 92See 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) |
