[C++] map과 unordered_map의 이해

 

1️⃣ map vs unordered_map 

구분	map	unordered_map
내부 구조	Red-Black Tree (균형 이진 트리)	Hash Table
탐색	항상 O(log N)	평균 O(1), 최악 O(N)
정렬	항상 Key 기준 정렬됨	순서 없음
안전성	매우 안정적	해시 충돌 시 폭망
코테 사용성	⭐⭐⭐⭐⭐	⭐⭐⭐

---

왜 unordered_map이 코테에서 위험한가?

unordered_map은 해시를 사용한다.

key → hash(key) → 배열 index

하지만 만약 서로 다른 key들이 같은 hash 값으로 몰리면?

→ 그 버킷에 선형 탐색 발생

→ 성능이 O(N) 으로 붕괴

코딩테스트 출제자는 이런 입력을 일부러 만들 수 있다.

그래서 실제 코테 고수들은:

“unordered_map이 빠르긴 한데, map이 더 안전하다”

라고 판단한다.

---

2️⃣ map에서 가장 많이 터지는 실수: m[key]

map<string, int> m;

if (m["banana"] == 0) { ... }   // ❌ 매우 위험

이 코드는 “banana가 있는지” 확인하는 것처럼 보이지만…

실제로는:

"banana"가 없으면
("banana", 0)을 map에 삽입한다

즉,

조회한 것 같지만 실제로는 데이터가 추가됨

이 때문에:

• map 크기 증가
• 메모리 증가
• 로직 붕괴

---

올바른 존재 여부 확인

if (m.find("banana") != m.end()) { ... }
// 또는
if (m.count("banana")) { ... }

find, count는 절대 삽입하지 않는다.

---

3️⃣ map의 핵심 함수 (코테 기준)

함수 의미

m[k] = v	삽입 또는 갱신
m.insert({k,v})	없을 때만 삽입
m.find(k)	존재 확인
m.count(k)	0 또는 1
m.erase(k)	삭제
m.clear()	전체 삭제

map은 내부가 트리이기 때문에

모든 연산이 항상 O(log N)

→ 시간 폭발 없음

→ 해시 저격 불가능

---

4️⃣ map을 순회하면 자동 정렬된다

for (const auto& [k, v] : m) {
    cout << k << " " << v << "\\n";
}

map은 이진 탐색 트리이므로

중위 순회 = 오름차순 정렬

그래서:

“작은 순서대로 출력하라”

“사전순으로 출력하라”

→ 그냥 map 순회하면 끝

---

5️⃣ map의 가장 강력한 용도: 빈도수 세기

vector<string> items = {"apple","banana","apple","cherry"};
map<string,int> counter;

for (auto& s : items)
    counter[s]++;

이 한 줄의 의미:

없으면 0 생성 → 1 증가
있으면 기존 값 증가

그래서:

• 문자열
• 좌표
• 큰 정수

전부 카운팅 가능

→ 배열보다 훨씬 강력

---

6️⃣ map 안에 또 자료구조를 넣을 수 있다

map<string, vector<int>> genreSongs;
map<int, set<int>> graph;

의미:

key별로 그룹 관리

이 패턴은:

• 카테고리 분류
• 그래프 인접 리스트
• 그룹핑 문제

에서 매우 자주 등장

---

7️⃣ 정렬 방향도 바꿀 수 있다

map<int, string, greater<int>> m;

→ key가 큰 것부터 정렬

즉, map을

정렬된 우선순위 큐처럼 사용 가능

---

8️⃣ map의 lower_bound

auto it = m.lower_bound(k);

의미:

key ≥ k 중 가장 작은 것

이게 왜 중요하냐면:

map은 정렬된 배열 + 이진탐색 역할을 동시에 한다.

그래서:

• 좌표 압축
• 순위 매기기
• 구간 쿼리
• 범위 문제

이 전부 map으로 해결 가능

---

언제 무엇을 써야 할까?

상황	선택
key가 1~100000	배열
key가 문자열 / 좌표	map
정렬된 상태 필요	map
단순 빠른 조회	unordered_map
해시 저격 걱정	map

---

9️⃣ operator[] vs at() — const map에서 터지는 함정

코테에서 자주 이런 형태의 함수가 등장한다.

void solve(const map<int,int>& m) {
    ...
}

이때 많은 사람들이 무심코 이렇게 쓴다.

m[key];   // ❌ 컴파일 에러

이유는 단순하다.

operator[]는 “없으면 새 원소를 삽입하는 연산”이기 때문

즉, 읽기 전용(const) map에서는

수정 가능성이 있는 []를 사용할 수 없다.

이때는 반드시:

m.at(key);        // 값 반환, 없으면 exception
m.find(key);     // 가장 안전

을 써야 한다.

이걸 모르면 “왜 const map에서 []가 안 되지?” 하며 시간을 낭비하게 된다.

---

🔟 map 순회 중 erase — iterator 지뢰밭

map을 순회하면서 원소를 삭제해야 하는 문제가 자주 나온다.

이때 절대 하면 안 되는 코드:

for (auto it = m.begin(); it != m.end(); it++) {
    if (조건) m.erase(it);   // ❌ iterator 깨짐
}

올바른 패턴은 이것이다.

for (auto it = m.begin(); it != m.end(); ) {
    if (조건)
        it = m.erase(it);   // 다음 iterator 반환
    else
        ++it;
}

---

1️⃣1️⃣ unordered_map.reserve() - TLE 방지

unordered_map<int,int> m;
m.reserve(100000);

이건 단순한 최적화가 아니다.

해시 테이블은 크기가 커질 때:

모든 원소를 다시 해싱하고 재배치한다 (rehash)

이게 발생하면:

• 순간적으로 O(N)
• 대량 입력 → TLE

그래서:

입력 크기가 크면 reserve는 사실상 필수다.

---

1️⃣2️⃣map은 메모리를 많이 먹는다

map의 한 노드는:

key, value,
left pointer, right pointer, parent pointer, color

즉:

배열보다 5~8배 많은 메모리를 사용

그래서:

상황 선택

key가 1~100000 정수	배열
key가 희소 / 문자열	map

이 기준을 모르고 map을 쓰면

메모리 초과(MLE) 가 난다.