GeezerVison is showing cpprefjp.github.io — std::merge - cpprefjp C++日本語リファレンス
最終更新日時:
2026年08月26日 16時18分05秒 (JST)
Akira Takahashi
が更新
function template
<algorithm>
std:: merge
namespace std {
template < class InputIterator1 , class InputIterator2 , class OutputIterator >
OutputIterator
merge ( InputIterator1 first1 ,
InputIterator1 last1 ,
InputIterator2 first2 ,
InputIterator2 last2 ,
OutputIterator result ); // (1) C++98
template < class InputIterator1 , class InputIterator2 , class OutputIterator >
constexpr OutputIterator
merge ( InputIterator1 first1 ,
InputIterator1 last1 ,
InputIterator2 first2 ,
InputIterator2 last2 ,
OutputIterator result ); // (1) C++20
template < class InputIterator1 , class InputIterator2 , class OutputIterator ,
class Compare >
OutputIterator
merge ( InputIterator1 first1 ,
InputIterator1 last1 ,
InputIterator2 first2 ,
InputIterator2 last2 ,
OutputIterator result ,
Compare comp ); // (2) C++98
template < class InputIterator1 , class InputIterator2 , class OutputIterator ,
class Compare >
constexpr OutputIterator
merge ( InputIterator1 first1 ,
InputIterator1 last1 ,
InputIterator2 first2 ,
InputIterator2 last2 ,
OutputIterator result ,
Compare comp ); // (2) C++20
template < class ExecutionPolicy , class ForwardIterator1 , class ForwardIterator2 ,
class ForwardIterator >
ForwardIterator
merge ( ExecutionPolicy && exec ,
ForwardIterator1 first1 ,
ForwardIterator1 last1 ,
ForwardIterator2 first2 ,
ForwardIterator2 last2 ,
ForwardIterator result ); // (3) C++17
template < class ExecutionPolicy , class ForwardIterator1 , class ForwardIterator2 ,
class ForwardIterator , class Compare >
ForwardIterator
merge ( ExecutionPolicy && exec ,
ForwardIterator1 first1 ,
ForwardIterator1 last1 ,
ForwardIterator2 first2 ,
ForwardIterator2 last2 ,
ForwardIterator result ,
Compare comp ); // (4) C++17
}
概要
2つのソート済みイテレータ範囲[first1, last1)と[first2, last2)をマージする。
事前条件
[first1,last1) と [first2,last2) は operator< または comp でソートされていること。結果のイテレータ範囲と入力のイテレータ範囲は重なっていてはならない。
効果
イテレータ範囲[first1,last1)とイテレータ範囲[first2,last2) の２つの要素を全て [result,result_last) へコピーする。その際に、is_sorted (result, result_last)is_sorted (result, result_last, comp)result_last は result + (last1 - first1) + (last2 - first2) とする）。
戻り値
return result + ( last1 - first1 ) + ( last2 - first2 );
計算量
N = (last1 - first1) + (last2 - first2)であるとして説明する。
(1), (2) : 最大でN - 1回比較する
(3), (4) : O(N) 回だけ比較する
備考
この操作は安定である。つまり、各入力イテレータ範囲内の要素の前後関係は保たれ、また、1 番目の範囲と 2 番目に等値の要素があった場合には、1 番目の範囲の要素の方が先に来る。
例
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
int main ()
{
std::vector < int > a = { 3 , 1 , 4 , 2 };
std::vector < int > b = { 2 , 5 , 6 , 4 };
std::vector < int > result ;
std::sort ( a.begin() , a.end() );
std::sort ( b.begin() , b.end() );
// aとbをマージ
std::merge ( a.begin() , a.end() ,
b.begin() , b.end() ,
std::back_inserter ( result ));
std::for_each ( result.begin() , result.end() , []( int x ) {
std::cout << x << std::endl ;
});
}
出力
1
2
2
3
4
4
5
6
実装例
template < class InputIterator1 , class InputIterator2 , class OutputIterator >
OutputIterator merge ( InputIterator1 first1 , InputIterator1 last1 ,
InputIterator2 first2 , InputIterator2 last2 ,
OutputIterator result )
{
while ( first1 != last1 ) {
if ( first2 == last2 )
return std::copy ( first1 , last1 , result );
* result ++ = * first2 < * first1 ? * first2 ++ : * first1 ++ ;
}
return std::copy ( first2 , last2 , result );
}
template < class InputIterator1 , class InputIterator2 , class OutputIterator ,
class Compare >
OutputIterator merge ( InputIterator1 first1 , InputIterator1 last1 ,
InputIterator2 first2 , InputIterator2 last2 ,
OutputIterator result , Compare comp )
{
while ( first1 != last1 ) {
if ( first2 == last2 )
return std::copy ( first1 , last1 , result );
* result ++ = comp ( * first2 , * first1 ) ? * first2 ++ : * first1 ++ ;
}
return std::copy ( first2 , last2 , result );
}
関連項目
参照