剑指信奥｜C++ 之 STL 算法 partition

黑白分明的划分

partition

今天，我们继续 C++ STL 算法的学习，我们将了解一个新的算法分类 — partiton 划分。

其实，在刚刚结束的的排序算法中，我们已经接触到了一个词 partial，叫做部分，跟划分的关联很密切。

先看第一个划分算法函数 partition()，这个函数也会让元素的顺序发生变化，从某种意义上说，也算是一种排序。

基本 partition() 函数接收 3 个参数：

1. first
2. last
3. 谓词 p

代码示例：

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

inline bool p(int x) {
    return x % 2 == 0;
}

int main() {

    // 初始化 vector
    vector<int> vi = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    // 声明迭代器
    vector<int>::iterator first, last;

    // 初始化迭代器
    first = vi.begin();
    last = vi.end();

    // partition 排序
    partition(first, last, p);

    // 输出 vi [first, last)
    for (auto i = first; i < last; ++i) {
        cout << *i << " ";
    }

    return 0;
}

/*
 output
    0 8 2 6 4 5 3 7 1 9
 */

代码说明：

在这段代码中，我们定义了一元谓词函数，偶数返回  true，奇数返回 false。

函数 partition() 将作如下划分：谓词对其返回 true 的元素位于返回 false 的元素之前。

partition() 在划分后并不能保证原有元素的相对顺序，于是有了下面的函数。

stable_partition

顾名思义，stable_partition() 的含义就是稳定的划分。

相对于上一个函数，就是在划分后，元素保持了原有的顺序，其余的内容都是一样的。

代码示例：

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

inline bool p(int x) {
    return x % 2 == 0;
}

int main() {

    // 初始化 vector
    vector<int> vi = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    // 声明迭代器
    vector<int>::iterator first, last;

    // 初始化迭代器
    first = vi.begin();
    last = vi.end();

    // stable_partition 排序
    stable_partition(first, last, p);

    // 输出 vi [first, last)
    for (auto i = first; i < last; ++i) {
        cout << *i << " ";
    }

    return 0;
}

/*
 output
    0 2 4 6 8 1 3 5 7 9
 */

代码说明：

与 partition() 的结果 0 8 2 6 4 5 3 7 1 9 相比，稳定的特点有了明显的体现。

is_partitioned

函数 is_partitioned() 是一个判断函数，如果 [first, last) 为空或完成了划分，返回 true，否则返回 false。

基本 is_partitioned() 函数接收 3 个参数：

1. first
2. last
3. 谓词 p

代码示例：

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

inline bool p(int x) {
    return x % 2 == 0;
}

int main() {

    // 初始化 vector
    vector<int> vi = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    // 声明迭代器
    vector<int>::iterator first, last;

    // 初始化迭代器
    first = vi.begin();
    last = vi.end();
    
    // is_partitioned() 判断
    cout << is_partitioned(first, last, p) << endl;

    // partition 排序
    partition(first, last, p);

    // is_partitioned() 判断
    cout << is_partitioned(first, last, p) << endl;

    return 0;
}

/*
 output
    0
    1
 */

代码说明：

0 表示 false，1 表示 true。

partition_point

函数 partition_point() 返回第一次划分结尾后的迭代器，如果所有元素都满足谓词，则返回 last。

基本 partition_point() 函数接收 3 个参数：

1. first
2. last
3. 谓词 p

代码示例：

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

inline bool p(int x) {
    return x % 2 == 0;
}

int main() {

    // 初始化 vector
    vector<int> vi = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    // 声明迭代器
    vector<int>::iterator first, last, it;

    // 初始化迭代器
    first = vi.begin();
    last = vi.end();

    // stable_partition 排序
    stable_partition(first, last, p);


    it = partition_point(first, last, p);

    for(auto i = first; i < it; ++i) {
        cout << *i << " ";
    }

    return 0;
}

/*
 output
    0 2 4 6 8
 */

代码说明：

代码输出了对谓词 p 返回为 true 的元素。

partition_copy

函数 partition_copy() 对划分后的结果进行复制，针对谓词 p 返回的不同结果，分别输出到两个容器中。

基本 partition_copy() 函数接收 5 个参数：

1. first
2. last
3. 满足谓词的起始迭代器 d_frist_true
4. 不满足谓词的起始迭代器 d_frist_false
5. 谓词 p

代码示例：

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

inline bool p(int x) {
    return x % 2 == 0;
}

int main() {

    // 初始化 vector
    vector<int> vi = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, v_true(5, 0), v_false(5, 0);

    // 声明迭代器
    vector<int>::iterator first, last, d_first_true, d_first_false, d_last_true, d_last_false;

    // 初始化迭代器
    first = vi.begin();
    last = vi.end();
    d_first_true = v_true.begin();
    d_first_false = v_false.begin();
    d_last_true = v_true.end();
    d_last_false = v_false.end();

    // partition_copy 排序后复制
    partition_copy(first, last, d_first_true, d_first_false, p);

    // 输出 v_true
    for (auto i = d_first_true; i < d_last_true; ++i) {
        cout << *i << " ";
    }

    cout << endl;

    // 输出 v_false
    for (auto i = d_first_false; i < d_last_false; ++i) {
        cout << *i << " ";
    }

    return 0;
}

/*
 output
    0 2 4 6 8
    1 3 5 7 9
 */

代码说明：

函数 partition_copy() 在根据谓词 p 进行排序的同时，完成了复制。

对 p 返回为 true 的，给定了范围起始迭代器 d_first_true。

对 p 返回为 false 的，给定了范围起始迭代器 d_first_false。

最后，把输出的两个容器内的元素进行了输出。

以上就是 C++ STL partition 算法的所有函数，这部分内容还是比较容易理解的。