multiset 기본 개념

multiset은 C++ 표준 라이브러리의 연관 컨테이너로, 중복된 값을 허용하는 정렬된 집합을 제공합니다. 내부적으로 레드-블랙 트리로 구현되어 있어 삽입, 삭제, 검색 연산이 O(log n) 시간 복잡도를 보장합니다.

선언 및 정렬 방식

// 오름차순 정렬 (기본값)
multiset<int> ms_asc;
// 동일: multiset<int, less<int>> ms_asc;

// 내림차순 정렬
multiset<int, greater<int>> ms_desc;

핵심 멤버 함수

사용 예시

#include <bits/stdc++.h>
using namespace std;

int main() {
    multiset<int> scores;
    
    // 데이터 삽입
    scores.insert(85);
    scores.insert(92);
    scores.insert(78);
    scores.insert(92);  // 중복 허용
    
    // 순회 (오름차순)
    for (int grade : scores) {
        cout << grade << " ";  // 78 85 92 92
    }
    cout << "\n";
    
    // 특정 값 개수 확인
    cout << scores.count(92) << "\n";  // 2
    
    // 범위 검색
    auto it_low = scores.lower_bound(85);   // 85
    auto it_up = scores.upper_bound(85);    // 92
    
    // 이전 원소 찾기
    if (it_low != scores.begin()) {
        auto prev = it_low;
        --prev;
        cout << "이전 값: " << *prev << "\n";  // 78
    }
    
    // 특정 값 하나만 삭제
    auto pos = scores.find(92);
    if (pos != scores.end()) scores.erase(pos);
    
    // 해당 값 전체 삭제
    scores.erase(78);  // 78인 모든 원소 제거
    
    return 0;
}

실전 문제: 순위 관리 시스템

다음은 multiset을 활용하여 동적 순위를 관리하는 예제입니다. 주어진 연산에 따라 점수를 삽입하거나 특정 순위의 점수를 조회합니다.

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int query_cnt;
    cin >> query_cnt;
    
    multiset<ll> ranking;
    // 경계값 삽입으로 예외 처리 단순화
    ranking.insert(LLONG_MIN);
    ranking.insert(LLONG_MAX);
    
    while (query_cnt--) {
        int cmd_type;
        ll param;
        cin >> cmd_type >> param;
        
        if (cmd_type == 1) {
            // param보다 작은 원소의 개수 (순위)
            auto it = ranking.lower_bound(param);
            int rank = distance(ranking.begin(), it);
            cout << rank << '\n';
        }
        else if (cmd_type == 2) {
            // k번째로 작은 원소 출력 (1-based)
            int idx = 0;
            for (ll val : ranking) {
                if (idx == param) {
                    cout << val << '\n';
                    break;
                }
                idx++;
            }
        }
        else if (cmd_type == 3) {
            // param보다 작은 최대 원소 (전임자)
            auto it = ranking.lower_bound(param);
            --it;
            cout << *it << '\n';
        }
        else if (cmd_type == 4) {
            // param보다 큰 최소 원소 (후임자)
            auto it = ranking.upper_bound(param);
            cout << *it << '\n';
        }
        else if (cmd_type == 5) {
            // 신규 점수 삽입
            ranking.insert(param);
        }
    }
    
    return 0;
}

주의사항 및 최적화

• 반복자 무효화: erase() 호출 시 해당 반복자만 무효화되며, 다른 반복자는 유효함
• distance()의 비용: multiset은 임의 접근 불가로, distance()가 O(n). 빈번한 순위 조회 시 order statistic tree 고려
• 사용자 정의 타입: 비교 연산자(operator<) 또는 비교자(comp) 제공 필요

struct Node {
    int id, priority;
    bool operator<(const Node& other) const {
        return priority < other.priority;
    }
};

multiset<Node> task_queue;  // priority 기준 정렬