C++ partition_copy()函数详解

C++ partition()和stable_partition()函数》一节中,已经详细介绍了 partition() 和 stable_partition() 函数的功能和用法。不知道读者是否发现,这 2 个函数在实现功能时,都直接修改了原序列中元素的存储位置。

而在某些场景中,我们需要类似 partition() 或者 stable_partition() 函数“分组”的功能,但并不想对原序列做任何修改。这种情况下,就可以考虑使用 partition_copy() 函数。

和 stable_partition() 一样,partition_copy() 函数也能按照某个筛选规则对指定区域内的数据进行“分组”,并且分组后不会改变各个元素的相对位置。更重要的是,partition_copy() 函数不会对原序列做修改,而是以复制的方式将序列中各个元组“分组”到其它的指定位置存储。

举个例子,有如下一个数组 a[10]:

1 2 3 4 5 6 7 8 9

假设筛选条件为 i%2==0(也就是筛选出偶数),如果借助 stable_partition() 函数,则数组 a[10] 中元素的存储顺序会变成:

2 4 6 8 1 3 5 7 9

而如果选用同样的筛选规则,使用 partition_copy() 函数还需要为其配备 2 个存储空间(例如 b[10] 和 c[10]),其中 b[10] 用于存储符合筛选条件的偶数,而 c[10] 用于存储不符合筛选条件的奇数,也就是说,partition_copy() 函数执行的最终结果为:

a[10]: 1 2 3 4 5 6 7 8 9
b[10]: 2 4 6 8
c[10]: 1 3 5 7 9

注意,这里仅展示了 b[10] 和 c[10] 数组中存储的有效数据。


值得一提的是,partition_copy() 函数定义在<algorithm>头文件中,其语法格式如下:
pair<OutputIterator1,OutputIterator2> partition_copy (
                    InputIterator first, InputIterator last,
                    OutputIterator1 result_true, OutputIterator2 result_false,
                    UnaryPredicate pred);
其中,各个参数的含义为:
  • first、last:都为输入迭代器,其组合 [first, last) 用于指定该函数处理的数据区域;
  • result_true:为输出迭代器,其用于指定某个存储区域,以存储满足筛选条件的数据;
  • result_false:为输出迭代器,其用于指定某个存储区域,以存储满足筛选条件的数据;
  • pred:用于指定筛选规则,其本质就是接收一个具有 1 个参数且返回值类型为 bool 的函数。注意,该函数既可以是普通函数,还可以是一个函数对象。

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

举个例子:
#include <iostream>     // std::cout
#include <algorithm>    // std::partition_copy
#include <vector>       // std::vector
using namespace std;
//以普通函数的方式定义筛选规则
bool mycomp(int i) { return (i % 2) == 0; }

//以函数对象的形式定义筛选规则
class mycomp2 {
public:
    bool operator()(const int& i) {
        return (i % 2 == 0);
    }
};

int main() {
    vector<int> myvector{ 1,2,3,4,5,6,7,8,9 };
    int b[10] = { 0 }, c[10] = { 0 };
    //以 mycomp 规则,对 myvector 容器中的数据进行分组,这里的 mycomp 还可以改为 mycomp2(),即以 mycomp2 为筛选规则
    pair<int*, int*> result= partition_copy(myvector.begin(), myvector.end(), b, c, mycomp);
    cout << "b[10]:";
    for (int *p = b; p < result.first; p++) {
        cout << *p << " ";
    }
    cout << "\nc[10]:";
    for (int *p = c; p < result.second; p++) {
        cout << *p << " ";
    }
    return 0;
}
程序执行结果为:

b[10]:2 4 6 8
c[10]:1 3 5 7 9

程序中仅演示了如何用数组来存储 partition_copy() 函数分组后的数据,当然也可以用容器来存储。

C++ 标准库中还给出了 partition_copy() 函数底层实现的参考代码,感兴趣的读者可自行研究,这里不再进行过多赘述。
template <class InputIterator, class OutputIterator1,
          class OutputIterator2, class UnaryPredicate pred>
          pair<OutputIterator1,OutputIterator2>
partition_copy (InputIterator first, InputIterator last,
                OutputIterator1 result_true, OutputIterator2 result_false,
                UnaryPredicate pred)
{
    while (first!=last) {
        if (pred(*first)) {
            *result_true = *first;
            ++result_true;
        }
        else {
            *result_false = *first;
            ++result_false;
        }
        ++first;
    }
    return std::make_pair (result_true,result_false);
}