[C++] Set/Map

📚 C++ Set/Map

🔸 set (집합)

기본 특징

• Red-Black Tree (레드-블랙 트리)로 구현
• 중복 불가 - 각 요소는 유일해야 함
• 자동 정렬 - 삽입 시 자동으로 정렬된 상태 유지
• Balanced BST 특성상 모든 연산이 O(log n) 보장

시간 복잡도

연산	시간 복잡도
Insertion (insert)	O(log n)
Deletion (erase)	O(log n)
Search (find)	O(log n)
Access (최소/최대)	O(log n)

메모리 구조 (Red-Black Tree)

레드-블랙 트리 속성:
1. 모든 노드는 Red 또는 Black
2. 루트는 항상 Black
3. 모든 리프(NULL)는 Black
4. Red 노드의 자식은 모두 Black
5. 모든 경로의 Black 노드 개수는 동일

예시: {10, 20, 30, 40, 50}
         30(B)
        /     \
     20(B)    40(B)
      /         \
   10(R)       50(R)

Stack:
┌──────────────────┐
│ root (pointer)  │ → 루트 노드
│ size            │ → 요소 개수
└──────────────────┘

Heap (각 노드):
┌────────────────────┐
│ color (R/B)       │
│ data              │
│ left (pointer)    │
│ right (pointer)   │
│ parent (pointer)  │
└────────────────────┘

사용 예시

#include <set>
#include <iostream>

std::set<int> s;

// ✅ 삽입 - O(log n)
s.insert(30);
s.insert(10);
s.insert(20);
s.insert(10);  // 중복 - 삽입 안 됨!

// ✅ 자동 정렬됨
for (int val : s) {
    std::cout << val << " ";  // 10 20 30
}

// ✅ 검색 - O(log n)
auto it = s.find(20);
if (it != s.end()) {
    std::cout << "Found: " << *it;
}

// ✅ 삭제 - O(log n)
s.erase(20);

// ✅ 범위 기반 검색
auto lower = s.lower_bound(15);  // >= 15인 첫 요소
auto upper = s.upper_bound(25);  // > 25인 첫 요소

커스텀 비교 함수

// 내림차순 정렬
std::set<int, std::greater<int>> descSet;

// 커스텀 비교자
struct Person {
    std::string name;
    int age;
};

struct CompareByAge {
    bool operator()(const Person& a, const Person& b) const {
        return a.age < b.age;
    }
};

std::set<Person, CompareByAge> people;

---

🔸 multiset (중복 허용 집합)

기본 특징

• set과 동일하게 Red-Black Tree로 구현
• 중복 허용 - 동일한 값을 여러 번 삽입 가능
• 자동 정렬 유지
• 시간 복잡도는 set과 동일

set vs multiset

std::set<int> s;
s.insert(10);
s.insert(10);
s.insert(10);
std::cout << s.size();  // 1 (중복 무시)

std::multiset<int> ms;
ms.insert(10);
ms.insert(10);
ms.insert(10);
std::cout << ms.size();  // 3 (중복 허용)

중복 요소 처리

std::multiset<int> ms = {10, 20, 20, 30, 30, 30};

// ✅ 특정 값의 개수 세기 - O(log n + k), k는 중복 개수
int count = ms.count(30);  // 3

// ✅ 특정 값의 범위 찾기
auto range = ms.equal_range(30);
for (auto it = range.first; it != range.second; ++it) {
    std::cout << *it << " ";  // 30 30 30
}

// ✅ 특정 값 하나만 삭제
auto it = ms.find(30);
if (it != ms.end()) {
    ms.erase(it);  // 30 하나만 삭제
}

// ✅ 특정 값 모두 삭제
ms.erase(30);  // 30 모두 삭제

---

🔸 map (키-값 쌍)

기본 특징

• Red-Black Tree로 구현
• 키(Key)는 중복 불가, 값(Value)은 중복 가능
• 키 기준으로 자동 정렬
• set과 동일한 시간 복잡도

시간 복잡도

연산	시간 복잡도
Insertion (insert, operator[])	O(log n)
Deletion (erase)	O(log n)
Search (find, operator[])	O(log n)

메모리 구조

Heap (각 노드):
┌────────────────────┐
│ color (R/B)       │
│ pair<Key, Value>  │ ← key와 value를 함께 저장
│ left (pointer)    │
│ right (pointer)   │
│ parent (pointer)  │
└────────────────────┘

사용 예시

#include <map>
#include <string>

std::map<std::string, int> ages;

// ✅ 삽입 방법 1: operator[] - O(log n)
ages["Alice"] = 25;
ages["Bob"] = 30;

// ✅ 삽입 방법 2: insert - O(log n)
ages.insert({"Charlie", 35});
ages.insert(std::make_pair("David", 40));

