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

上一节我们学习了partitioin()函数和stable_partition()函数，读者是否能够记起它们的功能以及对他们进行区分呢？本节我们将继续进行分区算法——partition_copy()函数的学习。该函数与前面两个函数大不相同，究其根本是partition_copy()函数能够保证不破破坏原序列，并且把分区后的元素复制到新的两个序列里。

比如原序列是{1，2，3，4，5，6，7，8，9，10}，经过partition_copy()函数不稳定分区后，会得到{2，4，6，8，10}、{1，3，5，7，9}这两个新分区，原序列仍然保持不变。值得注意的是，没有“stable_partition_copy()”这个函数，因为我们的partition_copy函数默认是稳定分区。

partition_copy()函数语法格式入下：

pair<OutputIterator1, OutputIterator2> partition_copy (
    InputIterator first,     // 1. 输入序列起始
    InputIterator last,      // 2. 输入序列结束
    OutputIterator1 result_true,  // 3. 真值输出位置
    OutputIterator2 result_false, // 4. 假值输出位置  
    UnaryPredicate pred);         // 5. 判断条件

这里我们原序列为[first,last)

result_true：为输出迭代器，其用于指定某个存储区域，以存储满足筛选条件的数据；

result_false：为输出迭代器，其用于指定某个存储区域，以存储满足筛选条件的数据；

pred是一个一元谓词，指的是函数返回值为bool类型，参数只有一个的函数或仿函数，可视为作元素的筛选条件。

除此之外，该函数还会返回一个 pair 类型值，其包含 2 个迭代器，第一个迭代器指向的是 result_true 区域内最后一个元素之后的位置；第二个迭代器指向的是 result_false 区域内最后一个元素之后的位置。

下面我们通过partition_copy()函数来对一个正整数序列进行一个奇偶分区。

#include<iostream>
#include<vector>
#include<algorithm>//需包含算法头文件才能使用partition_copy()函数
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_copy()函数*/ 
void test()
{
    vector<int> v{1,2,3,4,5,6,7,8,9,10};//原容器
vector<int> v1(5) ;//偶数容器
vector<int> v2(5) ;//奇数容器 
    /*进行切割*/
pair<vector<int>::iterator,vector<int>::iterator> dend = partition_copy(v.begin(),v.end(),v1.begin(),v2.begin(),pred_obj());//double_end 
   cout << "使用仿函数作一元谓词进行奇偶分区：\n";
   cout << "偶数区：";
    for(auto it = v1.begin();it!=dend.first;++it)cout << *it << " ";
    cout << "\n奇数区：";
    for(auto it = v2.begin();it!=dend.second;++it)cout << *it << " ";
    cout << "\n分区后原容器内元素稳定不变：\n";
    for(auto it = v.begin();it!=v.end();++it)cout << *it << " ";
} 
 
int main(){
    system("title dotcpp.com");
    test();
    return 0;
}

编译结果如下：

partition_copy函数默认是稳定分区，对于序列{1,2,3,4,5,6,7,8,9,10}来说，我们看到奇偶区成功分区到v1{2，4，6，8，10}和v2{1，3，5，7，9}上。

总结：如果想要保证不破破坏原序列，并且把分区后的元素复制到新的两个序列里，我们就能够选择partition_copy()函数；同时，在蓝桥杯、ACM等算法竞赛上该函数主要运用于二分图预处理、搜索优化和字符串处理等具体问题。