set과 unordered_set

기본 패턴

std::set<int> ordered{3, 1, 2};
std::unordered_set<int> fast{3, 1, 2};

설명

• 두 컨테이너 모두 중복 없는 원소 집합을 표현하지만, 내부 구조와 성질이 다릅니다.
• std::set은 보통 균형 이진 트리 기반이라 원소가 정렬된 순서로 유지되고, 탐색/삽입/삭제가 로그 시간 성능을 가집니다.
• std::unordered_set은 해시 기반이라 평균적으로 더 빠른 탐색을 기대할 수 있지만, 원소 순서는 유지되지 않습니다.
• 따라서 "정렬된 순회가 중요한가", "순서보다 빠른 membership test가 중요한가"를 보고 선택하는 것이 핵심입니다.
• 같은 값이 두 번 들어가지 않는다는 공통점 때문에, 방문 체크, 사전 중복 제거, 태그 집합 표현에 자주 쓰입니다.

짧은 예제

#include <iostream>
#include <set>
#include <unordered_set>

int main() {
    std::set<int> ordered{3, 1, 2};
    std::unordered_set<int> fast{3, 1, 2};

    std::cout << ordered.count(2) << "\n";
    std::cout << fast.count(2) << "\n";
}

빠른 정리

주의할 점