C++ partition()
C++算法partition()
C++算法 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)范围内是线性的: 将pred应用于每个元素，并可能交换一些元素
数据竞争
[first，last)范围内的对象已修改。
异常
如果元素交换或迭代器上的操作引发异常，则此函数引发异常。
请注意，无效参数会导致未定义的行为。
示例1
让我们看一个简单的示例来演示partitioning( ):
#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()函数对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
示例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
