inplace_merge

[機能]

　　2つの連続したソート済み範囲（同じ系列内の first から middle で指定した部分と，middle から last で指定した部分）をマージします．2 引数の比較関数を指定することも可能です（下の表現，sort 参照）．

[形式]

#include <algorithm>

template <class BidirectionalIterator>
    void inplace_merge(BidirectionalIterator first,
                       BidirectionalIterator middle,
                       BidirectionalIterator last);
template <class BidirectionalIterator, class Compare>
    void inplace_merge(BidirectionalIterator first,
                       BidirectionalIterator middle,
                       BidirectionalIterator last, Compare comp);		

[使用例]

1. merge と inplace_merge の使用方法です．

   #include <stdio.h>
   #include <vector>
   #include <algorithm>
   
   using namespace std;
   
   int main()
   {
   					// 初期設定
   	vector<int> v1 {5, 10, 4, 3, 7};
   	printf("初期状態 v1 :");
   	for (auto x : v1)
   		printf("  %d", x);
   	printf("\n");
   
   	vector<int> v2 {1, 9, 10, 6, 7};
   	printf("初期状態 v2 :");
   	for (auto x : v2)
   		printf("  %d", x);
   	printf("\n");
   					// 小さい順にソート
   	printf("小さい順に並べる\n");
   	sort(v1.begin(), v1.end());
   	sort(v2.begin(), v2.end());
   	printf("  v1 :");
   	for (auto x : v1)
   		printf("  %d", x);
   	printf("\n");
   	printf("  v2 :");
   	for (auto x : v2)
   		printf("  %d", x);
   	printf("\n");
   					// merge（v1 と v2 をマージして v3）
   	printf("merge（v1 と v2 をマージして v3）\n");
   	vector<int> v3;
   	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), inserter(v3, v3.begin()));   // inserter 参照
   	printf("  v3 :");
   	for (auto x : v3)
   		printf("  %d", x);
   	printf("\n");
   					// inplace_merge（全体を並べ替える）
   	printf("inplace_merge : 全体を並べ替える\n");
   	vector<int> v4 {1, 9, 10, 2, 7, 8, 9, 9};
   	printf("  前半3つ，後半5つはsort済み v4 :");
   	for (auto x : v4)
   		printf("  %d", x);
   	printf("\n");
   	inplace_merge(v4.begin(), v4.begin()+3, v4.end());
   	printf("  v4(全体をsort) :");
   	for (auto x : v4)
   		printf("  %d", x);
   	printf("\n");
   
   	return 0;
   }
   			

   （出力）

   初期状態 v1 :  5  10  4  3  7
   初期状態 v2 :  1  9  10  6  7
   小さい順に並べる
     v1 :  3  4  5  7  10
     v2 :  1  6  7  9  10
   merge（v1 と v2 をマージして v3）
     v3 :  1  3  4  5  6  7  7  9  10  10
   inplace_merge : 全体を並べ替える
     前半3つ，後半5つはsort済み v4 :  1  9  10  2  7  8  9  9
     v4(全体をsort) :  1  2  7  8  9  9  9  10
   			

[参照]

sort， merge