C++ partition 和stable_partition 函数详解

发布时间：2022-07-18 07:43:02 所属栏目：语言来源：互联网

导读：partition 可直译为分组，partition() 函数可根据用户自定义的筛选规则，重新排列指定区域内存储的数据，使其分为 2 组，第一组为符合筛选条件的数据，另一组为不符合筛选条件的数据。举个例子，假设有一个数组 a[9]，其存储数据如下： 1 2 3 4 5 6 7 8 9

　　partition 可直译为“分组”，partition() 函数可根据用户自定义的筛选规则，重新排列指定区域内存储的数据，使其分为 2 组，第一组为符合筛选条件的数据，另一组为不符合筛选条件的数据。

　　举个例子，假设有一个数组 a[9]，其存储数据如下：
　　1 2 3 4 5 6 7 8 9

　　在此基础上，如果设定筛选规则为 i%2=0（其中 i 即代指数组 a 中的各个元素），则借助 partition() 函数，a[9] 数组中存储数据的顺序可能变为：
　　1 9 3 7 5 6 4 8 2

　　其中 {1,9,3,7,5} 为第一组，{6,4,8,2} 为第二组。显然前者中的各个元素都符合筛选条件，而后者则都不符合。由此还可看出，partition() 函数只会根据筛选条件将数据进行分组，并不关心分组后各个元素具体的存储位置。
　　如果想在分组之后仍不改变各元素之间的相对位置，可以选用 stable_partition() 函数。有关此函数的功能和用法，本节后续会做详细讲解。

　　值得一提得是，partition() 函数定义于<algorithm>头文件中，因此在使用该函数之前，程序中应先引入此头文件：
　　#include <algorithm>
　　如下为 partition() 函数的语法格式：
　　ForwardIterator partition (ForwardIterator first,
　　                           ForwardIterator last,
　　                           UnaryPredicate pred);
　　其中，first 和 last 都为正向迭代器，其组合 [first, last) 用于指定该函数的作用范围；pred 用于指定筛选规则。
　　所谓筛选规则，其本质就是一个可接收 1 个参数且返回值类型为 bool 的函数，可以是普通函数，也可以是一个函数对象。

　　同时，partition() 函数还会返回一个正向迭代器，其指向的是两部分数据的分界位置，更确切地说，指向的是第二组数据中的第 1 个元素。

　　举个例子：
　　#include <iostream>     // std::cout
　　#include <algorithm>    // std::partition
　　#include <vector>       // std::vector
　　using namespace std;
　　//以普通函数的方式定义partition()函数的筛选规则
　　bool mycomp(int i) { return (i % 2) == 0; }
　　//以函数对象的形式定义筛选规则
　　class mycomp2 {
　　public:
　　    bool operator()(const int& i) {
　　        return (i%2 == 0);
　　    }
　　};
　　int main() {
　　    std::vector<int> myvector{1,2,3,4,5,6,7,8,9};
　　    std::vector<int>::iterator bound;
　　    //以 mycomp2 规则，对 myvector 容器中的数据进行分组
　　    bound = std::partition(myvector.begin(), myvector.end(), mycomp2());
　　    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it) {
　　        cout << *it << " ";
　　    }
　　    cout << "nbound = " << *bound;
　　    return 0;
　　}
　　程序执行结果为：
　　8 2 6 4 5 3 7 1 9
　　bound = 5

　　可以看到，程序中借助 partition() 对 myvector 容器中的数据进行了再加工，基于 mycomp2() 筛选规则，能够被 2 整除的元素位于第 1 组，不能被 2 整除的元素位于第 2 组。

　　同时，parition() 函数会返回一个迭代器，通过观察程序的执行结果可以看到，该迭代器指向的是元素 5，同时也是第 2 组数据中的第 1 个元素。
　　值得一提的是，C++ STL partition()函数官方给出了该函数底层实现的参考代码，感兴趣的读者可自行前往分析，这里不再做过多描述。

　　C++ stable_partition()函数
　　前面提到，partition() 函数只负责对指定区域内的数据进行分组，并不保证各组中元素的相对位置不发生改变。而如果想在分组的同时保证不改变各组中元素的相对位置，可以使用 stable_partition() 函数。

　　也就是说，stable_partition() 函数可以保证对指定区域内数据完成分组的同时，不改变各组内元素的相对位置。

　　仍以数组 a[9] 举例，其存储的数据如下：
　　1 2 3 4 5 6 7 8 9

　　假定筛选规则为 i%2=0（其中 i 即代指数组 a 中的各个元素），则借助 stable_partition() 函数，a[9] 数组中存储数据的顺序为：
　　2 4 6 8 1 3 5 7 9

　　其中 {2,4,6,8} 为一组，{1,3,5,7,9} 为另一组。通过和先前的 a[9] 对比不难看出，各个组中元素的相对位置没有发生改变。
　　所谓元素的相对位置不发生改变，以 {2,4,6,8} 中的元素 4 为例，在原 a[9] 数组中，该元素位于 2 的右侧，6 和 8 的左侧；在经过 stable_partition() 函数处理后的 a[9] 数组中，元素 4 仍位于 2 的右侧，6 和 8 的左侧。因此，该元素的相对位置确实没有发生改变。

　　stable_partition() 函数定义在<algorithm>头文件中，其语法格式如下：
　　BidirectionalIterator stable_partition (BidirectionalIterator first,
　　                                        BidirectionalIterator last,
　　                                        UnaryPredicate pred);
　　其中，first 和 last 都为双向迭代器，其组合 [first, last) 用于指定该函数的作用范围；pred 用于指定筛选规则。

　　同时，stable_partition() 函数还会返回一个双向迭代器，其指向的是两部分数据的分界位置，更确切地说，指向的是第二组数据中的第 1 个元素。

　　举个例子：
　　#include <iostream>     // std::cout
　　#include <algorithm>    // std::stable_partition
　　#include <vector>       // std::vector
　　using namespace std;
　　//以普通函数的方式定义partition()函数的筛选规则
　　bool mycomp(int i) { return (i % 2) == 1; }
　　//以函数对象的形式定义筛选规则
　　class mycomp2 {
　　public:
　　    bool operator()(const int& i) {
　　        return (i%2 == 1);
　　    }
　　};
　　int main() {
　　    std::vector<int> myvector{1,2,3,4,5,6,7,8,9};
　　    std::vector<int>::iterator bound;
　　    //以 mycomp2 规则，对 myvector 容器中的数据进行分组
　　    bound = std::stable_partition(myvector.begin(), myvector.end(), mycomp);
　　    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it) {
　　        cout << *it << " ";
　　    }
　　    cout << "nbound = " << *bound;
　　    return 0;
　　}
　　程序执行结果为：
　　1 3 5 7 9 2 4 6 8
　　bound = 2

（编辑：应用网_丽江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

类关系记忆秘诀	Makefile中另外的常用
矩阵稀疏矩阵压缩存	Java访问控制修饰符详