// ✅ 검색 - O(log n)
auto it = ages.find("Alice");
if (it != ages.end()) {
    std::cout << it->first << ": " << it->second;  // Alice: 25
}

// ⚠️ operator[]의 주의점
int age = ages["Eve"];  // 키가 없으면 자동 생성! (value는 0으로 초기화)
std::cout << ages.size();  // 5 (Eve가 추가됨)

// ✅ 안전한 검색: at() 사용
try {
    int age = ages.at("Frank");  // 키가 없으면 예외 발생
} catch (const std::out_of_range& e) {
    std::cout << "Key not found!";
}

iterator 활용

std::map<std::string, int> scores = {
    {"Alice", 90},
    {"Bob", 85},
    {"Charlie", 95}
};

// ✅ 순회 (키 기준 정렬된 순서)
for (const auto& [name, score] : scores) {
    std::cout << name << ": " << score << "\n";
}
// Alice: 90
// Bob: 85
// Charlie: 95

---

🔸 multimap (중복 키 허용)

기본 특징

• map과 동일하게 Red-Black Tree로 구현
• 키 중복 허용
• operator[] 사용 불가 (어떤 값을 반환할지 모호)

사용 예시

std::multimap<std::string, int> scores;

scores.insert({"Alice", 90});
scores.insert({"Alice", 85});  // 같은 키에 다른 값
scores.insert({"Bob", 95});

// ✅ 특정 키의 모든 값 찾기
auto range = scores.equal_range("Alice");
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->second << " ";  // 85 90 (정렬됨)
}

---

🔸 unordered_set (해시 집합)

기본 특징

• Hash Table로 구현
• 중복 불가
• 정렬되지 않음 (순서 보장 안 됨)
• 평균 O(1), 최악 O(n) 시간 복잡도

시간 복잡도

연산	평균	최악
Insertion	O(1)	O(n)
Deletion	O(1)	O(n)
Search	O(1)	O(n)

메모리 구조 (Hash Table with Separate Chaining)

Hash Table 구조:

해시 함수: hash(value) % bucket_count

Bucket Array (vector):
┌─────┬─────┬─────┬─────┬─────┐
│  0 │  1  │  2  │  3  │  4  │
└──┬──┴──┬──┴──┬──┴──┬──┴──┬──┘
   │     │     │     │     │
   ↓     ↓     ↓     ↓     ↓
  [10]  [21]  NULL [13]  [24]
   ↓     ↓           ↓     ↓
  [30]  NULL        [33]  NULL

각 버킷은 Linked List로 구현 (Separate Chaining)
해시 충돌 발생 시 같은 버킷에 연결

Stack:
┌──────────────────┐
│ buckets (array) │ → 버킷 배열
│ size            │ → 요소 개수
│ bucket_count    │ → 버킷 개수
│ max_load_factor │ → 최대 로드 팩터 (기본 1.0)
└──────────────────┘

해시 함수와 충돌 처리

// 해시 값 계산 예시
hash<int> hashFunc;
size_t hashValue = hashFunc(42);

// 버킷 인덱스 = hash(value) % bucket_count
size_t bucketIndex = hashValue % bucket_count;

// ✅ Separate Chaining
// 같은 버킷에 여러 요소가 linked list로 연결됨

Load Factor와 Rehashing

std::unordered_set<int> us;

// Load Factor = size / bucket_count
// 기본 max_load_factor = 1.0

us.insert(10);
us.insert(20);
us.insert(30);

std::cout << "Size: " << us.size() << "\n";
std::cout << "Bucket count: " << us.bucket_count() << "\n";
std::cout << "Load factor: " << us.load_factor() << "\n";
std::cout << "Max load factor: " << us.max_load_factor() << "\n";

// ⚠️ load_factor > max_load_factor 되면 Rehashing 발생!
// Rehashing: O(n) - 모든 요소를 새 버킷에 재배치

Rehashing 최적화

std::unordered_set<int> us;

// ✅ 미리 버킷 예약 - rehashing 방지
us.reserve(1000);  // 최소 1000개 요소를 담을 수 있도록 버킷 확보

// ✅ max_load_factor 조정
us.max_load_factor(0.5);  // 로드 팩터를 낮춰서 충돌 감소 (메모리 trade-off)

사용 예시

#include <unordered_set>

std::unordered_set<int> us;

// ✅ 삽입 - 평균 O(1)
us.insert(10);
us.insert(20);
us.insert(30);

// ✅ 검색 - 평균 O(1)
if (us.find(20) != us.end()) {
    std::cout << "Found!";
}

// ⚠️ 순서 보장 안 됨!
for (int val : us) {
    std::cout << val << " ";  // 순서 예측 불가
}

