std::merge

ヘッダ `<algorithm>` で定義
	(1)
template<class InputIt1, class InputIt2, class OutputIt > OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );			(C++20以前)
template<class InputIt1, class InputIt2, class OutputIt > constexpr OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );			(C++20およびそれ以降)
template<class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3 > ForwardIt3 merge( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first );		(2)	(C++17およびそれ以降)
		(3)
template<class InputIt1, class InputIt2, class OutputIt, class Compare> OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );				(C++20以前)
template<class InputIt1, class InputIt2, class OutputIt, class Compare> constexpr OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );				(C++20およびそれ以降)
template<class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3, class Compare> ForwardIt3 merge( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first, Compare comp );			(4)	(C++17およびそれ以降)

2つのソート済み範囲 [first1, last1) および [first2, last2) を d_first から始まる1つのソート済み範囲にマージします。

1) 要素は operator< を用いて比較されます。

3) 要素は指定された二項比較関数 comp を用いて比較されます。

2,4)(1,3) と同じですが、 policy に従って実行されます。このオーバーロードは、std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> が true である場合にのみ、オーバーロード解決に参加します

2つのマージ元範囲内に同等の要素がある場合、1つめの範囲の要素は2つめの範囲の要素より前に来ます。同じ範囲内の要素の順序は保たれます。

マージ先範囲がいずれかの入力範囲とオーバーラップしている場合、動作は未定義です (入力範囲はお互いにオーバーラップしていても構いません)。

first1, last1	-	1つめのマージする要素の範囲
first2, last2	-	2つめのマージする要素の範囲
d_first	-	マージ先範囲の先頭
policy	-	使用する実行ポリシー。詳細は実行ポリシーを参照してください
comp	-	最初の要素が2番目の要素より小さい (前に順序づけられる) 場合に true を返す、比較関数オブジェクト (`Compare` の要件を満たすオブジェクト)。比較関数のシグネチャは以下と同等なものであるべきです。 bool cmp(const Type1 &a, const Type2 &b); シグネチャが const& を持つ必要はありませんが、関数オブジェクトは渡されたオブジェクトを変更してはなりません。型 Type1 および Type2 は、 InputIt1 および InputIt2 型のオブジェクトの逆参照からType1 と Type2 の両方に暗黙に変換可能なものでなければなりません。
型の要件
- `InputIt1, InputIt2` は `InputIterator` の要件を満たさなければなりません。
- `ForwardIt1, ForwardIt2, ForwardIt3` は `ForwardIterator` の要件を満たさなければなりません。
- `OutputIt` は `OutputIterator` の要件を満たさなければなりません。

[編集]戻り値

最後にコピーされた要素の次の要素を指す出力イテレータ。

[編集]計算量

1,3) 多くとも std::distance(first1, last1)+std::distance(first2, last2)-1 回の比較。

2,4)O(std::distance(first1, last1)+std::distance(first2, last2))。

[編集]例外

テンプレート引数 ExecutionPolicy を持つオーバーロードは以下のようにエラーを報告します。

アルゴリズムの一部として呼び出された関数の実行が例外を投げ、 ExecutionPolicy が3つの標準のポリシーのいずれかの場合は、 std::terminate が呼ばれます。それ以外のあらゆる ExecutionPolicy については、動作は処理系定義です。
アルゴリズムがメモリの確保に失敗した場合は、 std::bad_alloc が投げられます。

[編集]ノート

このアルゴリズムは std::set_union と似た処理を行います。どちらも2つのソート済み範囲を消費し、両方の入力の要素を持つソート済みの出力を生成します。これらの2つのアルゴリズムの違いは、両方の入力範囲にある同等　(LessThanComparable のノートを参照) な値の処理方法です。同等な値が1つめの範囲に n 個現れ、2つめの範囲に m 個現れた場合、 std::merge は n+m 個をすべて出力しますが、 std::set_union は std::max(n, m) 個しか出力しません。そのため、 std::merge はちょうど std::distance(first1, last1)+std::distance(first2, last2) 個の値を出力しますが、 std::set_union の出力はそれより少なくなる場合があります。

[編集]実装例

1つめのバージョン

template<class InputIt1, class InputIt2, class OutputIt> OutputIt merge(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first){for(; first1 != last1;++d_first){if(first2 == last2){returnstd::copy(first1, last1, d_first);}if(*first2 <*first1){*d_first =*first2;++first2;}else{*d_first =*first1;++first1;}}returnstd::copy(first2, last2, d_first);}

2つめのバージョン

template<class InputIt1, class InputIt2, class OutputIt, class Compare> OutputIt merge(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp){for(; first1 != last1;++d_first){if(first2 == last2){returnstd::copy(first1, last1, d_first);}if(comp(*first2, *first1)){*d_first =*first2;++first2;}else{*d_first =*first1;++first1;}}returnstd::copy(first2, last2, d_first);}

[編集]例

Run this code

#include <iostream>#include <iterator>#include <algorithm>#include <vector>#include <random>#include <functional>   int main(){// fill the vectors with random numbersstd::random_device rd;std::mt19937 mt(rd());std::uniform_int_distribution<> dis(0, 9);   std::vector<int> v1(10), v2(10);std::generate(v1.begin(), v1.end(), std::bind(dis, std::ref(mt)));std::generate(v2.begin(), v2.end(), std::bind(dis, std::ref(mt)));   // sortstd::sort(v1.begin(), v1.end());std::sort(v2.begin(), v2.end());   // output v1std::cout<<"v1 : ";std::copy(v1.begin(), v1.end(), std::ostream_iterator<int>(std::cout, " "));std::cout<<'\n';   // output v2std::cout<<"v2 : ";std::copy(v2.begin(), v2.end(), std::ostream_iterator<int>(std::cout, " "));std::cout<<'\n';   // mergestd::vector<int> dst; std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dst));   // outputstd::cout<<"dst: ";std::copy(dst.begin(), dst.end(), std::ostream_iterator<int>(std::cout, " "));std::cout<<'\n';}

出力例:

v1 : 0 1 3 4 4 5 5 8 8 9 v2 : 0 2 2 3 6 6 8 8 8 9 dst: 0 0 1 2 2 3 3 4 4 5 5 6 6 8 8 8 8 8 9 9

[編集]関連項目

inplace_merge	2つのソート済み範囲をその場でマージします (関数テンプレート)[edit]
set_union	2つの集合の和を計算します (関数テンプレート)[edit]
sort	指定範囲を昇順にソートします (関数テンプレート)[edit]
stable_sort	等しい要素間の順序を維持しながら指定範囲の要素をソートします (関数テンプレート)[edit]

Mar	JUN	Jul
	01
2017	2018	2019

言語
ヘッダ
コンセプト
言語サポートライブラリ
診断ライブラリ
ユーティリティライブラリ
文字列ライブラリ
コンテナライブラリ
アルゴリズムライブラリ
イテレータライブラリ
数値演算ライブラリ
入出力ライブラリ
ローカライゼーションライブラリ
正規表現ライブラリ(C++11)
アトミック操作ライブラリ(C++11)
スレッドサポートライブラリ(C++11)
ファイルシステムライブラリ(C++17)
技術仕様書

cppreference.com

検索

名前空間

変種

表示

操作