C++ STL 병합 연산 완벽 가이드 | merge(), includes(), set_union(), set_intersection(), set_difference(), inplace_merge

이 글에서는 C++의 STL(표준 템플릿 라이브러리)을 활용해 다양한 병합(merge) 연산을 수행하는 방법을 알아보겠습니다.

merge() 함수는 두 개의 정렬된 컨테이너를 하나로 합치되, 결과 컨테이너 역시 정렬된 상태를 유지하도록 병합합니다. 한편 includes() 함수는 첫 번째 컨테이너의 모든 요소가 두 번째 컨테이너 안에 포함되어 있는지 여부를 검사하는 데 사용됩니다.

예제 코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
    vector<int> v1 = {1, 3, 4, 5, 20, 30};
    vector<int> v2 = {1, 5, 6, 7, 25, 30};
    //결과를 저장할 벡터 초기화
    vector<int> v3(12);
    merge(v1.begin(), v1.end(), v2.begin(),
    v2.end(), v3.begin());
    cout << "병합 후 새 컨테이너 :\n";
    for (int &x : v3)
        cout << x << " ";
    cout << endl;
    vector<int> v4 = {1, 3, 4, 5, 6, 20, 25, 30};
    includes(v4.begin(), v4.end(), v1.begin(), v1.end())?
       cout << "v4는 v1을 포함합니다":
       cout << "v4는 v1을 포함하지 않습니다";
    return 0;
}

실행 결과

병합 후 새 컨테이너 :
1 1 3 4 5 5 6 7 20 25 30 30
v4는 v1을 포함합니다

그 외 주요 병합 관련 함수

STL에는 위 함수들 외에도 집합 연산과 제자리 병합을 지원하는 유용한 알고리즘이 있습니다.

set_union()

두 정렬된 컨테이너의 합집합을 계산하여 결과 컨테이너에 저장합니다. 양쪽에 공통으로 존재하는 요소는 중복 없이 한 번만 포함됩니다.

set_intersection()

두 정렬된 컨테이너의 교집합, 즉 양쪽 모두에 존재하는 요소만 추출하여 결과 컨테이너에 저장합니다.

set_difference()

첫 번째 컨테이너에는 있지만 두 번째 컨테이너에는 없는 요소들, 즉 차집합을 구하여 결과 컨테이너에 저장합니다.

inplace_merge()

하나의 컨테이너 내부에서 각각 정렬되어 있는 두 구간을 제자리에서(in-place) 하나의 정렬된 구간으로 병합합니다. 추가 메모리 없이 기존 컨테이너 내에서 직접 처리할 수 있다는 점이 특징입니다.

마무리

STL의 병합 알고리즘들은 모두 입력 컨테이너가 미리 정렬되어 있다는 전제 하에 동작하므로, 사용 전 반드시 sort() 등으로 데이터를 정렬해 두어야 합니다. 이러한 알고리즘들을 적절히 활용하면 정렬된 데이터를 다루는 코드를 훨씬 간결하고 효율적으로 작성할 수 있습니다.