std::set_union

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

template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2, class ForwardIt3 >
ForwardIt3 set_union( ExecutionPolicy&& policy,
                      ForwardIt1 first1, ForwardIt1 last1,
                      ForwardIt2 first2, ForwardIt2 last2,
                      ForwardIt3 d_first );

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

template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2,
          class ForwardIt3, class Compare >
ForwardIt3 set_union( ExecutionPolicy&& policy,
                      ForwardIt1 first1, ForwardIt1 last1,
                      ForwardIt2 first2, ForwardIt2 last2,
                      ForwardIt3 d_first, Compare comp );

d_first から始まるソート済みの和集合を構築します。この和集合は、ソート済み範囲 [first1, last1) と [first2, last2) の一方または両方に存在する要素の集合から構成されます。

[first1, last1) に互いに同等な要素が m 個あり、[first2, last2) にそれらと同等な要素が n 個ある場合、すべての m 個の要素が [first1, last1) から出力範囲に順序を保ってコピーされ、その後、残りの std::max(n - m, 0) 個の要素が [first2, last2) から出力範囲に、やはり順序を保ってコピーされます。

と重なる場合、動作は未定義です。 [first1, last1)[first2, last2)

パラメータ

戻り値

構築された範囲の終端を超えるイテレータ。

計算量

\(\scriptsize N_1\) N 1 を std:: distance ( first1, last1 ) として、 \(\scriptsize N_2\) N 2 を std:: distance ( first2, last2 ) として定義する：

例外

ExecutionPolicyという名前のテンプレートパラメータを持つオーバーロードは、 以下のようにエラーを報告します：

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

実装例

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_union(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++;
        else
        {
            *d_first = *first1;
            if (!(*first1 < *first2))
                ++first2;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}

template<class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt set_union(InputIt1 first1, InputIt1 last1,
                   InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp)
{
    for (; first1 != last1; ++d_first)
    {
        if (first2 == last2)
            // 範囲2が終了、範囲1の残りを出力:
            return std::copy(first1, last1, d_first);
        if (comp(*first2, *first1))
            *d_first = *first2++;
        else
        {
            *d_first = *first1;
            if (!comp(*first1, *first2)) // 等価 => *first2を含める必要なし
                ++first2;
            ++first1;
        }
    }
    // 範囲1が終了、範囲2の残りを出力:
    return std::copy(first2, last2, d_first);
}

注記

このアルゴリズムは std::merge と同様の処理を実行します。両方とも2つのソート済み入力範囲を消費し、両方の入力からの要素を含むソート済み出力を生成します。これら2つのアルゴリズムの違いは、等価と比較される両方の入力範囲からの値の扱いです（ LessThanComparable に関する注記を参照）。等価な値が最初の範囲に 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 はより少ない数を出力する可能性があります。

例

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
void println(const std::vector<int>& v)
{
    for (int i : v)
        std::cout << i << ' ';
    std::cout << '\n';
}
int main()
{
    std::vector<int> v1, v2, dest;
    v1 = {1, 2, 3, 4, 5};
    v2 = {3, 4, 5, 6, 7};
    std::set_union(v1.cbegin(), v1.cend(),
                   v2.cbegin(), v2.cend(),
                   std::back_inserter(dest));
    println(dest);
    dest.clear();
    v1 = {1, 2, 3, 4, 5, 5, 5};
    v2 = {3, 4, 5, 6, 7};
    std::set_union(v1.cbegin(), v1.cend(),
                   v2.cbegin(), v2.cend(),
                   std::back_inserter(dest));
    println(dest);
}

1 2 3 4 5 6 7 
1 2 3 4 5 5 5 6 7

不具合報告

以下の動作変更の欠陥報告書は、以前に公開されたC++規格に対して遡及的に適用されました。

関連項目