std::map

1. 개념 & 기본 특징

---

형태

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>
> class map;

특징

1. Key-Value 쌍 저장

• 내부 요소 타입: std::pair<const Key, T>
• first: Key, second: Value

2. Key는 유일 (Unique Key)

• 같은 key를 두 번 insert하면 중복된 key의 insert는 무시
• 중복을 허용하는 버전은 std::multimap

3. 항상 정렬된 상태 유지

• Compare에 의해 오름차순 정렬이 기본 std::less<Key>
• 즉, begin에서 end까지 순회하면 key가 순서대로 나옴
• 사용자 정의 비교 함수를 통해 정렬 기준 변경 가능

4. 노드 기반 컨테이너

• 각 원소가 독립된 노드로 존재
• vector처럼 메모리가 연속적이지 않기에 캐시 친화도가 낮음

5. Log 시간 탐색

• 내부 자료구조가 균형 이진 탐색 트리이기 때문에 탐색/삽입/삭제 모두 평균적으로 O(log N)

2. 내부 자료구조

---

대부분의 구현에서 std::map은 균형 이진 탐색 트리의 일종인 Red-Black Tree로 구현.

트리의 높이가 log N이 되도록 보장

Red-Black Tree의 핵심 규칙 (간단 요약)

1. 각 노드는 Red 또는 Black의 색을 가짐
2. 루트는 항상 Black
3. 리프(NULL 노드)는 Black으로 간주
4. Red 노드의 자식은 항상 Black (Red가 연속으로 나오지 않음)
5. 임의의 한 노드에서 리프 노드까지 도달하는 모든 경로에는 항상 같은 수의 블랙 노드가 있음

3. std::map의 장단점 & 사용 시점

---

장점

1. 항상 정렬된 상태 유지

• for (auto& [k, v] : m) 시 자동으로 오름차순
• lower_bound, upper_bound 등 구간 검색에 좋음

2. 시간 복잡도 예측 가능

• 삽입/삭제/탐색 모두 O(log N)

3. iterator 안정성

• 삽입 시 기존 iterator 유지
• 삭제 시 해당 원소만 무효

단점

1. 노드 기반 구조 -> 캐시 비우호적

• 각 노드가 힙에 따로 할당되고 포인터로 연결
• 순차 접근 시 CPU 캐시 히트율이 낮음
• 같은 개수의 데이터를 std::vector에 정렬하여 이진 탐색하는 방식에 비해 실제 런타임에서는 느릴 수 있음

2. 메모리 오버헤드

• 각 노드마다 포인터, color 정보 등 메타데이터 포함

3. 해시 기반 컨테이너 대비 탐색 느림

• std::unordered_map은 평균 O(1) 탐색
• 많은 원소에서 단순 key->value 조회만 한다면 unordered_map이 더 유리

사용 시점

• key가 항상 정렬된 상태를 유지해야 할 때
  • 순서대로 순회가 중요한 경우
  • 범위 검색 (lower_bound, upper_bound)이 중요한 경우
• iterator를 길게 들고 다니면서 삽입/삭제가 자주 일어나는 경우
• 해시를 정의하기 애매한 복잡한 key 타입의 경우