커스텀 타입을 위한 Hash Function 정의

방법 1: Hash Function Object 생성

struct Person {
    std::string name;
    int age;
    
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// 커스텀 해시 함수 객체
struct PersonHash {
    size_t operator()(const Person& p) const {
        // 여러 필드를 조합한 해시 값 계산
        size_t h1 = std::hash<std::string>{}(p.name);
        size_t h2 = std::hash<int>{}(p.age);
        return h1 ^ (h2 << 1);  // XOR과 shift 조합
    }
};

// 사용
std::unordered_set<Person, PersonHash> people;
people.insert({"Alice", 25});

방법 2: std 네임스페이스에 특수화 주입

struct Person {
    std::string name;
    int age;
    
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// std::hash 특수화
namespace std {
    template<>
    struct hash<Person> {
        size_t operator()(const Person& p) const {
            size_t h1 = hash<string>{}(p.name);
            size_t h2 = hash<int>{}(p.age);
            return h1 ^ (h2 << 1);
        }
    };
}

// 사용 (추가 템플릿 인자 불필요)
std::unordered_set<Person> people;
people.insert({"Alice", 25});

커스텀 Equality Operator

// 방법 1: 클래스 내부에 operator== 정의 (위 예시 참고)

// 방법 2: 별도의 함수 객체
struct PersonEqual {
    bool operator()(const Person& a, const Person& b) const {
        return a.name == b.name && a.age == b.age;
    }
};

std::unordered_set<Person, PersonHash, PersonEqual> people;

---

🔸 unordered_map (해시 맵)

기본 특징

• Hash Table로 구현
• 키 중복 불가
• unordered_set과 동일한 시간 복잡도
• 실무에서 가장 많이 사용됨
• 알고리즘 면접에서 자주 출제됨

시간 복잡도

연산	평균	최악
Insertion (insert, operator[])	O(1)	O(n)
Deletion (erase)	O(1)	O(n)
Search (find, operator[])	O(1)	O(n)

메모리 구조

Bucket Array:
┌──────┬──────┬──────┬──────┐
│  0   │  1  │  2   │  3  │
└───┬──┴──┬───┴──┬───┴──┬───┘
   │     │      │      │
   ↓     ↓      ↓      ↓
 {k1:v1} NULL {k2:v2} NULL
   ↓                   ↓
 {k3:v3}             {k4:v4}

각 노드는 pair<Key, Value> 저장

사용 예시

#include <unordered_map>
#include <string>

std::unordered_map<std::string, int> phoneBook;

// ✅ 삽입 - 평균 O(1)
phoneBook["Alice"] = 1234;
phoneBook["Bob"] = 5678;
phoneBook.insert({"Charlie", 9012});

// ✅ 검색 - 평균 O(1)
auto it = phoneBook.find("Alice");
if (it != phoneBook.end()) {
    std::cout << it->first << ": " << it->second;
}

// ✅ operator[] - 평균 O(1)
int number = phoneBook["Alice"];  // 1234

// ⚠️ 키가 없으면 자동 생성
int unknown = phoneBook["David"];  // David 키 생성, value = 0

// ✅ 성능 최적화
phoneBook.reserve(10000);  // 예상 크기 미리 예약

실무 활용 예시

// 빈도수 카운팅
std::unordered_map<char, int> freq;
std::string text = "hello world";
for (char c : text) {
    freq[c]++;
}

// 캐싱 (Memoization)
std::unordered_map<int, int> cache;
int fibonacci(int n) {
    if (n <= 1) return n;
    if (cache.find(n) != cache.end()) {
        return cache[n];
    }
    cache[n] = fibonacci(n-1) + fibonacci(n-2);
    return cache[n];
}

// 그래프 인접 리스트
std::unordered_map<int, std::vector<int>> graph;
graph[1] = {2, 3};
graph[2] = {4};

커스텀 타입 예시

struct Point {
    int x, y;
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

struct PointHash {
    size_t operator()(const Point& p) const {
        return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) << 1);
    }
};

std::unordered_map<Point, std::string, PointHash> locations;
locations[{0, 0}] = "Origin";
locations[{10, 20}] = "Point A";

---

🔸 unordered_multiset / unordered_multimap

기본 특징

• 각각 unordered_set, unordered_map의 중복 허용 버전
• 시간 복잡도 동일
• unordered_multimap은 operator[] 사용 불가

사용 예시

std::unordered_multiset<int> ums = {10, 20, 20, 30, 30, 30};

// 특정 값의 개수
int count = ums.count(30);  // 3

// 특정 값 모두 찾기
auto range = ums.equal_range(30);
for (auto it = range.first; it != range.second; ++it) {
    std::cout << *it << " ";
}

---

🔸 set vs unordered_set 비교

성능 비교

특성	set	unordered_set
구현	Red-Black Tree	Hash Table
정렬	✅ 자동 정렬	❌ 정렬 안 됨
평균 검색	O(log n)	O(1) ✅
최악 검색	O(log n) ✅	O(n)
메모리	적음	많음 (버킷 배열)
순서 보장	✅	❌
iterator 안정성	높음	낮음 (rehashing 시 무효화)

선택 가이드

// ✅ set을 사용해야 하는 경우:
// 1. 정렬된 순서가 필요할 때
std::set<int> sorted = {30, 10, 20};
for (int val : sorted) {
    std::cout << val << " ";  // 10 20 30 (정렬됨)
}

// 2. 범위 검색이 필요할 때
auto lower = sorted.lower_bound(15);
auto upper = sorted.upper_bound(25);

// 3. 최악의 경우에도 일정한 성능이 필요할 때 (O(log n) 보장)

// ✅ unordered_set을 사용해야 하는 경우:
// 1. 빠른 검색이 최우선일 때 (평균 O(1))
std::unordered_set<int> fast;

// 2. 순서가 중요하지 않을 때

// 3. 데이터 크기를 미리 알고 reserve 가능할 때
fast.reserve(10000);

map vs unordered_map 비교

특성	map	unordered_map
구현	Red-Black Tree	Hash Table
키 정렬	✅	❌
평균 검색	O(log n)	O(1) ✅
최악 검색	O(log n) ✅	O(n)
실무 사용 빈도	중간	✅ 매우 높음

---

🔸 Hash Function 설계 원칙

좋은 해시 함수의 조건
1. 결정론적 (Deterministic): 같은 입력은 항상 같은 해시 값
2. 균등 분포 (Uniform Distribution): 해시 값이 고르게 분포
3. 효율성 (Efficient): 계산이 빠름 (O(1))
4. 충돌 최소화: 서로 다른 입력에 대해 다른 해시 값

해시 조합 기법

// ❌ 나쁜 예: 단순 더하기 (충돌 많음)
size_t badHash = hash<int>{}(x) + hash<int>{}(y);

// ✅ 좋은 예 1: XOR + Shift
size_t goodHash1 = hash<int>{}(x) ^ (hash<int>{}(y) << 1);

// ✅ 좋은 예 2: Boost 스타일
size_t goodHash2 = hash<int>{}(x);
goodHash2 ^= hash<int>{}(y) + 0x9e3779b9 + (goodHash2 << 6) + (goodHash2 >> 2);

// ✅ 좋은 예 3: 여러 필드 조합
struct Data {
    int a, b, c;
};

size_t hash_value(const Data& d) {
    size_t seed = 0;
    seed ^= hash<int>{}(d.a) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    seed ^= hash<int>{}(d.b) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    seed ^= hash<int>{}(d.c) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    return seed;
}

---

🔸 핵심 정리

컨테이너 선택 가이드

순서가 필요한가?
├─ YES → set / map
│         - 정렬된 순서 보장
│         - 범위 검색 가능
│         - O(log n) 성능 보장
│
└─ NO → unordered_set / unordered_map
          - 평균 O(1) 성능
          - 메모리 사용량 높음
          - rehashing 주의

중복이 필요한가?
├─ YES → multiset / multimap / unordered_multiset / unordered_multimap
└─ NO → set / map / unordered_set / unordered_map

키-값 쌍이 필요한가?
├─ YES → map / unordered_map
└─ NO → set / unordered_set

성능 최적화 팁

1. unordered_* 사용 시:

   • 예상 크기를 아는 경우 reserve() 사용
   • max_load_factor 조정으로 충돌 제어
   • 좋은 해시 함수 설계

2. set/map 사용 시:

   • 커스텀 비교 함수로 정렬 순서 제어
   • lower_bound, upper_bound 활용

3. 일반적인 권장사항:

   • 대부분의 경우: unordered_map (실무 표준)
   • 정렬이 필요한 경우: map
   • 중복이 필요한 경우: multiset / multimap

실무에서 자주 쓰이는 패턴

// 1. 빈도수 카운팅
unordered_map<string, int> wordCount;

// 2. 중복 제거
unordered_set<int> uniqueValues;

// 3. 캐싱/메모이제이션
unordered_map<int, Result> cache;

// 4. 그래프 표현
unordered_map<Node, vector<Node>> adjacencyList;

// 5. 빠른 조회 테이블
unordered_map<string, UserData> userDatabase;

---

<참고 자료>

코드없는 프로그래밍
std::set
std::map
std::unordered_set
std::unordered_map
Red-Black Tree
Hash Table