C++ 算法 inplace_merge()函数

C++算法 inplace_merge() 函数用于将两个连续的排序范围[first, last)和[middle, last)合并为一个排序范围[first, last)。

元素的比较使用第一版本的运算符<或使用给定的二元比较函数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 ：一个用户定义的二元谓词函数，接受两个参数，并在这两个参数顺序正确时返回true，否则返回false。它遵循严格弱排序规则来排序元素。

返回值

无

复杂度

如果有足够的额外内存可用，则复杂度与first和last之间的距离线性相关：执行N-1次比较和最多两倍的元素移动。否则，复杂度为线性对数：执行最多N*log(N)次元素比较，其中N = last – first，并进行最多这么多次元素交换。

数据竞争

范围[first, last)中的对象被修改。

异常

如果元素比较、元素交换（或移动）或迭代器的操作抛出异常，则此函数会抛出异常。

注意：无效的参数会导致未定义行为。

示例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;
}

输出：