C++ order_of_key() 함수 완벽 정리 – 개념부터 예제까지

C++에서 order_of_key()란 무엇인가?

이 글에서는 C++의 order_of_key() 함수에 대해 자세히 알아보겠습니다.

order_of_key()는 정렬된 집합(ordered set)에서 매개변수로 전달받은 키(key)보다 작은 원소의 개수를 반환하는 함수입니다. 이 함수는 C++ 표준 라이브러리가 아닌, GCC 컴파일러가 제공하는 GNU PBDS(Policy-Based Data Structures) 라이브러리에 포함되어 있으며, 주로 경쟁 프로그래밍에서 순위 통계 기능이 필요할 때 유용하게 활용됩니다.

예를 들어, 집합에 {2, 4, 5, 6}이 저장되어 있다면 order_of_key(6)은 6보다 작은 원소인 2, 4, 5의 개수인 3을 반환합니다.

주요 특징

• 키 자체가 집합에 존재하지 않아도 결과를 계산할 수 있습니다.
• 레드-블랙 트리(rb_tree_tag) 기반으로 구현되어 삽입·삭제·조회 모두 O(log n)의 시간 복잡도를 가집니다.
• tree_order_statistics_node_update 정책을 지정해야 해당 함수를 사용할 수 있습니다.

예제 코드

#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

// 정렬된 집합(ordered set) 초기화
typedef tree<int, null_type, less<int>, rb_tree_tag,
    tree_order_statistics_node_update>
    ordered_set;

int main(){
    ordered_set mySet;
    mySet.insert(5);
    mySet.insert(2);
    mySet.insert(6);
    mySet.insert(4);

    cout << "6보다 작은 원소의 개수 :: " << mySet.order_of_key(6) << endl;
    cout << "7보다 작은 원소의 개수 :: " << mySet.order_of_key(7) << endl;
    return 0;
}

실행 결과

6보다 작은 원소의 개수 :: 3
7보다 작은 원소의 개수 :: 4

결과 분석

집합에는 2, 4, 5, 6 네 개의 원소가 저장되어 있습니다.

• order_of_key(6): 6보다 작은 원소는 2, 4, 5로 총 3개입니다. 키와 같은 값인 6은 포함되지 않습니다.
• order_of_key(7): 7보다 작은 원소는 2, 4, 5, 6으로 총 4개입니다. 참고로 7은 집합에 존재하지 않지만, 함수는 정상적으로 동작합니다.

마무리

order_of_key()는 단순한 멤버 검색을 넘어, 특정 값의 순위(rank)를 O(log n) 시간에 구할 수 있는 강력한 도구입니다. find_by_order() 함수와 함께 사용하면 k번째로 작은 원소 조회 등 다양한 통계 연산을 효율적으로 처리할 수 있으니, 알고리즘 문제 풀이에 적극 활용해 보시기 바랍니다.