std::merge

헤더 `<algorithm>`
template< class InputIt1, class InputIt2, class OutputIt > OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );	에 정의됨 (1)	(C++20부터 constexpr)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3 > ForwardIt3 merge( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first );	(2)	(C++17부터)
template< class InputIt1, class InputIt2, class OutputIt, class Compare > OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );	(3)	(C++20부터 constexpr)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3, class Compare > ForwardIt3 merge( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first, Compare comp );	(4)	(C++17부터)

두 개의 정렬된 범위 [first1, last1)와 [first2, last2)을 d_first에서 시작하는 하나의 정렬된 범위로 병합합니다.

1) [first1, last1) 또는 [first2, last2)이 에 대해 정렬되지 않은 경우 (C++20까지)operator<(C++20부터)std::less{}, 동작이 정의되지 않습니다.3)

또는 [first1, last1)이 [first2, last2)에 대해 정렬되지 않은 경우, 동작이 정의되지 않습니다.comp2,4)

(1,3)과 동일하지만, 에 따라 실행됩니다.policy 이러한 오버로드는 다음 표현식의 값이

인 경우에만 오버로드 해결에 참여합니다: true(C++20까지)

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(C++20부터)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	이 병합 함수는 안정적입니다. 즉, 원래 두 범위에서 동등한 요소에 대해 첫 번째 범위의 요소(원래 순서 유지)가 두 번째 범위의 요소(원래 순서 유지)보다 앞에 옵니다.

출력 범위가

또는 [first1, last1)과 겹치면 동작이 정의되지 않습니다. [first2, last2)목차

first1, last1

-	병합할 첫 번째	요소 범위를 정의하는 반복자 쌍 first2, last2
-	병합할 두 번째	요소 범위를 정의하는 반복자 쌍 d_first
-	대상 범위의 시작	policy
-	사용할	실행 정책 comp
-	비교 함수 객체 (즉,	Compare의 요구 사항을 충족하는 객체)로, 첫 번째 인수가 두 번째 인수보다 작은`true` 경우 (즉, 보다 앞에 정렬됨) 을 반환합니다. 비교 함수의 시그니처는 다음과 동등해야 합니다: 시그니처에 `bool cmp(const Type1& a, const Type2& b);` 이 있을 필요는 없지만, 함수는 전달된 객체를 수정해서는 안 되며 `const&`값 범주`Type1`에 관계없이 (const일 수 있는) `Type2` 및 유형의 모든 값을 받아들일 수 있어야 합니다 (따라서 은 허용되지 않으며`Type1&`, 도 `Type1`에 대해 이동이 복사와 동등한 경우가 아니면 허용되지 않습니다`Type1`(C++11부터)). 유형과 `Type1` 유형은 `Type2`와 `InputIt1` 유형의 객체를 역참조한 후 `InputIt2`와 `Type1` 모두로 암시적으로 변환될 수 있어야 합니다. `Type2`
유형 요구 사항
- `InputIt1, InputIt2`LegacyInputIterator의 요구 사항을 충족해야 합니다.
- `ForwardIt1, ForwardIt2, ForwardIt3`LegacyForwardIterator의 요구 사항을 충족해야 합니다.
- `OutputIt`LegacyOutputIterator의 요구 사항을 충족해야 합니다.
- `Compare`Compare의 요구 사항을 충족해야 합니다.

반환값

마지막으로 복사된 요소의 다음 요소를 가리키는 출력 반복자.

복잡도

$\scriptsize N_1$ $N 1$ 이 std::distance(first1, last1)이고 $\scriptsize N_2$ $N 2$ 이 std::distance(first2, last2)일 때:

1) 최대

N 1 +N 2 -1

번의 비교 (operator< 사용) (C++20까지)std::less{}(C++20부터).

2)

O(N 1 +N 2)

번의 비교 (operator< 사용) (C++20까지)std::less{}(C++20부터).

3) 최대

N 1 +N 2 -1

번의 비교 함수 comp 적용.

4)

O(N 1 +N 2)

번의 비교 함수 comp 적용.

예외

ExecutionPolicy라는 템플릿 매개변수가 있는 오버로드는 다음과 같이 오류를 보고합니다:

알고리즘의 일부로 호출된 함수의 실행이 예외를 발생시키고 ExecutionPolicy이 표준 정책 중 하나이면 std::terminate이 호출됩니다. 다른 ExecutionPolicy의 경우 동작은 구현에서 정의됩니다.
알고리즘이 메모리 할당에 실패하면 std::bad_alloc이 발생합니다.

가능한 구현

libstdc++ 및 libc++의 구현도 참조하십시오.

merge (1)

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

merge (3)

template<class InputIt1, class InputIt2,
         class OutputIt, class Compare>
