C++ Algorithm partition()

2024年8月30日 | 阅读4分钟

C++ Algorithm partition() 函数用于根据其参数中提到的给定谓词（条件）对元素进行分区。如果容器被分区，则此函数返回 true，否则返回 false。

语法

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

参数

first：指向要分区的范围中第一个元素的双向迭代器。

last：指向要分区的范围中最后一个元素之后的双向迭代器。

pred：一个用户定义的一元谓词函数，它定义了如果一个元素要被分类则需要满足的条件。

返回值

此函数返回一个迭代器，指向不满足谓词条件的范围的第一个元素。

复杂度

复杂度在范围 [first, last) 内呈线性关系：对每个元素应用谓词，并可能交换其中一些元素。

数据竞争

范围 [first, last) 中的对象被修改。

异常

如果元素交换或迭代器操作抛出异常，此函数将抛出异常。

请注意，无效参数会导致未定义行为。

示例 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 被分区为偶数和奇数。

示例 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 ).

示例 3

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

#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

示例 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

下一主题C++ 算法

C++ Algorithm partition()

语法

参数

返回值

复杂度

数据竞争

异常

示例 1

示例 2

示例 3

示例 4

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ Algorithm partition()

语法

参数

返回值

复杂度

数据竞争

异常

示例 1

示例 2

示例 3

示例 4

相关帖子

algorithm fill() 函数

algorithm copy_backward() 函数

algorithm generate() 函数

algorithm find_first_of() 函数

algorithm copy_n() 函数

algorithm set_union() 函数

C++ Algorithm next_permutation () 函数

algorithm equal() 函数

algorithm for_each() 函数

algorithm any_of() 函数