• Class / Function / Type

      std::
    • Header file

      <>
    • Other / All

    最終更新日時(UTC):
    が更新

    履歴 編集

    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++03
    
      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++03
    
      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) の2つの要素を全て [result,result_last) へコピーする。その際に、is_sorted(result, result_last) または is_sorted(result, result_last, comp) の条件を満たすようにコピーする(result_lastresult + (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>
    
    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);
    }
    

    関連項目

    参照