unordered_set

김민수·2025년 1월 20일

C++

목록 보기

59/68

unordered_set은 해시 기반 데이터 구조를 사용해서 데이터를 저장하고 검색하는 컨테이너다. 데이터의 중복을 방지하면서 빠르게 삽입, 삭제, 검색할 수 있는 기능을 제공한다.

1. 특징

1) 내부 동작 방식

unordered_set은 해시 테이블을 사용해서 데이터를 저장한다.
각 요소는 해시 함수에 의해 특정 버킷(bucket)에 매핑된다.
충돌이 발생하면 해당 버킷에 연결 리스트로 요소를 추가한다.

2) 시간 복잡도

삽입, 삭제, 검색: 평균 O(1) (최악의 경우 O(n) - 해시 충돌 발생 시)
정렬된 데이터나 순서가 중요한 작업에서는 적합하지 않다.

2. 주요 함수

insert(const T& value): 요소를 삽입한다. 이미 존재하는 값은 삽입되지 않는다.
find(const T& key): 특정 키를 찾고, 존재하면 해당 요소의 이터레이터를 반환한다.
erase(const T& key): 특정 키를 삭제한다.
size(): 현재 저장된 요소의 개수를 반환한다.
clear(): 모든 요소를 제거한다.
empty(): 컨테이너가 비어 있는지 여부를 반환한다.

3. 예제

기본 사용법

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet;

    // 삽입
    mySet.insert(10);
    mySet.insert(20);
    mySet.insert(30);

    // 검색
    if (mySet.find(20) != mySet.end()) {
        std::cout << "20이 존재합니다." << std::endl;
    }

    // 삭제
    mySet.erase(10);

    // 전체 출력
    for (const auto& elem : mySet) {
        std::cout << elem << " ";
    }
    return 0;
}

중복 제거

#include <iostream>
#include <unordered_set>
#include <vector>

int main() {
    std::vector<int> data = {1, 2, 2, 3, 4, 4, 5};
    std::unordered_set<int> uniqueData;

    for (int num : data) {
        uniqueData.insert(num);
    }

    std::cout << "중복 제거 후: ";
    for (const auto& elem : uniqueData) {
        std::cout << elem << " ";
    }
    return 0;
}