[Set, Map / Hash] std::map

 

 

 

1. Map이란?

이전 글에서는 std::set과 std::multiset에 대해 알아보았습니다.

이번에는 std::map과 std::multimap에 대해 알아보겠습니다.

std::map은 쉽게 말해 Set에 Key-Value 개념을 추가한 컨테이너라고 생각하면 됩니다.

즉,

• set은 값(Value)만 저장하고,
• map은 Key와 Value를 한 쌍(Pair)으로 저장합니다.

 

 

 

2. std::map의 내부 구조

std::map 역시 std::set과 마찬가지로 내부적으로 Red-Black Tree와 같은 균형 이진 탐색 트리(Balanced Binary Search Tree)를 사용합니다.

다만 트리의 각 노드에는 하나의 값이 아니라 Key와 Value가 함께 저장됩니다.

예를 들어

std::map<int, int> numbers;

를 생성한 뒤

numbers.emplace(1, 101);
numbers.emplace(2, 102);
numbers.emplace(3, 103);
numbers.emplace(4, 104);
numbers.emplace(5, 105);

를 수행하면,

각 노드는 다음과 같은 Key-Value 관계를 저장합니다.

Key	Value
1	101
2	102
3	103
4	104
5	105

이터레이션을 수행하면

for (const auto& pair : numbers)
{
    std::cout << pair.first << " : " << pair.second << '\n';
}

처럼 first는 Key, second는 Value를 의미합니다.

 

 

3. Map의 정렬 기준

std::map은 Key를 기준으로 자동 정렬됩니다.

즉,

(Key, Value)

쌍이 저장되더라도 트리의 정렬 기준은 Value가 아니라 Key입니다.

따라서 탐색과 삽입도 모두 Key를 기준으로 수행됩니다.

 

 

 

4. Key는 중복될 수 없다

std::map은 std::set과 동일하게 Key의 중복을 허용하지 않습니다.

예를 들어

numbers.emplace(1, 200);
numbers.emplace(1, 1000);

을 수행해도,

이미 Key가 1인 데이터가 존재하므로 새로운 데이터는 삽입되지 않습니다.

즉,

1 → 101

만 유지됩니다.

 

 

 

5. operator[] 사용하기

map은 emplace() 외에도

numbers[1] = 200;

처럼 대괄호([])를 이용하여 값을 저장할 수 있습니다.

이 경우에는

기존 Key가 존재하면

1 → 200

처럼 Value가 덮어쓰기(Overwrite) 됩니다.

즉,

• emplace() → 이미 존재하면 삽입 실패
• operator[] → 이미 존재하면 값 수정

이라는 차이가 있습니다.

 

 

 

6. operator[] 사용 시 주의할 점

operator[]는 존재하지 않는 Key에 접근하면

자동으로 새로운 원소를 생성합니다.

예를 들어

numbers[6];

을 수행하면,

아무 값도 대입하지 않았지만

6 → 0

이 자동으로 생성됩니다.

이는 int의 기본값(Default Value)인 0이 저장되기 때문입니다.

따라서, operator[]는 단순 조회 목적이라면 예상하지 못한 데이터가 생성될 수 있으므로 주의해서 사용해야 합니다.

 

 

 

7. 다양한 자료형 사용

Map은 int뿐 아니라 다양한 자료형을 사용할 수 있습니다.

예를 들어

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

을 사용하면

IDName

ID	Name
1	Nabi
2	Kitty
3	Coco
4	Bingo

처럼 ID와 이름을 저장할 수 있습니다.

 

 

 

8. String도 Key가 될 수 있다

Key 역시 다양한 타입을 사용할 수 있습니다.

예를 들어

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

을 사용하면

Name	ID
Bingo	4
Kitty	2
Nabi	1
Coco	3

와 같이 사용할 수 있습니다.

이때 std::string은 기본적으로 사전식(Lexicographical) 비교 연산자를 제공하기 때문에

Map은 문자열을 알파벳 순서로 자동 정렬합니다.

 

 

 

9. 시간 복잡도

std::map은 내부적으로 Balanced Binary Search Tree를 사용하므로

다음 연산들이 모두

O(log N)

의 시간 복잡도를 가집니다.

• find()
• insert()
• emplace()
• erase()

즉, 시간 복잡도는 std::set과 동일합니다.

 

 

 

10. MultiMap

std::multimap은 std::map과 거의 동일하지만

중복된 Key를 허용한다는 차이점이 있습니다.

따라서 하나의 Key에 여러 개의 Value를 저장할 수 있습니다.

기본적인 사용법은 std::map과 거의 동일하므로 쉽게 사용할 수 있습니다.

 

 

 

최종 정리

이번에는 std::map과 std::multimap에 대해 알아보았습니다.

std::map은 std::set과 동일하게 균형 이진 탐색 트리(Red-Black Tree)를 기반으로 동작하지만, 각 노드에 Key와 Value를 함께 저장한다는 차이가 있습니다.

Map은 Key를 기준으로 자동 정렬되며, Key는 중복될 수 없습니다. emplace()는 중복된 Key를 삽입하지 않지만, operator[]는 기존 Value를 덮어쓰고, 존재하지 않는 Key에 접근하면 기본값을 가진 원소를 자동으로 생성하므로 주의해야 합니다.

또한 Key와 Value에는 int, std::string 등 비교 연산이 가능한 다양한 자료형을 사용할 수 있으며, 탐색·삽입·삭제는 모두 O(log N)의 시간 복잡도를 가집니다.

다음에는 Hash Function을 사용하는 std::unordered_set과 std::unordered_map을 통해 평균 O(1)의 성능을 제공하는 해시 기반 컨테이너에 대해 알아보겠습니다.