OutputIt merge(InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2,
               OutputIt d_first, Compare comp)
{
    for (; first1 != last1; ++d_first)
    {
        if (first2 == last2)
            return std::copy(first1, last1, d_first);
        
        if (comp(*first2, *first1))
        {
            *d_first = *first2;
            ++first2;
        }
        else
        {
            *d_first = *first1;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}

참고

이 알고리즘은 std::set_union과 유사한 작업을 수행합니다. 둘 다 두 개의 정렬된 입력 범위를 소비하고 두 입력의 요소로 정렬된 출력을 생성합니다. 이 두 알고리즘의 차이점은 동등하게 비교되는 두 입력 범위의 값 처리 방식에 있습니다 (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 <functional>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>

auto print = [](const auto rem, const auto& v)
{
    std::cout << rem;
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
};

int main()
{
    // fill the vectors with random numbers
    std::random_device rd;
    std::mt19937 mt(rd());
    std::uniform_int_distribution<> dis(0, 9);
    
    std::vector<int> v1(10), v2(10);
    std::generate(v1.begin(), v1.end(), std::bind(dis, std::ref(mt)));
    std::generate(v2.begin(), v2.end(), std::bind(dis, std::ref(mt)));
    
    print("Originally:\nv1: ", v1);
    print("v2: ", v2);
    
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
    
    print("After sorting:\nv1: ", v1);
    print("v2: ", v2);
    
    // merge
    std::vector<int> dst;
    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dst));
    
    print("After merging:\ndst: ", dst);
}

가능한 출력:

Originally:
v1: 2 6 5 7 4 2 2 6 7 0
v2: 8 3 2 5 0 1 9 6 5 0
After sorting:
v1: 0 2 2 2 4 5 6 6 7 7
v2: 0 0 1 2 3 5 5 6 8 9
After merging:
dst: 0 0 0 1 2 2 2 2 3 4 5 5 5 6 6 6 7 7 8 9

결함 보고서

다음 동작 변경 결함 보고서는 이전에 게시된 C++ 표준에 소급하여 적용되었습니다.

DR	적용 대상	게시된 동작	올바른 동작
LWG 780	C++98	병합 연산이 정의되지 않음	정의됨

같이 보기

inplace_merge	두 개의 정렬된 범위를 제자리에서 병합 (함수 템플릿 & 알고리즘 함수 객체)
ranges::inplace_merge (C++20)	두 개의 정렬된 범위를 제자리에서 병합 (함수 템플릿 & 알고리즘 함수 객체)
is_sorted (C++11)	범위가 정렬되었는지 확인 (함수 템플릿 & 알고리즘 함수 객체)
ranges::is_sorted (C++20)	범위가 정렬되었는지 확인 (함수 템플릿 & 알고리즘 함수 객체)
set_union	두 집합의 합집합 계산 (함수 템플릿 & 알고리즘 함수 객체)
ranges::set_union (C++20)	두 집합의 합집합 계산 (함수 템플릿 & 알고리즘 함수 객체)
sort	요소 범위 정렬 (함수 템플릿 & 알고리즘 함수 객체)
ranges::sort (C++20)	요소 범위 정렬 (함수 템플릿 & 알고리즘 함수 객체)
stable_sort	동등한 요소 간의 상대적 순서를 유지하면서 요소 범위 정렬 (함수 템플릿 & 알고리즘 함수 객체)
ranges::stable_sort (C++20)	동등한 요소 간의 상대적 순서를 유지하면서 요소 범위 정렬 (함수 템플릿 & 알고리즘 함수 객체)
ranges::merge (C++20)	두 정렬된 범위 병합 (알고리즘 함수 객체)

컴파일러 지원
프리스탠딩 및 호스티드
언어
표준 라이브러리
표준 라이브러리 헤더
명명된 요구 사항
기능 테스트 매크로 (C++20)
언어 지원 라이브러리
개념 라이브러리 (C++20)
진단 라이브러리
메모리 관리 라이브러리
메타프로그래밍 라이브러리 (C++11)
일반 유틸리티 라이브러리
컨테이너 라이브러리
반복자 라이브러리
범위 라이브러리 (C++20)
알고리즘 라이브러리
문자열 라이브러리
텍스트 처리 라이브러리
수치 라이브러리
날짜 및 시간 라이브러리
입출력 라이브러리
파일 시스템 라이브러리 (C++17)
동시성 지원 라이브러리 (C++11)
실행 제어 라이브러리 (C++26)
기술 명세서
기호 색인
외부 라이브러리

ko.cppreference.net

Namespaces

Variants

std::merge

1

first1, last1

반환값

복잡도

예외

가능한 구현

참고

예제

결함 보고서

같이 보기