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 이 throw됩니다.

가능한 구현

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 가 수행하는 작업과 유사한 작업을 수행합니다. 둘 다 정렬된 두 입력 범위를 소비하고 두 입력의 요소들로 구성된 정렬된 출력을 생성합니다. 이 두 알고리즘의 차이는 동등하게 비교되는 양쪽 입력 범위의 값들을 처리하는 방식에 있습니다 (참고: LessThanComparable ). 만약 동등한 값들이 첫 번째 범위에서 n 번 나타나고 두 번째 범위에서 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++ 표준에 소급 적용되었습니다.

같이 보기