C++ 초급 - 11. 표준 라이브러리(STL) (3 - std::set, std::unordered_set (중복 없는 집합 컨테이너))

📌 11.3 std::set, std::unordered_set (중복 없는 집합 컨테이너)

C++에서는 중복 없는 요소를 저장하고 관리할 수 있는 컨테이너로 std::set (정렬된 집합)과 std::unordered_set (해시 기반 집합)을 제공한다.
각각 이진 검색 트리와 해시 테이블을 기반으로 동작하며, 사용 목적과 성능 차이가 존재한다.

---

📌 1. std::set (정렬된 중복 없는 요소 저장)

🔹 (1) std::set이란?

• 중복을 허용하지 않는 정렬된 집합 컨테이너.
• 이진 검색 트리(Red-Black Tree)를 기반으로 동작.
• 시간 복잡도: 삽입, 삭제, 탐색 연산이 O(log N).
• 자동 정렬된 상태로 요소를 유지.

💡 기본 문법

#include <set>

std::set<int> mySet;  // 정수형 집합 선언

💡 예제: std::set 기본 사용법

#include <iostream>
#include <set>

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

    mySet.insert(3);
    mySet.insert(1);
    mySet.insert(2);
    mySet.insert(3);  // 중복된 값은 삽입되지 않음

    std::cout << "집합 요소 출력: ";
    for (int x : mySet) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

🔹 출력 결과

집합 요소 출력: 1 2 3

💡 설명

• 중복된 값(3)은 자동으로 제거됨.
• 값이 자동 정렬되어 1 2 3 순서로 저장됨.

---

📌 2. std::unordered_set (해시 기반 빠른 검색)

🔹 (1) std::unordered_set이란?

• 중복을 허용하지 않는 해시 기반 집합 컨테이너.
• **해시 테이블(Hash Table)**을 기반으로 동작.
• 시간 복잡도: 평균 O(1), 최악 O(N).
• 삽입 순서는 보장되지 않음 (정렬되지 않음).

💡 기본 문법

#include <unordered_set>

std::unordered_set<int> myUnorderedSet;

💡 예제: std::unordered_set 기본 사용법

#include <iostream>
#include <unordered_set>

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

    myUnorderedSet.insert(3);
    myUnorderedSet.insert(1);
    myUnorderedSet.insert(2);
    myUnorderedSet.insert(3);  // 중복된 값은 삽입되지 않음

    std::cout << "집합 요소 출력: ";
    for (int x : myUnorderedSet) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

🔹 출력 결과 (실행할 때마다 순서가 다를 수 있음)

집합 요소 출력: 3 1 2

💡 설명

• 중복된 값(3)은 삽입되지 않음.
• 해시 테이블 기반이므로 저장 순서가 일정하지 않음.

---

📌 3. 삽입, 삭제, 탐색 (insert, erase, find)

🔹 (1) insert를 활용한 요소 추가

💡 예제: insert()를 사용한 요소 추가

std::set<int> mySet;
mySet.insert(10);
mySet.insert(20);

---

🔹 (2) erase를 활용한 요소 삭제

💡 예제: erase()를 사용한 요소 삭제

mySet.erase(10);  // 값 10 제거

---

🔹 (3) find를 활용한 요소 탐색

💡 예제: find()를 사용한 요소 검색

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

---

📌 4. std::set vs std::unordered_set 성능 비교

특징	std::set	std::unordered_set
구조	이진 검색 트리(Red-Black Tree)	해시 테이블(Hash Table)
정렬	자동 정렬 O	정렬되지 않음 X
삽입, 삭제, 검색	O(log N)	평균 O(1), 최악 O(N)
메모리 사용량	상대적으로 적음	상대적으로 많음
적합한 경우	정렬된 데이터가 필요한 경우	빠른 검색이 필요한 경우

💡 선택 기준

• 데이터가 정렬된 상태로 유지되어야 한다면 std::set 사용.
• 빠른 검색이 필요하면 std::unordered_set 사용.

---

📌 5. 커스텀 정렬 및 해시 함수 적용 방법

🔹 (1) std::set에서 사용자 정의 비교 함수 사용

💡 예제: 내림차순 정렬

#include <iostream>
#include <set>

struct DescendingOrder {
    bool operator()(int a, int b) const {
        return a > b;  // 내림차순 정렬
    }
};

int main() {
    std::set<int, DescendingOrder> mySet;
    
    mySet.insert(1);
    mySet.insert(3);
    mySet.insert(2);

    for (int x : mySet) {
        std::cout << x << " ";
    }

    return 0;
}

🔹 출력 결과

3 2 1

💡 설명

• std::set<int, DescendingOrder>를 사용하여 내림차순 정렬 적용.

---

🔹 (2) std::unordered_set에서 사용자 정의 해시 함수 사용

💡 예제: 사용자 정의 해시 함수

#include <iostream>
#include <unordered_set>

struct CustomHash {
    size_t operator()(int x) const {
        return x % 10;  // 단순한 해시 함수
    }
};

int main() {
    std::unordered_set<int, CustomHash> myUnorderedSet;
    
    myUnorderedSet.insert(1);
    myUnorderedSet.insert(12);  // 같은 해시값을 가질 수 있음

    for (const auto& value : myUnorderedSet) {
        std::cout << value << " ";
    }

    return 0;
}

---

📌 6. 정리

개념	설명
std::set	키가 정렬된 상태로 저장되는 집합 컨테이너
std::unordered_set	해시 기반으로 저장되어 빠른 검색 가능
삽입, 삭제, 탐색	insert, erase, find 활용
성능 차이	std::set → O(log N), std::unordered_set → 평균 O(1)
커스텀 정렬 및 해시	std::set은 사용자 정의 비교 함수 가능, std::unordered_set은 사용자 정의 해시 가능