关注我们

C++ 算法中的 partition函数

C++算法 partition()函数用于根据其参数中提到的给定谓词(条件)对元素进行分区。如果集合已分区，则此函数返回true，否则返回false。

partition - 语法

template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator partition (BidirectionalIterator first,
BidirectionalIterator last, UnaryPredicate pred);	      //until C++ 11

template <class ForwardIterator, class UnaryPredicate>
ForwardIterator partition (ForwardIterator first,
ForwardIterator last, UnaryPredicate pred);	     //Since C++ 11

partition - 参数

first:一个双向迭代器，指向要分区参数内的第一个元素。

last:一个双向迭代器，指向要分区参数内的最后一个最后一个元素。

pred :用户定义的一元谓词函数，用于定义要对元素进行分类时要满足的条件。

partition - 返回值

此函数将迭代器返回到不满足谓词条件的参数的第一个元素。

partition - 例子1

让我们看一个简单的示例来演示partition()的用法:

复制代码

#include <iostream>    //std::cout
#include <algorithm>   //std::partition
#include <vector>      //std::vector

using namespace std;

bool IsOdd (int i) { return (i%2)==1; }

int main () {
  vector<int> myvector;

 //set some values:
  for (int i=1; i<10; ++i) myvector.push_back(i);//1 2 3 4 5 6 7 8 9

  vector<int>::iterator bound;
  bound = partition (myvector.begin(), myvector.end(), IsOdd);

 //print out content:
  cout << "odd elements:";
  for (vector<int>::iterator it=myvector.begin(); it!=bound; ++it)
    cout << ' ' << *it;
  cout << '\n';

  cout << "even elements:";
  for (vector<int>::iterator it=bound; it!=myvector.end(); ++it)
    cout << ' ' << *it;
  cout << '\n';

  return 0;
}

输出:

odd elements: 1 9 3 7 5
even elements: 6 4 8 2

在上面的示例中，从1到9的元素被划分为偶数和奇数元素。

partition - 例子2

让我们看另一个简单的例子:

无涯教程网

在线运行复制代码

#include <vector>  
#include <algorithm>  
#include <iostream>  
  
bool greater5 ( int value ) {  
   return value >5;  
}  
  
int main( ) {  
   using namespace std;  
   vector <int> v1, v2;  
   vector <int>::iterator Iter1, Iter2;  
  
   int i;  
   for ( i = 0 ; i <= 10 ; i++ )  
   {  
      v1.push_back( i );  
   }  
   random_shuffle( v1.begin( ), v1.end( ) );  
  
   cout << "Vector v1 is ( " ;  
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )  
      cout << *Iter1 << " ";  
   cout << ")." << endl;  
  
  //Partition the range with predicate greater10  
   partition ( v1.begin( ), v1.end( ), greater5 );  
   cout << "The partitioned set of elements in v1 is: ( " ;  
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )  
      cout << *Iter1 << " ";  
   cout << ")." << endl;  
   
   return 0;
}

输出:

Vector v1 is ( 4 10 7 8 0 5 2 1 6 9 3 ).
The partitioned set of elements in v1 is: ( 9 10 7 8 6 5 2 1 0 4 3 ).

partition - 例子3

让我们看另一个简单的示例，使用partition()函数对vector的元素进行快速排序:

在线运行复制代码

#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';
    
    return 0;
}

输出:

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

partition - 例子4

让我们看另一个简单的例子:

无涯教程网

在线运行复制代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  vector<int> v = {1, 2, 3, 4, 5};
  
  cout<<"Before Partition: ";
    for_each(v.begin(), v.end(), [](int v) {
   cout << v << " ";
  });


  auto pred = [](int x) { return x % 2 == 0; };

 //Divide it into an even group and an odd group 
  partition(v.begin(), v.end(), pred);
  cout<<"\nAfter partition: ";
  for_each(v.begin(), v.end(), [](int x) {
   cout << x << " ";
  });

  cout<<"\n\nIs it partitioned?"<<endl;
 //Is it divided into an even group and an odd group?  
  if (is_partitioned(v.begin(), v.end(), pred)) {
    cout << "Yes, it is partitioned" << endl;
  }
  else {
    cout << "No, it is not partitioned" << endl;
  }
  
  return 0;
}

输出:

Before Partition: 1 2 3 4 5 
After partition: 4 2 3 1 5 

Is it partitioned?
Yes, it is partitioned

祝学习愉快！(内容编辑有误？请选中要编辑内容 -> 右键 -> 修改 -> 提交！)

技术教程推荐

Python自动化办公实战课 -〔尹会生〕

基于人因的用户体验设计课 -〔刘石〕

B端产品经理入门课 -〔董小圣〕

结构会议力 -〔李忠秋〕

好记忆不如烂笔头。留下您的足迹吧 :)

C++ 算法 中的 partition函数

partition - 语法

partition - 参数

partition - 返回值

partition - 例子1

partition - 例子2

partition - 例子3

partition - 例子4

C++ 算法中的 partition函数