이 글에서는 C++ STL의 forward_list::merge() 함수가 어떻게 동작하는지, 그 문법은 어떤지, 그리고 실제 활용 예제를 통해 자세히 알아보겠습니다.
STL에서 forward_list란 무엇인가?
forward_list는 시퀀스 컨테이너(sequence container)로, 시퀀스 내 임의의 위치에서 상수 시간(constant time)에 삽입(insert)과 삭제(erase) 연산을 수행할 수 있는 자료구조입니다. forward_list는 단일 연결 리스트(singly-linked list)로 구현되며, 각 요소가 다음 요소를 가리키는 링크(link)의 연결을 통해 순서가 유지됩니다.
forward_list::merge()란?
forward_list::merge()는 C++ STL에 내장된 함수로, 헤더 파일에 선언되어 있습니다. 이 함수는 정렬된 두 개의 forward_list를 하나로 병합하는 데 사용됩니다.
두 리스트를 병합하기 전에는 반드시 각 리스트가 이미 정렬되어 있는지 확인해야 합니다. 비교자(comparator)를 전달하지 않으면 두 리스트를 하나의 정렬된 리스트로 병합하며, 두 리스트 간의 내부적인 비교 로직이 필요한 경우에는 반드시 비교자를 추가해야 합니다.
문법(Syntax)
flist_container1.merge(flist_container2); // 두 리스트를 병합 flist_container1.merge(flist_container2, comparator); // 비교자와 함께 병합
이 함수는 아래 매개변수 중 하나 또는 두 개를 모두 받을 수 있습니다.
매개변수(Parameters)
list_container2 − 병합 대상이 되는 두 번째 리스트의 객체입니다.
comparator − 내부 비교 방식을 정의합니다. 이는 이진 술어(binary predicate)로, 리스트 컨테이너에 정의된 것과 동일한 타입의 입력값 두 개를 받습니다. list_container1의 요소가 list_container2의 요소보다 앞에 와야 한다고 판단되면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
반환 값(Return Value)
이 함수는 아무것도 반환하지 않습니다(void). 병합 결과는 호출한 첫 번째 리스트에 직접 저장되며, 두 번째 리스트는 비워지게 됩니다.
예제 1: 기본적인 병합
/* 아래 코드에서는 정렬된 값을 담은 두 개의 forward_list를 생성하고, C++의 merge() 함수를 사용하여 두 리스트를 정렬된 상태로 병합합니다. */
#include <bits/stdc++.h>
using namespace std;
int main() {
// 정렬된 값들을 삽입하여 forward_list 생성
forward_list<int> myForwardList1 = { 1, 3, 5, 7 };
forward_list<int> myForwardList2 = { 2, 4, 6 };
// 정렬된 두 forward_list 병합
myForwardList1.merge(myForwardList2);
cout << "elements after merging" << endl;
for (auto i = myForwardList1.begin(); i != myForwardList1.end(); ++i)
cout << *i << " ";
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
elements after merging 1 2 3 4 5 6 7
예제 2: 비교자(comparator) 없이 정렬 후 병합
/* 아래 코드에서는 정렬되지 않은 두 개의 forward_list를 생성하고, 먼저 sort() 함수로 각 리스트를 정렬한 뒤 merge() 함수를 사용하여 병합합니다. 최종 결과 역시 정렬된 상태로 유지됩니다. */
#include <bits/stdc++.h>
using namespace std;
int main (){
// 정렬되지 않은 forward_list 생성
forward_list<int> myForwardList1 = {3, 2, 9};
forward_list<int> myForwardList2 = {8, 1, 2};
// sort() 함수를 사용하여 forward_list 정렬
myForwardList1.sort();
myForwardList2.sort();
myForwardList1.merge(myForwardList2);
cout << "Elements after merging" << endl;
for (auto i = myForwardList1.begin(); i != myForwardList1.end(); ++i)
cout << *i << " ";
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Elements after merging 1 2 2 3 8 9
마무리
forward_list::merge() 함수는 정렬된 두 리스트를 효율적으로 하나로 합칠 수 있는 강력한 도구입니다. 단, 병합 전에 각 리스트가 반드시 정렬되어 있어야 하며, 필요에 따라 사용자 정의 비교자를 활용하면 다양한 정렬 기준으로 병합할 수 있다는 점을 기억하세요.