merge
merge (두 정렬 범위 병합)
두 개의 정렬된 범위를 병합해 하나의 정렬된 출력 범위로 만드는 알고리즘이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
merge는 정렬된 [first1, last1)과 [first2, last2)를 병합해 정렬된 결과를 d_first부터 써 내려가요.
template< class InputIt1, class InputIt2, class OutputIt >
OutputIt merge( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first ); // (1)
비교기 버전도 있어요.
template< class InputIt1, class InputIt2, class OutputIt, class Compare >
OutputIt merge( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first, Compare comp ); // (2)
두 입력 범위는 반드시 정렬되어 있어야 해요. 출력은 전체적으로 정렬된 시퀀스예요. 소스와 출력이 겹치면 안 돼요.
-
operator<로, 2)comp로 비교해요.
- 복잡도:
N1 + N2번의 비교(N1, N2는 각 범위 크기). - 반환 값: 마지막으로 쓴 출력 다음 반복자.
std::vector<int> a{1, 3, 5}, b{2, 4, 6};
std::vector<int> out(6);
std::merge(a.begin(), a.end(), b.begin(), b.end(), out.begin());
// out == {1,2,3,4,5,6}
이미 정렬된 두 시퀀스를 합쳐 정렬을 유지할 때 써요. 파생된 목록/스트림 병합에 자주 사용돼요.