std:: set_union

ソート済みの和集合を 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++規格に対して遡及的に適用されました。

関連項目