Namespaces
Variants
Views
Actions

Difference between revisions of "cpp/algorithm/partition"

From cppreference.com
< cpp‎ | algorithm
m (fmt)
m (Change function to lambda and add std::iota)
Line 63: Line 63:
 
#include <iterator>
 
#include <iterator>
 
#include <vector>
 
#include <vector>
−
 
−
bool is_even(int i) { return i % 2 == 0; }
 
  
 
int main()
 
int main()
 
{
 
{
−
     std::vector<int> v;
+
     std::vector<int> v(10);
−
     for (int i = 0; i < 10; ++i) v.push_back(i);
+
     std::iota(std::begin(v), std::end(v), 0);
 
      
 
      
 
     std::cout << "Original vector:\n    ";
 
     std::cout << "Original vector:\n    ";
Line 75: Line 73:
 
      
 
      
 
     // Partition the vector
 
     // Partition the vector
−
     auto it = std::partition(v.begin(), v.end(), is_even);
+
     auto it = std::partition(v.begin(), v.end(), [](int i){return i % 2 == 0;});
 
      
 
      
 
     std::cout << "\nPartitioned vector:\n    ";
 
     std::cout << "\nPartitioned vector:\n    ";

Revision as of 00:40, 14 May 2015

 
C++
 
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy, ranges::sort, ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
(C++11)                (C++11)(C++11)

Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17)(C++11)
(C++20)(C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
partition
(C++11)  
Sorting operations
Binary search operations
(on partitioned ranges)
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
Minimum/maximum operations
(C++11)
(C++17)
Lexicographical comparison operations
(C++20)
Permutation operations
C library
Numeric operations
Operations on uninitialized memory
 
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 v of type (possibly const) VT, where VT is the value type of ForwardIt, 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). ​

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 1

Run this code
#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>
 
int main()
{
    std::vector<int> v(10);
    std::iota(std::begin(v), std::end(v), 0);
 
    std::cout << "Original vector:\n    ";
    for (int elem : v) std::cout << elem << ' ';
 
    // Partition the vector
    auto it = std::partition(v.begin(), v.end(), [](int i){return i % 2 == 0;});
 
    std::cout << "\nPartitioned vector:\n    ";
    std::copy(std::begin(v), std::end(v), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nBefore partition:\n    ";
    std::copy(std::begin(v), it, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nAfter partition:\n    ";
    std::copy(it, std::end(v), 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

Example 2

Run this code
#include <iterator>
#include <algorithm>
#include <forward_list>
#include <iostream>
 
template <class ForwardIt>
 ForwardIt choose_pivot(ForwardIt first, ForwardIt last)
 {
   return std::next(first, std::distance(first,last)/2);
 }
 
template <class ForwardIt>
 void quicksort(ForwardIt first, ForwardIt last)
 {
    if(first == last) return;
 
    auto pivot = *choose_pivot(first,last);
 
    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::forward_list<int> fl = {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92};
 
   quicksort(std::begin(fl), std::end(fl));
 
   for(int fi : fl) std::cout << fi << ' ';
   std::cout << '\n';
}

Output: 

-8 -5 -4 -4 1 1 1 2 3 5 6 30 64 92

See also

(C++11)
 determines if the range is partitioned by the given predicate
(function template) [edit]
divides elements into two groups while preserving their relative order
(function template) [edit]
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/partition&oldid=78275"