[C++] map과 unordered_map 정리

오늘은 STL의 연관 컨테이너인 map과 unordered_map에 대해 정리해보려고 한다.

둘 다 key와 value를 쌍으로 저장하는 컨테이너지만,
내부적으로 데이터를 관리하는 방식이 다르기 때문에 성능 특성과 사용 기준도 다르다.

• map : 보통 레드-블랙 트리 기반, key 기준 정렬 유지
• unordered_map : 해시 테이블 기반, key 순서 보장 X

map의 특징과 일부 주요 함수, unordered_map의 해시 구조,
그리고 map의 기반이 되는 레드-블랙 트리까지 간단히 정리해보려고 한다.

---

map이란?

map은 STL의 연관 컨테이너 중 하나로 key와 value를 쌍으로 저장하는 컨테이너이다.
하나의 key에 하나의 value가 대응되며 같은 key를 중복해서 저장할 수 없다.

map은 보통 내부적으로 레드-블랙 트리와 같은 균형 이진 탐색 트리로 구현된다.
따라서 삽입, 삭제, 탐색의 시간 복잡도는 O(log N) 이다.

또한 map은 기본적으로 key를 기준으로 오름차순 정렬된 상태를 유지한다.

---

map 원소 조회와 추가

operator[]

map에서 operator[]는 key를 이용해 value에 접근할 때 사용한다.
이때 중요한 점은 key가 없으면 새 원소를 생성한다는 것이다.

예를 들어 아래 코드는 key 10이 없더라도 새 원소를 생성한다.

std::map<int, int> m;

std::cout << m[10] << '\n';

int의 기본값은 0이므로 m[10]은 새 원소를 만들고 value를 0으로 초기화한다.
따라서 단순히 존재 여부만 확인하고 싶다면 operator[]보다는
find()나 contains()를 사용하는 것이 좋다.

if (m.find(10) != m.end()) {
    // key가 존재함
}

C++20부터는 contains()도 사용할 수 있다.

if (m.contains(10)) {
    // key가 존재함
}

insert

insert는 이미 생성된 원소를 map에 삽입하려고 할 때 사용한다.

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

m.insert({1, "one"});
m.insert({1, "ONE"});

map은 key 중복을 허용하지 않기 때문에 이미 같은 key가 존재하면 삽입에 실패한다.

즉, 위 코드에서 두 번째 insert는 실패하고 기존 값 "one"이 유지된다.

insert는 삽입 성공 여부를 확인할 수 있는 값 std::pair<iterator, bool>을 반환한다.

auto result = m.insert({1, "one"});

if (result.second) {
    std::cout << "insert success\n";
}
else {
    std::cout << "insert failed\n";
}

emplace

emplace는 전달받은 인자를 이용해 컨테이너 내부에서 원소를 직접 생성하려고 시도한다.

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

m.emplace(1, "one");

insert는 이미 만들어진 객체를 넣는 느낌이라면,
emplace는 내부에서 직접 생성하는 방식이다.

따라서 불필요한 임시 객체 생성을 줄이기 위한 용도로 사용할 수 있다.
하지만 emplace는 key가 이미 존재하더라도, 전달한 인자나 value 생성 비용이 발생할 수 있다.

즉, key가 이미 있을 때 value 생성 비용까지 피하고 싶다면 try_emplace가 더 적합할 수 있다.

try_emplace

try_emplace는 key가 없을 때만 value 생성을 시도한다.

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

m.try_emplace(1, "one");
m.try_emplace(1, "ONE");

위 코드에서 두 번째 try_emplace는 key 1이 이미 존재하므로
새 value를 만들지 않는다.

try_emplace는 다음과 같은 상황에서 유용하다.

• key가 없을 때만 삽입하고 싶을 때
• key가 이미 있으면 value 생성 비용을 피하고 싶을 때
• value 생성 비용이 큰 객체를 다룰 때

---

unordered_map이란?

unordered_map도 map처럼 key, value 쌍으로 데이터를 저장하는 연관 컨테이너이다.
하지만 map과 달리 정렬을 유지하지 않는다.

unordered_map은 내부적으로 보통 해시 테이블을 사용한다.
key를 해시 함수에 넣어 해시 값을 구하고 그 해시 값을 이용해 데이터를 저장할 위치인 bucket을 결정한다.

특징은 다음과 같다.

• key, value 쌍으로 데이터를 저장한다.
• key 중복을 허용하지 않는다.
• key 순서를 보장하지 않는다.
• 내부적으로 해시 테이블을 사용한다.
• 평균적으로 삽입, 삭제, 탐색이 O(1)이다.
• 최악의 경우 O(N)이 될 수 있다.

---

unordered_map의 해시 구조

unordered_map은 내부적으로 여러 개의 bucket을 가진다.

key가 들어오면 다음 과정을 거친다.

1. key를 해시 함수에 넣어 해시 값을 만든다.
2. 해시 값을 bucket 개수에 맞게 변환한다.
3. 해당 bucket에 원소를 저장한다.

