std::merge

Defined in header `<algorithm>`

template< class InputIt1, class InputIt2, class OutputIt > OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 OutputIt d_first );	(1)

template< class InputIt1, class InputIt2, class OutputIt, class Compare> OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 OutputIt d_first, Compare comp );	(2)

[first1, last1)と[first2, last2)d_first少なくとも1ソート範囲の先頭に2つのソートされた範囲をマージします。最初のバージョンは、要素を比較するoperator<使用して、2番目のバージョンは、指定された比較関数compを使用しています。同等の要素の相対的な順序は保持されます.

first1, last1	-	マージする要素の最初の範囲 Original: the first range of elements to merge The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions.
first2, last2	-	マージする要素の第2の範囲 Original: the second range of elements to merge The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions.
d_first	-	目的の範囲の始まり Original: the beginning of the destination range The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions.
comp	-	比較関数. 最初の値が二つ目の値より小さい場合、 trueを返します. 比較関数のシグネチャは以下と同等でなければなりません. bool cmp(const Type1 &a, const Type2 &b); シグネチャは`const`を含まなくても構いませんが, 比較関数は渡されたオブジェクトを変更してはなりません. The types Type1 and Type2 must be such that objects of types InputIt1 and InputIt2 can be dereferenced and then implicitly converted to Type1 and Type2 respectively.
型の要件
- `InputIt1` は `InputIterator` の要求を満足しなければなりません。
- `InputIt2` は `InputIterator` の要求を満足しなければなりません。
- `OutputIt` は `OutputIterator` の要求を満足しなければなりません。

[編集] 値を返します

最後の要素は、過去の要素への出力イテレータは、コピーされた.

[編集] 複雑性

最もstd::distance(first1, last1) + std::distance(first2, last2) + 1比較で.

[編集] 可能な実装

First version

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) {
            return std::copy(first1, last1, d_first);
        }
        if (*first2 < *first1) {
            *d_first = *first2;
            ++first2;
        } else {
            *d_first = *first1;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}

Second version

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) {
            return std::copy(first1, last1, d_first);
        }
        if (comp(*first2, *first1)) {
            *d_first = *first2;
            ++first2;
        } else {
            *d_first = *first1;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}

[編集] 例

このコードを実行します

#include <iostream>
#include <iterator>
#include <cstdlib>
#include <algorithm>
#include <vector>
 
int main() 
{
    const std::size_t items = 10;
 
    std::vector<int> v1, v2, dst;
 
    // fill the vectors
    for (std::size_t idx = 0; idx < items; ++idx) {
        v1.push_back(std::rand()%items);
        v2.push_back(std::rand()%items);
    }
 
    // sort
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
 
    // output v1
    std::cout << "v1 : ";
    std::copy(v1.begin(), v1.end(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
 
    // output v2
    std::cout << "v2 : ";
    std::copy(v2.begin(), v2.end(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
 
    // merge
    std::merge(v1.begin(), v1.end(),
               v2.begin(), v2.end(),
               std::back_inserter(dst));
 
    // output
    std::cout << "dst: ";
    std::copy(dst.begin(), dst.end(),
             std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
}

出力:

v1 : 0 0 2 2 3 3 3 6 7 9 
v2 : 1 2 5 5 6 6 6 6 7 9 
dst: 0 0 1 2 2 2 3 3 3 5 5 6 6 6 6 6 7 7 9 9

[編集] 参照


inplace_merge	その場で2つの順序の範囲をマージします Original: merges two ordered ranges in-place The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (関数テンプレート) [edit]

sort	昇順にソートする範囲 Original: sorts a range into ascending order The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (関数テンプレート) [edit]

stable_sort	ソートされた範囲の要素を等しい要素間の順序を維持しながら Original: sorts a range of elements while preserving order between equal elements The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (関数テンプレート) [edit]

言語
コンセプト
ユーティリティライブラリ
ストリングスライブラリ
コンテナライブラリ
アルゴリズムライブラリ
イテレータライブラリ
ニューメリックスライブラリ
入力/出力ライブラリ
ローカライゼーションライブラリ
正規表現ライブラリ (C++11)
アトミック操作ライブラリ (C++11)
スレッドのサポートライブラリ (C++11)

cppreference.com

検索

名前空間

変種

表示

操作