이 글에서는 C++ STL에서 제공하는 list::merge() 함수의 동작 원리, 문법 그리고 실제 사용 예제를 자세히 살펴보겠습니다.
STL에서 리스트(List)란 무엇인가?
리스트는 시퀀스 내 임의의 위치에서 상수 시간(constant time)에 삽입과 삭제를 수행할 수 있는 자료구조입니다. 내부적으로는 이중 연결 리스트(doubly linked list)로 구현되어 있어 메모리 할당이 연속적이지 않아도 됩니다.
리스트는 배열(array), 벡터(vector), 덱(deque)과 비교했을 때 컨테이너의 어느 위치에서든 요소를 삽입, 추출, 이동하는 작업에서 더 뛰어난 성능을 보여줍니다. 다만 요소에 직접 접근하는 속도는 느린 편입니다. 리스트는 forward_list와 유사하지만, forward_list는 단일 연결 리스트(singly linked list)로 구현되어 있어 앞쪽 방향으로만 순회할 수 있다는 차이점이 있습니다.
list::merge()란 무엇인가?
list::merge()는 C++ STL에 내장된 함수로, <list> 헤더 파일에 선언되어 있습니다. merge()는 두 개의 리스트를 하나로 병합하는 데 사용됩니다. 단순히 두 리스트를 합칠 수도 있고, 추가적인 비교 로직이 필요하다면 비교자(comparator)를 인자로 전달할 수도 있습니다.
주의: 두 리스트를 병합하기 전에는 반드시 각 리스트가 이미 정렬된 상태여야 합니다. 비교자를 전달하지 않으면 두 리스트가 하나의 정렬된 리스트로 병합되며, 리스트 간의 세부적인 비교 규칙이 필요한 경우에는 반드시 비교자를 함께 지정해야 합니다.
문법(Syntax)
list_container1.merge(list_container2); // 두 리스트를 list_container1에 병합 list_container1.merge(list_container2, comparator);
이 함수는 한 개 또는 두 개의 매개변수를 받을 수 있습니다.
매개변수
list_container2 − 병합 대상이 되는 두 번째 리스트 객체입니다.
comparator − 내부 비교 방식을 정의합니다. 리스트 컨테이너에 저장된 값과 동일한 타입의 입력 두 개를 받는 이항 조건자(binary predicate)로, list_container1의 요소가 list_container2의 요소보다 앞에 와야 한다면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
반환 값(Return Value)
이 함수는 아무 값도 반환하지 않습니다. 병합 결과는 호출한 리스트(list_container1)에 직접 반영되며, list_container2의 모든 요소는 병합 후 비워집니다.
비교자 없이 사용하기
예제
아래 코드에서는 두 개의 정렬된 리스트를 생성하고, 이를 병합하여 결과 역시 정렬된 상태를 유지하도록 만듭니다.
#include <bits/stdc++.h>
using namespace std;
int main(){
// 정렬된 리스트 생성
list<int> myList_1 = {2, 4, 6, 8 };
list<int> myList_2 = {1, 3, 5, 7 };
// merge() 함수를 사용해 리스트 병합
myList_2.merge(myList_1);
cout <<"Lists after merging : ";
for(auto i = myList_2.begin(); i != myList_2.end(); ++i)
cout << *i << " ";
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Lists after merging : 1 2 3 4 5 6 7 8
비교자(Comparator)와 함께 사용하기
예제
아래 코드에서는 두 개의 리스트를 병합하고, 비교자를 활용해 최종 결과 리스트를 원하는 기준으로 정렬합니다.
#include <bits/stdc++.h>
using namespace std;
bool compare(int myList_1, int myList_2){
return ( int(myList_1)<int(myList_2) );
}
int main(){
// 리스트 생성
list<int> myList_1 = {2, 4, 1 };
list<int> myList_2 = {7, 6, 5 };
myList_1.sort();
myList_2.sort();
// merge() 함수를 사용해 리스트 병합
myList_1.merge(myList_2);
myList_2.push_back (3);
myList_1.merge(myList_2,compare);
cout<<"List Elements are : ";
for(auto i = myList_1.begin(); i!=myList_1.end(); ++i)
cout<< ' ' << *i;
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
List Elements are : 1 2 3 4 5 6 7
정리
C++ STL의 list::merge() 함수는 두 개의 정렬된 리스트를 효율적으로 하나로 합치는 강력한 도구입니다. 기본 오름차순 병합은 물론, 커스텀 비교자를 통해 다양한 정렬 기준을 적용할 수 있으므로 실무에서 정렬된 데이터를 다룰 때 매우 유용하게 활용할 수 있습니다.