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

分久必合

merge

今天的 STL 算法，我们学习的函数来自于集合操作这一分类。

需要注意的是，这个分类的所有序列都是有序的，如果无序，需要先做好排序。

首先了解一下函数 merge()，这个函数的作用是合并两个有序序列，把合并好的序列存入第三个序列。

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

1. 序列1 的 first1 和 last1
2. 序列2 的 first2 和 last2
3. 目标序列的 d_first

示例代码：

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

using namespace std;

int main() {

    // 初始化 vector v1, v2, v3
    vector<int> v1 = {4, 3, 2, 1}, v2 = {0, -1, 5, 6, 7}, v3(v1.size() + v2.size());

    // 声明迭代器
    vector<int>::iterator first1, last1, first2, last2, first3, last3, i;

    // 初始化迭代器
    first1 = v1.begin();
    last1 = v1.end();
    first2 = v2.begin();
    last2 = v2.end();
    first3 = v3.begin();

    // v1, v2 排序
    stable_sort(first1, last1);
    stable_sort(first2, last2);

    // 调用 merge
    last3 = merge(first1, last1, first2, last2, first3);

    // 输出 v3
    for (i = first3; i < last3; ++i) {
        cout << *i << " ";
    }

    return 0;
}

/*
 output
    -1 0 1 2 3 4 5 6 7
 */

代码分析：

在这段代码中，我们初始化了三个 vector，其中第三个向量的长度为前两个向量之和，它是目标向量。

在调用 merge() 函数之前，不要忘了对 v1 和 v2 做好排序。

函数 merge() 返回的是合并之后最后元素的后一个元素的迭代器。因为我们目标序列的长度定义为前两个序列之和，所以这个返回值也就是 v2.end()。

最后的输出结果就是两个序列在升序排序之后的合并结果。

函数 merge() 也有带比较函数的重载形式，在此不再举例。

inplace_merge

函数 inplace_merge() 的作用是合并一个序列内的两个有序子序列，合并后为两个子序列重新排列的结果。

基本的 inplace_merge() 接收 3 个参数：

1. 第一个子序列的起始迭代器 first
2. 第二个子序列的起始迭代器 middle
3. 第二个子序列的结尾迭代器 last

示例代码：

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

using namespace std;

int main() {

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

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

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

    // 调用 inplace_merge
    inplace_merge(first, middle, last);

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

    return 0;
}

/*
 output
    -1 0 1 2 3 4 5 6 7
 */

代码分析：

这段代码需要注意的是原始序列 :

vi = {1, 2, 3, 4, -1, 0, 5, 6, 7};

不难发现，这个序列中包含两个升序的序列，所以我们把 middle 设置为 first + 4，指向的元素是 -1，它既是第一个有序序列的尾，又是第二个有序序列的头。

最终的合并结果是两个子序列合并后重新排列的新序列。

函数 inplace_merge() 也有带比较函数的重载形式，在此不再举例。