C++ partition()和stable_partition()函数详解

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

C++ partition()和stable_partition()函数详解

C++ stable_partition()函数

推荐阅读