Merge

정렬된 2개의 소스 범위의 모든 요소를 단일 정렬된 대상 범위로 결합합니다. 이 경우 순서 기준은 이항 술어로 지정될 수 있습니다.

template <class In1, class In2, class Out>
Out Merge (
    In1                 first1,
    In1                 last1,
    In2                 first2,
    In2                 last2,
    Out                 res
);

template <class In1, class In2, class Out, class BinPred>
Out Merge (
    In1                 first1,
    In1                 last1,
    In2                 first2,
    In2                 last2,
    Out                 res,
    BinPred             cmp
);

Template 파라미터

In1

입력 반복자입니다.

In2

입력 반복자입니다.

Out

출력 반복자입니다.

BinPred

이항 술어(Binary predicate)입니다.

파라미터

first1

단일 범위로 결합되고 정렬될 2개의 정렬된 소스 범위들 중 1번째 범위의 1번째 요소의 위치를 설명하는 입력 반복자입니다.

last1

단일 범위로 결합되고 정렬될 2개의 정렬된 소스 범위들 중 1번째 범위의 마지막 직전 요소의 위치를 설명하는 입력 반복자입니다.

first2

단일 범위로 결합되고 정렬될 2개의 정렬된 소스 범위들 중 2번째 범위의 1번째 요소의 위치를 설명하는 입력 반복자입니다.

last2

단일 범위로 결합되고 정렬될 2개의 정렬된 소스 범위들 중 2번째 범위의 마지막 직전 요소의 위치를 설명하는 입력 반복자입니다.

res

2개의 소스 범위들이 단일 정렬된 범위로 결합될 목적지 범위에서 1번째 요소의 위치를 설명하는 출력 반복자입니다.

cmp

어떤 요소가 다른 요소보다 크다는 의미를 정의하는 사용자 정의 술어 함수 객체입니다. 이항 술어(binary predicate)는 2개의 인자를 취하며 1번째 요소가 2번째 요소보다 작을 경우 true를, 그 외에는 false를 리턴합니다.

리턴 값

정렬된 목적지 범위에서 마지막 직전 요소의 위치를 알려주는 출력 반복자입니다.

설명

Merge는 2개의 정렬된 범위 [first1, last1)과 [first2, last2)를 단일 정렬된 범위로 결합합니다. 즉, [first1, last1)과 [first2, last2)의 요소들을 [result, result + (last1 - first1) + (last2 - first2))로 복사하여 결과 범위가 오름차순이 됩니다. Merge는 안정적입니다. 이것은 각 입력 범위 안의 요소들의 상대적인 순서가 보존되며, 두 입력 범위들의 같은 요소들에 대하여 1번째 범위의 요소가 2번째 범위의 요소보다 앞선다는 것을 의미합니다. 리턴 값은 result + (last1 - first1) + (last2 - first2)입니다. Merge의 2가지 버전들은 요소들을 어떻게 비교하느냐에 따라 다릅니다. 1번째 버전은 operator<를 사용합니다. 즉, 입력 범위와 출력 범위는 반복자 i와 j의 모든 쌍에 대하여 i가 j보다 앞서고, *j < *i가 false라는 조건을 만족합니다. 2번째 버전은 술어 pred를 사용합니다. 즉, 입력 범위와 출력 범위는 반복자 i와 j의 모든 쌍에 대하여 i가 j보다 앞서고, pred(*j, *i)가 false라는 조건을 만족합니다.

참고사항

알고리즘