C++ STL 合并算法std::merge()函数入门

本节我们进入合并算法merge()函数的学习。”merge“意思是”合并“，其函数功能是将两个有序同向排序的序列根据排序规则合并成第三个序列。

它的形式是：merge(first1 , last1 , first2 , last2 , first3)。它指的是将[first1, last1)和[first2, last2)这两个区间的元素按排序规则放到first3的后面，这里所有参数皆为迭代器。

既然谈到有序，读者应该能够猜到我们能够使用仿函数来更改排序规则，就像这样：merge(first1 , last1 , first2 , last2 , first3，cmp)，此处cmp是仿函数且能够更改合并的排序规则。

我们通过merge(first1 , last1 , first2 , last2 , first3)合并两个区间到第三个区间：

#include<iostream>
#include<vector>
#include<algorithm>//包含算法头文件！
using namespace std;
void test()
{
/*将两个有序排序的序列合并成第三个序列*/
    vector<int> v1{1,2,3,4,5};
    vector<int> v2{6,7,8,9,10};
    vector<int> v3(10);
    merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin());
    cout << "通过merge()合并两个有序序列\n";
    for(auto it = v3.begin();it!=v3.end();++it)
    {
    cout << *it << " ";
}
cout << '\n';
    
} 
int main(){
    system("title dotcpp.com");
    test();
    return 0;
}

编译结果如下：

从输出结果我们可以清晰地看到，{1，2，3，4，5}和{6，7，8，9，10}已经合并成了一个序列{1，2，3，4，5，6，7，8，9，10}了。

如果我们想对一个容器的两个相邻有序子序列进行合并，我们可以使用inplace_merge(first，middle, last)，它的功能是将[first , middle)区间和[middle,last)区间根据排序规则进行合并，其参数均为迭代器。

同理于merge()函数，inplace_merge()函数也能重新更改排序规则：inplace_merge(first，middle, last, cmp)。

下面我们通过inplace_merge(first，middle, last)合并同一个容器的两个有序相邻子序列。

#include<iostream>
#include<vector>
#include<iterator> //使用迭代器函数进行切割，复习前面知识 next(it,n) 
#include<algorithm>//包含算法头文件！
using namespace std;
void test()
{
/*将inplace_merge(first，middle, last)*/
    vector<int> v{1,3,5,7,9,2,4,6,8,10};
    inplace_merge(v.begin(),next(v.begin(),5),v.end());
    for(auto it = v.begin();it!=v.end();++it)
    {
    cout << *it << " ";
}
cout << '\n';
} 
int main(){
    system("title dotcpp.com");
    test();
    return 0;
}

编译结果如下：

可以看到，容器为{1,3,5,7,9,2,4,6,8,10}，我们中切后通过inplace_merge()函数成功合并为1到10的等差数列，

总结，如果要合并两个有序序列到第三个容器，我们选择merge()函数；如果要对一个容器的相邻两个有序序列进行合并，我们选择inplace_merge()函数。