C++ STL分区算法std::partition()函数入门

本节我们进行分区算法——partition()函数的学习。”partition“意为“隔断”，partition(beg,end,pred)函数的功能是将一个序列“切割”成两个序列（逻辑意义上操作，并非创建两个序列），前一个序列满足一元谓词，后一个序列不满足一元谓词，并返回指向第二个序列的起始迭代器。

举个例子：比如我们有一个序列{1，3，5，6，7}，我们想要把该序列分区，一个奇数区，一个偶数区，此时我们就能使用partition()函数进行“切割”，分区后序列变成{1，3，5，7，6}，函数返回指向“7”的迭代器。

partition()函数的函数模型是：

ForwardIterator partition (ForwardIterator first,
 ForwardIterator last,
 UnaryPredicate pred);

下面，我们通过代码的方式进行partition()函数的学习：

#include<iostream>
#include<vector>
#include<algorithm>//包含算法头文件！
using namespace std;
 
 /*一元谓词*/
 /*普通函数*/
 bool pred_basic(const int&a) 
 {
 	return a%2==0;
 }
 
 /*仿函数*/
 struct pred_obj
 {
 bool operator()(const int &a)const
 {
 	return a%2==0;
 }
};
 
/*partition(beg,end,pred)*/ 
void test()
{
    vector<int> v{1,2,3,4,5,6,7,8,9,10};
    /*进行切割*/
	auto pos = partition(v.begin(),v.end(),pred_obj());//两个一元谓词都可以使用
   cout << "使用仿函数作一元谓词进行奇偶分区：\n";
   cout << "偶数区：";
    for(auto it = v.begin();it!=pos;++it)cout << *it << " ";
    cout << "奇数区：";
    for(auto it = pos;it!=v.end();++it)cout << *it << " ";
} 
 
int main(){
    system("title dotcpp.com");
    test();
    return 0;
}

编译结果如下：

对于序列{1,2,3,4,5,6,7,8,9,10}，partition()函数使用双指针前后对比，根据一元谓词进行”元素交换“，实现“切割”效果。对比输出结果完全符合我们的预期。

有时，对于满足一元谓词的元素，我们为了保持元素的相对位置，从而需要不“移动”它。就上面这个例子，可以看到分区后偶数区是{10，2，8，4，6}，可是，在原序列里“2”要在“10”之前啊，这里把”10“放”2“之前真让人感到不舒服。这时我们就可以使用stable_partition()函数来进行”稳定分区“了。

stable_partition()函数的函数模型是：

BidirectionalIterator stable_partition (BidirectionalIterator first,
 BidirectionalIterator last,
 UnaryPredicate pred);

还是刚才那个序列{1,2,3,4,5,6,7,8,9,10}的奇偶分区问题，我们使用stable_partition()函数后：

auto pos = stable_partition(v.begin(),v.end(),pred_obj());//两个一元谓词都可以使用

输出结果就没有破坏元素在原来序列的相对位置：

这下分区就顺眼多了。

总结：想要对一个序列进行分区，我们可以使用partition()函数，该函数的一元谓词既可以使用普通函数也可以使用仿函数；如果不想破环元素在原序列的相对位置，我们可以通过stable_partition()函数来实现。