C++에서 set, unordered_set 및 priority_queue 학습

Source: Dev.to

set

개요

• 고유하고 정렬된 데이터
• 고유한 원소만 저장
• 정렬된 순서 유지
• 자체 균형 BST(Red‑Black Tree)를 사용해 구현

예제

std::set

#include 
#include 

int main() {
    std::set s = {3, 1, 2, 2};
    for (int x : s) std::cout 
}

std::unordered_set

#include 

int main() {
    std::unordered_set us = {3, 1, 2, 2};
    for (int x : us) std::cout 
}

std::priority_queue (max‑heap)

int main() {
    std::priority_queue pq;
    pq.push(3);
    pq.push(1);
    pq.push(5);
    std::cout 
}

Min‑heap with std::greater

#include 
#include 

std::priority_queue, std::greater> minHeap;

복잡도

• 삽입 / 삭제: O(log n)
• 최상위 원소 조회: O(1)
• 공간: O(n)

사용 시점

• k번째 최대/최소 원소가 필요할 때
• 최대/최소 원소를 반복적으로 추출할 때
• 스케줄링 및 탐욕 알고리즘 문제