名前空間
変種
操作

std::merge

提供: cppreference.com
< cpp‎ | algorithm

 
 
アルゴリズムライブラリ
機能します
Original:
Functions
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
シーケンス動作を非改変
Original:
Non-modifying sequence operations
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
シーケンス動作を変更する
Original:
Modifying sequence operations
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
操作を仕切る
Original:
Partitioning operations
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
(ソートされた範囲で)ソート操作
Original:
Sorting operations (on sorted ranges)
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
バイナリ検索操作(ソート範囲で)
Original:
Binary search operations (on sorted ranges)
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
(ソートされた範囲で)操作を設定します
Original:
Set operations (on sorted ranges)
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
ヒープ操作
Original:
Heap operations
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
最小値/最大値操作
Original:
Minimum/maximum operations
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
数値演算
Original:
Numeric operations
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
Cライブラリ
Original:
C library
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
 
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を使用しています。同等の要素の相対的な順序は保持されます.
Original:
Merges two sorted ranges [first1, last1) and [first2, last2) into one sorted range beginning at d_first. The first version uses operator< to compare the elements, the second version uses the given comparison function comp. The relative order of equivalent elements is preserved.
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

目次

[編集] パラメータ

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. ​

型の要件
-
InputIt1InputIterator

の要求を満足しなければなりません。

-
InputIt2InputIterator

の要求を満足しなければなりません。

-
OutputItOutputIterator

の要求を満足しなければなりません。

[編集] 値を返します

最後の要素は、過去の要素への出力イテレータは、コピーされた.
Original:
An output iterator to element past the last element copied.
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

[編集] 複雑

最もstd::distance(first1, last1) + std::distance(first2, last2) + 1比較で.
Original:
At most std::distance(first1, last1) + std::distance(first2, last2) + 1 comparisons.
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

[編集] 可能な実装

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

[編集] も参照してください

その場で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]
昇順にソートする範囲
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]
ソートされた範囲の要素を等しい要素間の順序を維持しながら
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]