개념적으로는 다음과 같다.

bucket_index = hash(key) % bucket_count

key 자체를 순서대로 정렬해서 저장하는 것이 아니라 해시 결과를 이용해 어느 bucket에 넣을지 결정한다.
이 방식 덕분에 평균적으로 매우 빠른 탐색이 가능하다.

---

해시 충돌

서로 다른 key라도 같은 bucket 위치가 나올 수 있고 이를 해시 충돌이라고 한다.

해시 충돌을 처리하는 대표적인 방식으로는 체이닝과 개방 주소법이 있다.
std::unordered_map은 보통 버킷에 원소를 연결해 관리하는 체이닝 방식으로 설명된다.

체이닝은 버킷 내부에 연결 리스트나 그에 준하는 구조로 원소들을 연결해 저장하는 방식이고,
개방 주소법은 충돌이 발생했을 때 다른 빈 슬롯을 찾아 저장하는 방식이다.

해시 충돌이 많아지면 탐색 성능이 나빠질 수 있다.
평균적으로는 O(1)이지만 충돌이 심하면 최악의 경우 O(N)까지 갈 수 있다.

---

rehash란?

unordered_map에 원소가 많아지면 bucket이 부족해질 수 있다.
이때 컨테이너는 bucket 개수를 늘리고 기존 원소들을 새로운 bucket 위치에 다시 배치한다.
이 과정을 rehash라고 한다.

rehash가 발생하면 다음 과정이 일어난다.

1. 더 많은 bucket을 가진 새 구조를 준비한다.
2. 기존 원소들의 hash 값을 다시 계산하거나 bucket 위치를 다시 정한다.
3. 원소들을 새 bucket 구조에 재배치한다.

즉, vector가 capacity를 초과하면 더 큰 메모리로 재할당하듯이,
unordered_map도 원소가 많아지면 bucket 수를 늘리고 원소를 다시 배치하는 rehash가 발생할 수 있다.

---

언제 map을 사용할까?

다음과 같은 경우에는 map이 적합하다.

• key 기준으로 정렬된 순회가 필요할 때
• 범위 탐색이 필요할 때
• lower_bound, upper_bound 같은 정렬 기반 연산이 필요할 때
• 최악의 경우에도 O(log N) 성능을 기대하고 싶을 때

예를 들어 key를 오름차순으로 출력해야 한다면 map이 자연스럽다.

---

언제 unordered_map을 사용할까?

다음과 같은 경우에는 unordered_map이 적합하다.

• key 순서가 중요하지 않을 때
• 빠른 탐색이 중요할 때
• 평균 O(1) 성능을 기대하고 싶을 때
• 해시 가능한 key를 사용할 때

예를 들어 단순히 key로 값을 빠르게 찾는 용도라면 unordered_map이 더 적합할 수 있다.
다만 해시 충돌, rehash, 해시 함수 품질에 따라 성능이 달라질 수 있다는 점은 고려해야 한다.

---

레드-블랙 트리란?

map은 보통 내부적으로 레드-블랙 트리 기반으로 구현된다.

레드-블랙 트리는 각 노드에 Red 또는 Black 색상을 부여하여
트리의 높이가 한쪽으로 치우치지 않도록 균형을 유지하는 트리이다.

일반 이진 탐색 트리는 정렬된 데이터를 순차적으로 삽입하면 한쪽으로 길게 늘어진 형태가 될 수 있다.
이 경우 탐색 성능이 O(N)까지 나빠질 수 있다.

레드-블랙 트리는 이런 문제를 막기 위해 색상 변경과 회전을 통해 트리의 균형을 맞춘다.

---

레드-블랙 트리의 규칙

레드-블랙 트리는 대표적으로 다음과 같은 규칙을 가진다.

1. 모든 노드는 Red 또는 Black이다.
2. 루트 노드는 Black이다.
3. Red 노드의 자식은 Black이다.
4. 임의의 노드부터 리프까지 가는 모든 경로의 Black 노드 수는 같다.

노드를 삽입할 때는 보통 Red로 시작하고 이후 규칙을 만족하도록 색상 변경과 회전을 수행한다.
이런 방식으로 트리의 균형을 유지하기 때문에 삽입, 삭제, 탐색을 O(log N)에 수행할 수 있다.

---

마무리

이번에 map과 unordered_map 두 컨테이너는 모두 key-value 데이터를 저장하지만
내부 구조가 완전히 다르다는 것을 알 수 있었다.

map은 정렬된 상태를 유지하기 위해 트리 구조를 사용하고,
unordered_map은 빠른 접근을 위해 해시 테이블을 사용한다.

따라서 컨테이너를 선택할 때는
단순히 key-value 저장이 필요하다는 이유만으로 고르기보다,
정렬된 순회가 필요한지, 빠른 탐색이 중요한지,
해시 충돌이나 rehash를 고려해야 하는지를 함께 생각해야겠다.