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

到目前为止，我们已经学习了3个分区算法，读者知道他们分别是什么吗？partition()函数、stable_partition()函数和partition_copy()函数，它们都能够实现分区操作。比如我们可以通过stable_partition()函数对序列{1，2，3，4，5，6，7，8，9，10}进行“奇偶切割”，原序列处理后会变成{2，4，6，8，10，1，3，5，7，9}。当我们面临一些“切割”好的序列时，我们怎么去寻找它们的“切割点”呢？这里“切割点”可以理解为不满足一元谓词的区间的起始迭代器。比如我们已经知道{2，4，6，8，10，1，3，5，7，9}是一个分区好的序列，那它的“切割点”就是指向元素1的迭代器。面对这种问题时我们就可以用到partitioin_point()函数来寻找切割点了，“point”意为“点”，该函数的功能是给定分区后的序列，找寻该序列的“切割点”，找到返回指向“切割点”的迭代器，否则返回尾后迭代器。

partition_point()函数的语法格式为：

ForwardIterator partition_point (
    ForwardIterator first,     // 指向序列起始位置的迭代器 
    ForwardIterator last,      // 指向序列结束位置（尾后）的迭代器  
    UnaryPredicate pred);   // 一元谓词函数，定义分区条件

partition_point()函数的作用区间是[first,last)，pred为一元谓词，指的是函数返回值为bool类型，参数只有一个的函数或仿函数，可视为作元素的筛选条件。

下面我们通过partition_copy()函数来寻找一个奇偶分区的“切割点”。

#include<iostream>
#include<vector>
#include<algorithm>//需包含算法头文件才能使用partition_point()函数
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_point()函数*/ 
void test()
{
    vector<int> v{1,2,3,4,5,6,7,8,9,10};
    cout << "原序列为：";
    for(auto it = v.begin();it!=v.end();++it)cout << *it << " ";
    cout << '\n';
    /*获得处理好的分区序列*/ 
stable_partition(v.begin(),v.end(),pred_obj());
 cout << "stable_partition()函数切割后：";
    for(auto it = v.begin();it!=v.end();++it)cout << *it << " ";
    cout << '\n';
    vector<int>::iterator pos =partition_point(v.begin(),v.end(),pred_obj()) ;
    if(pos!=v.end())
    {
    cout << "找到切割点并且切割点的元素是【" << *pos << "】\n" ;
}
} 
 
int main(){
    system("title dotcpp.com");
    test();
    return 0;
}

编译结果如下：

根据输出结果，我们找到“切割点”的元素是“1”，符合我们的预期。

总结：partition_copy()函数能够帮助我们快速找到分区序列的“切割点”；同时，在蓝桥杯、ACM等算法竞赛上该函数主要运用于统计达标元素或在DFS/BFS搜索中快速筛选邻节点。