std:: set_union

정렬된 범위 [ first1 , last1 ) 와 [ first2 , last2 ) 중 하나 또는 둘 모두에 존재하는 요소들의 집합으로 구성된 정렬된 합집합을 d_first 에서 시작하여 구성합니다.

만약 [ 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++ 표준에 소급 적용되었습니다.

참고 항목