C++ 순서 있는 집합(Ordered Set)과 GNU PBDS 완벽 가이드

이 튜토리얼에서는 순서 있는 집합(Ordered Set)과 GNU C++ PBDS(Policy-Based Data Structures)에 대해 알아보겠습니다.

순서 있는 집합이란?

순서 있는 집합은 STL 라이브러리의 일반적인 컨테이너와 달리, GNU PBDS에서 제공하는 정책 기반(policy-based) 자료구조입니다. 일반적인 std::set과 마찬가지로 모든 요소를 정렬된 상태로 유지하며 중복 값을 허용하지 않지만, STL에는 없는 강력한 기능 두 가지를 추가로 제공합니다.

• find_by_order(k): k번째 인덱스(0부터 시작)에 위치한 요소의 반복자를 반환합니다.
• order_of_key(x): x보다 작은 요소의 개수를 반환합니다.

두 연산 모두 내부적으로 레드-블랙 트리(red-black tree)를 기반으로 하며 O(log n) 시간 복잡도로 수행됩니다.

예제 코드

#include <iostream>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

int main(){
    // 순서 있는 집합 선언
    ordered_set o_set;
    o_set.insert(5);
    o_set.insert(1);
    o_set.insert(2);

    // 인덱스 1의 요소 출력 (현재 집합: {1, 2, 5})
    cout << *(o_set.find_by_order(1)) << endl;

    // 4보다 작은 요소의 개수 출력
    cout << o_set.order_of_key(4) << endl;

    // 5보다 작은 요소의 개수 출력
    cout << o_set.order_of_key(5) << endl;

    // 값 2가 존재하면 삭제
    if (o_set.find(2) != o_set.end())
        o_set.erase(o_set.find(2));

    // 삭제 후 인덱스 1의 요소 출력 (현재 집합: {1, 5})
    cout << *(o_set.find_by_order(1)) << endl;

    // 삭제 후 4보다 작은 요소의 개수 출력
    cout << o_set.order_of_key(4) << endl;

    return 0;
}

실행 결과

2
2
2
5
1

코드 설명

요소 5, 1, 2를 삽입하면 집합은 항상 {1, 2, 5}로 정렬된 상태를 유지합니다.

1. find_by_order(1)은 인덱스 1에 해당하는 값 2를 반환합니다.
2. order_of_key(4)는 4보다 작은 요소가 1과 2, 총 2개이므로 2를 반환합니다.
3. order_of_key(5)는 5보다 작은 요소가 역시 2개이므로 2를 반환합니다.

값 2를 삭제한 후에는 집합이 {1, 5}가 되므로, find_by_order(1)은 5를 반환하고, order_of_key(4)는 1개만 남아 1을 반환합니다.

활용 분야

순서 있는 집합은 특정 순위의 요소 조회나, 어떤 값보다 작은 원소의 개수를 빠르게 구해야 하는 문제에서 유용합니다. 대표적으로 경쟁 프로그래밍에서 구간 통계, 순위 계산, 역방향 반복 없이 k번째 요소를 찾는 문제 등에 널리 활용됩니다.