STL partition_point函数

STL partition_point函数算法

在 STL 中 partition_point() 函数用于在已分好组的数据中找到分界位置，该函数会返回一个正向迭代器，该迭代器指向的是 [first, last] 范围内第一个不符合 pred 筛选规则的元素。

STL partition_point函数使用

在前面章节中，我们系统学习了 partition()、stable_partition() 和 partition_copy() 这 3 个函数，它们的功能本质上都是根据某个筛选规则对指定范围内的数据进行分组（即符合条件的为一组，不符合条件的为另一组），并且反馈给我们两组数据之间的分界位置。

事实上，有些数据本身就已经是按照某个筛选规则分好组的，例如：

1,2,3,4,5,6,7      <-- 根据规则 i<4，{1,2,3} 为一组，{4,5,6,7} 为另一组
2,4,6,8,1,3,5,7,9  <-- 根据规则 i%2=0，{2,4,6,8} 为一组，{1,3,5,7,9} 为另一组

类似上面这样已经“分好组”的数据，在使用时会有一个问题，即不知道两组数据之间的分界在什么位置。有读者可能想到，再调用一次 partition()、stale_partition() 或者 partition_copy() 不就可以了吗？这种方法确实可行，但对已经分好组的数据再进行一次分组，是没有任何必要的。

实际上，对于如何在已分好组的数据中找到分界位置，C++ 11 标准库提供了专门解决此问题的函数，即 partition_point() 函数。

STL partition_point函数详解

头文件

#include <algorithm>

语法

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

参数

参数	描述
first	正向迭代器
last	正向迭代器
pred	指定数据的筛选规则。

说明

first 和 last 为正向迭代器，[first, last) 用于指定该函数的作用范围；pred 用于指定数据的筛选规则。所谓筛选规则，其实就是包含 1 个参数且返回值类型为 bool 的函数，此函数可以是一个普通函数，也可以是一个函数对象。

技术细节

该函数会返回一个正向迭代器，该迭代器指向的是 [first, last] 范围内第一个不符合 pred 筛选规则的元素。

案例

STL partition_point函数

使用 STL partition_point 函数分组集合

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool mycomp(int i) 
{ 
	return (i % 2) == 0; 
}
int main() 
{
	cout << "嗨客网(www.haicoder.net)\n" << endl;	
	vector<int> myvector{ 2,4,6,8,1,3,5,7,9 };
    vector<int>::iterator iter = partition_point(myvector.begin(), myvector.end(),mycomp);
    for (auto it = myvector.begin(); it != iter; ++it) 
    {
        cout << *it << " ";
    }
    cout << "\n";
    for (auto it = iter; it != myvector.end(); ++it) 
    {
        cout << *it << " ";
    }
    cout << "\n*iter = " << *iter;
    cout << endl;
    return 0;
}

我们在 Linux 下使用 g++ 进行编译，具体命令如下：

g++ partition_point.cpp -std=c++11

编译后，我们直接运行生成的二进制文件 a.out，如下图所示：

我们使用了 partition_point 函数找到了分组的位置。

STL partition_point函数总结

在 STL 中 partition_point() 函数用于在已分好组的数据中找到分界位置，该函数会返回一个正向迭代器，该迭代器指向的是 [first, last] 范围内第一个不符合 pred 筛选规则的元素。