C++ inplace_merge()
C++算法inplace_merge()
C++算法 inplace_merge()函数用于合并两个连续的排序范围[first，last)和[middle，
使用第一个版本的运算符或第二个版本的给定二进制比较函数comp来比较元素。
语法
default (1) template <class BidirectionalIterator>
void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,
BidirectionalIterator last);
custom (2) template <class BidirectionalIterator, class Compare>
void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,
BidirectionalIterator last, Compare comp);
参数
first: 双向迭代器，指向要合并的两个连续排序范围中的第一个范围中的第一个元素，并将其排序为单个范围
last : 一个双向迭代器，该迭代器指向两个要合并的连续排序范围中的第二个范围中的倒数第二个过去的元素。
middle: 一个双向迭代器，该迭代器指向要合并并排序到单个范围内的两个连续排序范围中的第二个范围中的第一个元素的位置。
comp : 用户定义的二进制谓词函数，该函数接受两个参数，如果两个参数的顺序为false，则返回true。
返回值
无
复杂度
如果有足够的额外内存可用，则复杂度在第一个和最后一个之间是线性的: 执行N-1个比较，最多移动许多元素两次。
否则，复杂度是线性的: 执行最多N * log(N)个元素比较，其中N =倒数第一个，并且最多交换许多元素。
数据竞争
范围[第一个，最后一个)被修改。
异常
如果元素比较，元素交换(或移动)或迭代器上的任何操作抛出异常，则此函数将引发异常。
注意: 无效的参数会导致未定义的行为。
示例1
让我们看一个简单的示例来演示inplace_merge()的用法:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void printVector(vector<int>& v)
{
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
cout << ' ' << *it;
cout << '\n';
}
int main () {
vector<int> v1 = {5,10,15,20,25}, v2 = {50,40,30,20,10}, v3(10);
vector<int>::iterator it;
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
it = copy(v1.begin(), v1.end(), v3.begin());
copy(v2.begin(), v2.end(), it);
inplace_merge(v3.begin(), it, v3.end());
cout << "Vector v1 : ";
printVector(v1);
cout << "Vector v2 : ";
printVector(v2);
cout << "Vector v3 : ";
printVector(v3);
}
输出:
Vector v1 : 5 10 15 20 25
Vector v2 : 10 20 30 40 50
Vector v3 : 5 10 10 15 20 20 25 30 40 50
示例2
让我们看另一个简单的示例:
#include <iostream> // std::cout
#include <algorithm> // std::inplace_merge, std::sort, std::copy
#include <vector> // std::vector
using namespace std;
int main () {
int first[] = {5,10,15,20,25};
int second[] = {50,40,30,20,10};
vector<int> v(10);
vector<int>::iterator it;
sort (first,first+5);
sort (second,second+5);
it=copy (first, first+5, v.begin());
copy (second,second+5,it);
inplace_merge (v.begin(),v.begin()+5,v.end());
cout << "The resulting vector contains:";
for (it=v.begin(); it!=v.end(); ++it)
cout << ' ' << *it;
cout << '\n';
return 0;
}
输出:
The resulting vector contains: 5 10 10 15 20 20 25 30 40 50
示例3
让我们看另一个简单的示例，该示例演示如何使用operator <:
来使用inplace_merge()。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
vector<int> v = {1, 3, 2, 4, 5};
inplace_merge(v.begin(), v.begin() + 2, v.end());
for (auto it = v.begin(); it != v.end(); ++it)
cout << *it << endl;
return 0;
}
输出:
示例4
让我们看一个简单的示例，该示例使用比较功能来演示inplace_merge()的使用:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool descending_sort(int a, int b) {
return (a > b);
}
int main(void) {
vector<int> v = {3, 1, 5, 4, 2};
inplace_merge(v.begin(), v.begin() + 2, v.end(), descending_sort);
for (auto it = v.begin(); it != v.end(); ++it)
cout << *it << endl;
return 0;
}
输出:
示例5
让我们看另一个简单的示例:
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
template<class Iter>
void merge_sort(Iter first, Iter last)
{
if (last-first > 1) {
Iter middle = first + (last-first) / 2;
merge_sort(first, middle);
merge_sort(middle, last);
inplace_merge(first, middle, last);
}
}
int main()
{
vector<int> v{10, 2,-9, 0, 9, 7, 1, 3, 4};
merge_sort(v.begin(), v.end());
for(auto n : v) {
cout << n << ' ';
}
cout << '\n';
return 0;
}
输出:
