CS — std map

📕 04/29 — std::map (Red-Black Tree 기반 정렬 연관 컨테이너)

모의면접 후속 주제: “std::map은 어떻게 동작하나요? unordered_map과 어떻게 다른가요?” Red-Black Tree → 5가지 속성과 회전 → O(log n) 보장 → 해시맵과의 비교 → 캐시 친화성·메모리 오버헤드 → 언리얼 TMap/TSortedMap 꼬리질문 연결 다리

---

학습 영역 전환점 — 시퀀스에서 연관 컨테이너로

13번에서 시퀀스 컨테이너(vector vs list) 의 메모리 레이아웃과 캐시 친화성을 다뤘다면, 14번부터는 연관 컨테이너(Associative Container) 의 검색 자료구조 영역으로 넘어옵니다.

13번  std::vector vs std::list                — 시퀀스: 연속 메모리 vs 분산 노드 + CPU 캐시
─────────────────────────────────────────────────────────────────────────────
14번  std::map                                — 연관: 정렬 트리 (Red-Black Tree) ★
이후  std::unordered_map / 해시 충돌 / 정렬   — 해시 자료구조 + 알고리즘 영역

13번이 “메모리 레이아웃이 캐시 성능을 결정한다” 였다면, 14번은 “같은 키-값 저장소라도 정렬 트리(O(log n) 보장) 와 해시 테이블(평균 O(1)) 은 트레이드오프가 정반대” 라는 점이 핵심입니다. 면접에서는 거의 항상 map vs unordered_map 이 한 세트로 나옵니다.

---

모의면접 답변

std::map은 정렬된 연관 컨테이너로, 키-값 쌍을 키 기준으로 자동 정렬해 저장합니다. 내부 자료구조는 거의 모든 표준 라이브러리 구현에서 Red-Black Tree (자기 균형 이진 탐색 트리) 입니다. 키 중복은 허용하지 않고, <map> 헤더에 std::map<Key, Value, Compare, Allocator> 템플릿으로 정의됩니다.

Red-Black Tree는 각 노드에 빨강·검정 색깔을 부여하고 5가지 속성을 유지해 트리 높이를 항상 O(log n) 으로 보장합니다. 1) 모든 노드는 빨강 또는 검정, 2) 루트는 검정, 3) 모든 NIL(리프) 은 검정, 4) 빨강 노드의 자식은 반드시 검정 (빨강 연속 금지), 5) 임의 노드에서 후손 NIL 까지의 경로마다 검정 노드 개수가 동일합니다(black height). 삽입·삭제 시 회전(rotation) 과 색 변경(recoloring) 으로 이 속성을 복구합니다. 그래서 insert·erase·find 모두 O(log n) 최악 보장입니다.

비슷한 자기 균형 BST 인 AVL 트리와 비교하면, AVL 은 더 엄격한 균형(높이 차 1 이하)으로 검색이 약간 빠르지만 회전 횟수가 많아 삽입·삭제가 느립니다. RB 트리는 균형이 약간 느슨한 대신 회전이 적어 삽입·삭제 위주 워크로드에서 유리합니다. 그래서 STL 의 map·set 은 RB 트리를 채택했습니다.

std::unordered_map 은 해시 테이블 기반으로 평균 O(1) 조회·삽입·삭제를 제공하지만 정렬이 안 되고 최악은 O(n) 입니다(해시 충돌). 메모리 오버헤드도 버킷 배열 + 노드로 더 큽니다. map 은 키 정렬·범위 조회·O(log n) 최악 보장이 필요할 때, unordered_map 은 순서 무관 + 최대 처리량이 중요할 때 선택합니다.

iterator 무효화 규칙은 vector 와 정반대로 깔끔합니다. map 은 삽입 시 다른 iterator 가 무효화되지 않고, 삭제 시에도 삭제된 노드의 iterator 만 무효화됩니다. 이는 list 와 같은 노드 안정성으로, RB 트리가 노드를 힙에 분산 할당하기 때문에 자연스럽게 따라옵니다. 단, 그 대가로 캐시 친화성이 떨어져 vector 보다 순회가 느립니다.

언리얼에서는 STL map 에 직접 대응하는 1급 컨테이너가 없습니다. TMap 은 해시 기반(unordered_map 대응) 이고, 정렬이 필요하면 TSortedMap 을 사용합니다. 게임 엔진 특성상 캐시 친화성이 우선이라 RB 트리 컨테이너는 의도적으로 두지 않은 것입니다.

---

핵심 개념

분류	키워드	한 줄 정의
연관 컨테이너	std::map	RB-Tree 기반 정렬된 키-값 컨테이너. 키 중복 불가
	std::set	RB-Tree 기반 정렬된 키 집합. value 없음
	std::multimap	동일 키 중복 허용. equal_range 로 범위 조회
	std::multiset	동일 키 중복 허용 set
	std::unordered_map	해시 테이블 기반. 평균 O(1), 순서 없음
	std::unordered_set	해시 테이블 기반 키 집합
	std::unordered_multimap / _multiset	해시 + 중복 허용
자기 균형 BST	Red-Black Tree	노드 색깔 5속성으로 높이 O(log n) 보장
	AVL Tree	높이 차 1 이하 엄격 균형. 회전 잦음
	black height	임의 노드에서 NIL 까지 경로의 검정 노드 수
	NIL 노드	리프 (실제 자식이 없는 위치). 항상 검정
	회전 (Rotation)	좌회전/우회전 — 부모-자식 관계 재배치
	재색칠 (Recoloring)	색깔만 바꿔 속성 복구 (회전 없이)
해시 테이블	버킷 (Bucket)	해시값으로 매핑되는 슬롯. 배열로 관리
	해시 함수 (Hash Function)	키 → 정수 매핑. 균등 분포가 핵심
	충돌 (Collision)	다른 키가 같은 버킷에 매핑됨. 체이닝/오픈 어드레싱으로 해결
	체이닝 (Separate Chaining)	같은 버킷의 원소를 연결 리스트로 묶음 (STL 채택)
	로드 팩터 (Load Factor)	size / bucket_count. 초과 시 rehash
	rehash	버킷 배열 확장 + 모든 원소 재배치 — O(n)
시간 복잡도	O(log n)	map 모든 핵심 연산. 트리 높이에 비례
	O(1) 평균	unordered_map 의 조회·삽입·삭제
	O(n) 최악	unordered_map 해시 충돌 시
iterator 안정성	노드 안정성	map 은 삭제된 노드만 무효, 나머지 안전 (list 와 동일)
	rehash 무효화	unordered_map rehash 시 모든 iterator 무효화
메모리 오버헤드	map 노드 크기	부모 8B + 좌 8B + 우 8B + 색 + 키-값 + 힙 헤더 ~16B
	unordered_map 오버헤드	버킷 배열 + 체이닝 노드 (next 포인터)
코드 관용구	operator[]	키 없으면 default 삽입 (mutating). const 에서 못 씀
	find vs count	find 는 iterator, count 는 0 또는 1 (multimap 에서만 의미)
	emplace	in-place 생성 — 임시 객체 회피
	try_emplace (C++17)	키 있으면 아무 일도 안 함 — operator[] 보다 안전
	insert_or_assign (C++17)	있으면 대입, 없으면 삽입 — 명확한 의도
	structured binding (C++17)	for (auto& [k, v] : m)
언리얼 컨테이너	TMap	해시 기반 — STL unordered_map 대응
	TSortedMap	정렬 기반이지만 RB-Tree 가 아닌 정렬된 배열
	TMultiMap	키 중복 허용

---

목차

1. 핵심 요약 카드
2. std::map 이란 — 정렬된 연관 컨테이너
3. 내부 동작 — Red-Black Tree
4. 주요 연산과 시간 복잡도
5. iterator 무효화 규칙 (vector·list 와 비교)
6. 유사한 범위의 다른 컨테이너 — set / multimap / unordered_*
7. 코드 예제 — 기본 사용 / Custom Compare / emplace
8. 면접 단골 꼬리물기
9. 언리얼 TMap vs STL
10. 회귀 다리 — 다른 CS 파일 연결
11. 꼬리질문 예상 경로
12. 모의면접 답변 템플릿 (1분 / 3분)

---

1. 핵심 요약 카드

한 줄 요약 30초

std::map      — RB-Tree 기반 정렬 연관 컨테이너.
                 insert/erase/find 모두 O(log n) 최악 보장.
                 키 중복 불가, 키 자동 정렬, 노드 안정성 (삭제 노드만 무효).
unordered_map — 해시 테이블 기반. 평균 O(1), 최악 O(n), 순서 없음.

선택 룰      — 정렬·범위 조회·최악 보장 필요 → map
              순서 무관·최대 처리량 → unordered_map

시간 복잡도 표 30초

연산	map	unordered_map
insert	O(log n)	평균 O(1), 최악 O(n)
erase	O(log n)	평균 O(1), 최악 O(n)
find	O(log n)	평균 O(1), 최악 O(n)
operator[]	O(log n)	평균 O(1)
순회 begin → end	O(n) (정렬 순)	O(n) (순서 없음)
범위 조회 (lower/upper_bound)	O(log n) ★	지원 안 함

Red-Black Tree 5속성 30초

1) 모든 노드는 빨강 또는 검정
2) 루트는 검정
3) 모든 NIL (리프) 은 검정
4) 빨강 노드의 자식은 반드시 검정 (빨강 연속 금지)
5) 임의 노드 → 후손 NIL 까지 경로의 검정 노드 수 동일 (black height)

→ 트리 높이가 최악 2 log(n+1) 로 제한
→ insert/erase/find 모두 O(log n) 보장

꼬리질문 연결 맵

std::map
├── 내부 동작 — Red-Black Tree
│   ├── 5가지 속성 (R/B 색깔 규칙)
│   ├── 회전 (LL, RR, LR, RL) + 재색칠
│   └── AVL 과 비교 (회전 횟수 트레이드오프)
├── 시간 복잡도 O(log n) 보장
│   └── operator[] / find / lower_bound / upper_bound
├── iterator 무효화 (★ 13번 회귀)
│   ├── 삽입 — 무효화 없음
│   └── 삭제 — 삭제된 노드만 무효
├── unordered_map 비교 ★ 가장 중요한 꼬리물기
│   ├── 해시 테이블 (버킷 + 체이닝)
│   ├── 평균 O(1) vs 최악 O(n)
│   └── 캐시 친화성 / 메모리 오버헤드
├── set / multimap / multiset
│   └── equal_range 로 동일 키 범위 조회
├── 코드 관용구
│   ├── operator[] vs find vs at
│   ├── emplace vs insert vs try_emplace (C++17)
│   └── insert_or_assign / structured binding
└── 언리얼
    ├── TMap (해시) — STL unordered_map 대응
    ├── TSortedMap (정렬 배열, RB 아님)
    └── 게임 엔진은 RB 트리 회피 — 캐시 친화 우선

---

2. std::map 이란 — 정렬된 연관 컨테이너

핵심 한 문장

std::map 은 키 기준으로 자동 정렬되는 키-값 쌍 컨테이너이며, 내부적으로 Red-Black Tree 를 써서 모든 핵심 연산이 O(log n) 최악 보장됩니다.

2-1. 기본 정의

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

• Key — 키 타입 (정렬되어야 함)
• T — 값 타입
• Compare — 정렬 기준. 기본은 std::less<Key> (오름차순)
• Allocator — 메모리 할당자

#include <map>
#include <string>

std::map<std::string, int> ages;
ages["Alice"] = 30;
ages["Bob"]   = 25;
ages["Carol"] = 35;

// 순회 시 자동으로 키 정렬 순서: Alice → Bob → Carol
for (const auto& [name, age] : ages) {
    std::cout << name << ": " << age << "\n";
}

2-2. 키 중복 불가, 자동 정렬

std::map<int, std::string> m;
m.insert({3, "three"});
m.insert({1, "one"});
m.insert({2, "two"});
m.insert({1, "ONE"});   // 무시됨 — 키 1 이미 존재

// 순회 결과: (1, "one"), (2, "two"), (3, "three")

• 같은 키 두 번 삽입하면 두 번째는 삽입 실패 (값이 덮어쓰이지 않음)
• 값을 덮어쓰려면 m[1] = "ONE" 또는 insert_or_assign(1, "ONE") 사용

2-3. std::pair<const Key, T> 가 원소 타입인 이유

using value_type = std::pair<const Key, T>;
//                          ^^^^^^^^^^^
//                          키는 const — 변경 불가

• 키를 변경하면 트리 정렬 순서가 깨지므로 const 로 막음
• 값(T) 만 변경 가능

auto it = m.find(1);
it->second = "modified";   // ✅ 값 변경 OK
it->first = 99;            // ❌ 컴파일 에러 — const Key

2-4. 헤더와 표준 시그니처

#include <map>           // map, multimap

namespace std {
    template <class Key, class T, class Compare, class Allocator>
    class map;
    template <class Key, class T, class Compare, class Allocator>
    class multimap;       // 키 중복 허용
}

2-5. 어디에 쓰는가

사용 사례	이유
정렬된 사전 (이름 → 나이)	키 자동 정렬, 순회 시 정렬 순서
범위 조회 (특정 시간 범위의 이벤트)	lower_bound/upper_bound O(log n)
최악 시간 보장이 필요한 시스템	해시 충돌로 인한 O(n) 스파이크 회피
키가 복잡한 비교 가능 객체	Compare 만 정의하면 됨 (해시 함수 불필요)
변경 빈도가 적고 정렬 순회가 잦음	트리 순회 자체는 깔끔

해시가 더 적합한 경우:

• 키 정렬이 필요 없음
• 최대 처리량이 중요 (게임 엔진, 인메모리 캐시)
• 키가 해시 함수로 잘 분포됨 (정수, 문자열 등)

---

3. 내부 동작 — Red-Black Tree

핵심 한 문장

Red-Black Tree 는 각 노드에 빨강·검정 색깔을 부여하고 5가지 속성을 유지해 트리 높이를 O(log n) 으로 보장하는 자기 균형 이진 탐색 트리입니다. STL map·set 의 표준적 구현입니다.

3-1. 왜 자기 균형 BST 가 필요한가

일반 이진 탐색 트리(BST) 의 문제:

순서대로 삽입한 경우 (1, 2, 3, 4, 5):

       1
        \
         2
          \
           3
            \
             4
              \
               5

→ 트리가 한쪽으로 치우침 (skewed)
→ 높이 = n
→ 검색이 O(n) — 사실상 연결 리스트와 동일

자기 균형 BST 는 삽입·삭제할 때마다 자동으로 균형을 맞춰 높이를 O(log n) 으로 유지합니다.

RB-Tree 로 같은 데이터 삽입:

         3
       /   \
      1     4
       \     \
        2     5

→ 높이 3 — log₂(5) ≈ 2.3 정도 수준

3-2. Red-Black Tree 의 5가지 속성

속성 1) 모든 노드는 빨강(R) 또는 검정(B)
속성 2) 루트는 항상 검정
속성 3) 모든 NIL (리프) 은 검정
        — NIL 은 실제 자식이 없는 위치를 나타내는 가상 노드
속성 4) 빨강 노드의 자식은 반드시 검정
        — 빨강 연속 (R-R) 금지
속성 5) 임의의 노드에서 후손 NIL 까지의 모든 경로에 대해
        검정 노드 개수가 동일 (black height)

시각적 예시

         [10:B]                  ← 루트는 검정 (속성 2)
        /      \
     [5:R]    [15:R]             ← 빨강 노드. 자식은 모두 검정이어야 함 (속성 4)
     /  \      /  \
  [3:B][7:B][12:B][20:B]         ← 검정 노드들
   / \  / \  / \   / \
  N  N N  N N  N  N  N           ← NIL 노드 (모두 검정, 속성 3)

각 노드 → NIL 까지의 black height:
  10 → 어떤 NIL: 검정 = 2개 (자기 자신 포함 안 함, 또는 포함)
  → 모든 경로 동일 (속성 5) ✓

속성이 보장하는 것 — 높이 ≤ 2 log(n+1)

• 속성 4: R-R 금지 → 어떤 경로도 절반 이상이 빨강일 수 없음
• 속성 5: 모든 경로의 검정 수 동일 → 검정 경로 길이 일정
• 결과: 가장 짧은 경로(전부 검정) vs 가장 긴 경로(R-B 교대) 의 길이 차이가 2배 이내

가장 짧은 경로: B - B - B - ... (검정만)
가장 긴 경로:  R - B - R - B - ... (R/B 교대)

→ 긴 경로 ≤ 짧은 경로 × 2
→ 트리 높이 h ≤ 2 log₂(n+1)
→ 모든 연산 O(log n) 보장

3-3. 삽입 — 회전과 재색칠

새 노드는 항상 빨강으로 삽입합니다 (속성 5: black height 변화 최소화).

삽입 알고리즘:
  1. BST 규칙으로 위치 찾기
  2. 새 노드를 빨강으로 삽입
  3. 속성 위반 검사 → 위반이면 복구 루프:
     - 부모가 검정이면 아무 작업 없이 종료
     - 부모가 빨강이고 삼촌도 빨강 → 재색칠 (할아버지가 빨강이 됨, 위로 전파)
     - 부모가 빨강이고 삼촌이 검정 → 회전 + 재색칠

회전 4가지 케이스

LL (왼쪽 자식의 왼쪽 자식이 빨강):

       G(B)                     P(B)
      /    \                   /    \
    P(R)   U(B)    →RR회전    X(R)  G(R)
    /                                  \
  X(R)                                 U(B)

LR (왼쪽 자식의 오른쪽 자식이 빨강):

       G(B)                G(B)                   X(B)
      /    \              /    \                 /    \
    P(R)   U(B)  →LR     X(R)  U(B)   →RR     P(R)   G(R)
       \                  /                              \
       X(R)              P(R)                            U(B)

RL (오른쪽의 왼쪽 자식): LR 의 대칭
RR (오른쪽의 오른쪽 자식): LL 의 대칭

핵심:

• 회전(Rotation) 은 BST 속성을 유지하면서 부모-자식 관계를 재배치
• 재색칠(Recoloring) 은 회전 없이 색깔만 바꿔 속성 복구
• 삽입 시 회전은 최대 2번 (LR, RL 케이스에서만 2번)

3-4. 삭제 — 더 복잡한 복구

삭제는 black height 가 깨질 수 있어 더 까다롭습니다.

삭제 알고리즘 요약:
  1. BST 규칙으로 삭제할 노드 찾기
  2. 자식이 2개면 후속자(successor) 와 값 교환 → 자식 0/1개 케이스로 환원
  3. 삭제할 노드가 빨강 → 그냥 삭제 (속성 5 영향 없음)
  4. 삭제할 노드가 검정 → black height 1 감소 → 복구 루프:
     - 형제 노드의 색깔과 자식들에 따라 5가지 케이스 분기
     - 회전 + 재색칠로 black height 복구

삭제 시 회전은 최대 3번 으로 제한됩니다.

3-5. 왜 RB 트리인가 — AVL 과의 비교

특성	Red-Black Tree	AVL Tree
균형 조건	색깔 5속성 (느슨한 균형)	모든 노드의 좌우 높이 차 ≤ 1 (엄격)
트리 높이	≤ 2 log(n+1)	≤ 1.44 log(n+2)
검색 속도	약간 느림	약간 빠름
삽입 회전	최대 2회 ★	최대 1회지만 위로 전파 가능
삭제 회전	최대 3회	최대 O(log n) 회
메모리	색깔 1비트	높이 정보 (보통 4바이트)
사용처	STL map/set, Linux CFS 스케줄러	DB 인덱스 (전통적)

핵심 트레이드오프:

• AVL — 검색 위주 워크로드에 유리 (균형이 엄격해 트리 높이가 약간 낮음)
• RB — 삽입·삭제 위주 워크로드에 유리 (회전이 적어 갱신 비용 낮음)

STL map 은 일반 목적이고 삽입·삭제도 자주 일어나므로 RB 트리를 채택했습니다.

3-6. 노드 메모리 레이아웃

// libstdc++ 의 _Rb_tree_node 단순화
struct _Rb_tree_node {
    _Rb_tree_color color;        // R or B (1바이트지만 정렬로 보통 4~8B)
    _Rb_tree_node* parent;       // 부모 8B
    _Rb_tree_node* left;         // 왼쪽 자식 8B
    _Rb_tree_node* right;        // 오른쪽 자식 8B
    std::pair<const Key, T> data; // 키-값 쌍
};

std::map<int, int> 노드 1개:

색깔 + 부모 + 좌 + 우 + (키 4B + 값 4B + 패딩 4B) + 힙 헤더 ~16B
≈ 8 + 8 + 8 + 8 + 12 + 16 = 60바이트

데이터 8바이트(int 키+값) 를 위해 60바이트 사용 → 효율 ~13%

13번 list 와 마찬가지로 노드 분산 + 큰 오버헤드 — 캐시 친화성이 vector 대비 떨어집니다.

---

4. 주요 연산과 시간 복잡도

핵심 한 문장

std::map 의 모든 핵심 연산은 트리 높이 O(log n) 에 비례하며, 이게 해시맵의 평균 O(1) 과 가장 큰 차이입니다.

4-1. 시간 복잡도 종합

연산	복잡도	비고
insert(pair)	O(log n)	위치 찾기 + 회전
insert(hint, pair)	amortized O(1)	hint 가 정확하면
erase(key)	O(log n)	노드 찾기 + 복구
erase(iterator)	amortized O(1)	iterator 직접 가짐
find(key)	O(log n)	표준 BST 검색
count(key)	O(log n)	map 은 0/1, multimap 은 동일 키 개수
contains(key) (C++20)	O(log n)	find != end 와 동일
operator[](key)	O(log n)	없으면 default 삽입 (mutating!)
at(key)	O(log n)	없으면 std::out_of_range 예외
lower_bound(key)	O(log n)	key 이상의 첫 원소
upper_bound(key)	O(log n)	key 초과의 첫 원소
equal_range(key)	O(log n)	[lower, upper) 쌍
begin() / end()	O(1)	보통 캐시된 포인터
size()	O(1)	별도 카운터 유지
전체 순회	O(n)	중위 순회 → 정렬된 키 순서

4-2. operator[] 의 함정

std::map<std::string, int> m;
m["Alice"] = 30;        // 삽입
int x = m["Bob"];       // ★ Bob 이 없으면 default(0) 로 삽입됨!
                        //    그리고 x 는 0

// const map 에서는 컴파일 에러
const std::map<std::string, int> cm = {{"Alice", 30}};
int x = cm["Alice"];    // ❌ 컴파일 에러 — operator[] 가 mutating
                        //    없으면 삽입을 해야 하므로 const 에 못 씀
int y = cm.at("Alice"); // ✅ at 사용

안전한 대안

// 1) find 사용 — 가장 명확
auto it = m.find("Bob");
if (it != m.end())
    std::cout << it->second;

// 2) at — 없으면 예외
try {
    int x = m.at("Bob");
} catch (const std::out_of_range&) {
    // 키 없음
}

// 3) contains (C++20)
if (m.contains("Bob"))
    std::cout << m["Bob"];

// 4) count != 0
if (m.count("Bob"))
    std::cout << m["Bob"];

4-3. 범위 조회 — map 의 정직한 강점

해시맵으로는 못 하는 연산입니다.

std::map<int, std::string> events;
events[100] = "A";
events[200] = "B";
events[300] = "C";
events[400] = "D";
events[500] = "E";

// 시간 150 ~ 400 사이의 이벤트
auto from = events.lower_bound(150);   // 200 가리킴
auto to   = events.upper_bound(400);   // 500 가리킴

for (auto it = from; it != to; ++it)
    std::cout << it->first << ": " << it->second << "\n";
// 200: B
// 300: C
// 400: D

해시맵은 키가 정렬돼 있지 않아 이런 범위 조회를 O(log n) 으로 못 함. 이게 정렬·범위 조회가 필요할 때 map 을 선택하는 결정적 이유입니다.

4-4. hint 를 활용한 amortized O(1) 삽입

std::map<int, int> m;
auto hint = m.end();

// 정렬된 데이터를 순서대로 삽입할 때
for (int i = 0; i < 1'000'000; ++i)
    hint = m.insert(hint, {i, i * 10});  // amortized O(1)

// hint 없이는 매번 O(log n) → 총 O(n log n)

C++11 이후 hint 가 정확(직전 위치) 하면 O(1) 으로 처리됩니다. 정렬된 입력에 매우 효과적.

4-5. 순회 — 중위 순회 = 정렬된 순서

std::map<int, std::string> m = {
    {3, "three"}, {1, "one"}, {2, "two"}
};

for (const auto& [k, v] : m)
    std::cout << k << ": " << v << "\n";
// 1: one
// 2: two
// 3: three   ← 자동 정렬

내부적으로 RB-Tree 의 중위 순회(in-order traversal) — 왼쪽 부분트리 → 자기 → 오른쪽 부분트리. 이게 BST 정의에 의해 정렬된 키 순서를 보장합니다.

---

5. iterator 무효화 규칙 (vector·list 와 비교)

핵심 한 문장

std::map 의 iterator 는 노드 안정성 이 강해서 삽입은 무효화가 전혀 없고 삭제도 삭제된 노드만 무효화됩니다 — vector 와 정반대, list 와 동일합니다.

5-1. map 의 무효화 규칙

연산	iterator 무효화
insert	없음 ★
emplace	없음 ★
erase(it)	삭제된 it 만 무효
erase(key)	해당 노드 it 만 무효
clear()	모두

std::map<int, std::string> m = {{1, "one"}, {2, "two"}, {3, "three"}};
auto it = m.find(2);                    // it → (2, "two")

m.insert({4, "four"});                  // ✅ it 그대로 유효
m.insert({0, "zero"});                  // ✅ it 그대로 유효
m.emplace(5, "five");                   // ✅ it 그대로 유효

m.erase(1);                             // ✅ it 유효 (다른 노드 삭제)
m.erase(it);                            // ❌ it 무효화 — 삭제된 본인

// erase 후 다음 노드를 안전하게 얻으려면:
auto next_it = m.erase(it);             // C++11+ — 다음 노드 반환

이는 노드 단위 자료구조(list, map, set 등) 의 공통 특성 — RB 트리가 노드를 힙에 분산 할당해 한 노드 이동/삭제가 다른 노드 주소에 영향 없습니다.

5-2. 컨테이너별 비교표

	vector	list	map	unordered_map
메모리 레이아웃	연속	분산 노드	분산 노드 (트리)	버킷 배열 + 분산 노드
insert iterator 무효화	재할당 시 모두	없음	없음	rehash 시 모두
erase iterator 무효화	위치 이후 모두	삭제 노드만	삭제 노드만	삭제 노드만
노드 안정성	약함	강함	강함	약함 (rehash)
캐시 친화	★★★★★	★	★★	★★
검색 복잡도	O(n)	O(n)	O(log n)	평균 O(1)
정렬	사용자 책임	사용자 책임	자동 ★	없음

map 의 iterator 안정성은 외부 자료구조에 iterator 를 저장해 둘 수 있는 강점으로 이어집니다. 13번 list 의 정직한 장점과 동일한 맥락.

5-3. unordered_map 의 rehash 무효화 — 주의

std::unordered_map<int, int> u;
auto it = u.insert({1, 100}).first;    // it 가 (1, 100) 가리킴

for (int i = 0; i < 10000; ++i)
    u.insert({i, i});                   // ★ rehash 발생 → 모든 iterator 무효!

*it;                                    // ❌ UB — 댕글링 (10번 회귀)

해시맵은 로드 팩터 초과 시 버킷 배열 확장 + 모든 원소 재배치(rehash) 가 일어나 모든 iterator·포인터·참조가 무효화됩니다. 13번 vector 재할당과 같은 패턴.

→ map 은 이런 무효화가 없음 이 안정성 면에서의 결정적 차이.

---

6. 유사한 범위의 다른 컨테이너 — set / multimap / unordered_*

핵심 한 문장

map 가족은 (정렬 vs 해시) × (키만 vs 키-값) × (중복 허용 vs 불허) 의 8가지 조합입니다. 가장 자주 쓰는 4가지를 먼저 익히고, 나머지는 표로 기억하세요.

6-1. std::set — 키만 저장

#include <set>

std::set<int> s = {3, 1, 4, 1, 5, 9, 2, 6};
// 자동 정렬 + 중복 제거 → {1, 2, 3, 4, 5, 6, 9}

s.insert(7);
s.erase(4);
if (s.count(3))         // 정렬 컨테이너의 멤버십 검사
    std::cout << "3 exists\n";

• map 의 value 제거 버전, 동일하게 RB-Tree 기반
• O(log n) insert/find/erase
• 키 중복 불가, 자동 정렬

6-2. std::multimap — 중복 키 허용

#include <map>

std::multimap<std::string, int> scores;
scores.insert({"Alice", 85});
scores.insert({"Alice", 92});      // ✅ 같은 키로 두 번째 항목
scores.insert({"Alice", 78});
scores.insert({"Bob",   90});

// Alice 의 모든 점수 조회 — equal_range 사용
auto [from, to] = scores.equal_range("Alice");
for (auto it = from; it != to; ++it)
    std::cout << it->second << "\n";   // 85, 92, 78

• 같은 키에 여러 값 저장 가능
• operator[] 와 at 은 없음 (어떤 값을 반환할지 모호)
• equal_range 로 같은 키 범위 조회
• 사용 사례: 시간 → 이벤트 (같은 시간에 여러 이벤트), 태그 → 항목

6-3. std::multiset

std::multiset<int> ms = {1, 2, 2, 3, 3, 3};
// 자동 정렬, 중복 허용 → {1, 2, 2, 3, 3, 3}
ms.count(3);   // 3 (중복 개수 반환 — set 과 다른 점)

6-4. std::unordered_map — 해시 기반

#include <unordered_map>

std::unordered_map<std::string, int> u;
u["Alice"] = 30;
u["Bob"]   = 25;

// 평균 O(1) 조회
if (u.contains("Alice"))    // C++20
    std::cout << u["Alice"];

// 버킷 통계
std::cout << "size: " << u.size() << "\n";
std::cout << "bucket count: " << u.bucket_count() << "\n";
std::cout << "load factor: " << u.load_factor() << "\n";  // size / bucket_count

내부 구조

버킷 배열 + 체이닝 (Separate Chaining)

    bucket[0]  →  null
    bucket[1]  →  ("Alice", 30) → null
    bucket[2]  →  null
    bucket[3]  →  ("Bob", 25) → ("Carol", 35) → null   ← 충돌
    bucket[4]  →  null
    ...

해시 함수: hash(key) % bucket_count → 버킷 인덱스

• 평균 O(1) (균등한 해시 분포 + 적절한 로드 팩터)
• 최악 O(n) (모든 키가 한 버킷에 몰릴 경우)
• 정렬 없음, 메모리 더 사용

6-5. unordered_set / unordered_multimap / unordered_multiset

std::unordered_set<int> us = {3, 1, 4, 1, 5};            // 해시 + 키만 + 중복 X
std::unordered_multimap<std::string, int> umm;            // 해시 + 키-값 + 중복 O
std::unordered_multiset<int> ums = {1, 2, 2, 3};          // 해시 + 키만 + 중복 O

특징은 정렬 컨테이너(set, multimap, multiset) 의 해시 버전과 동일.

6-6. 8가지 조합 종합표

	정렬 (RB-Tree)	해시 (Hash Table)
키-값 + 중복 X	std::map	std::unordered_map
키-값 + 중복 O	std::multimap	std::unordered_multimap
키만 + 중복 X	std::set	std::unordered_set
키만 + 중복 O	std::multiset	std::unordered_multiset

6-7. 선택 가이드

요구사항	선택
키 정렬 필요	map / set
빠른 조회 (순서 무관)	unordered_map / unordered_set
키 중복 허용 + 정렬	multimap / multiset
키 중복 허용 + 빠른 조회	unordered_multimap / unordered_multiset
범위 조회 (lower/upper_bound)	map / set ★ 해시 불가
최악 시간 보장 필요	map / set (해시는 O(n) 최악)
키가 해시 함수 정의 어려움	map / set (Compare 만 정의)

6-8. map vs unordered_map 정량 비교

항목	std::map	std::unordered_map
자료구조	Red-Black Tree	해시 테이블 (체이닝)
평균 조회	O(log n)	O(1)
최악 조회	O(log n)	O(n)
정렬	자동	없음
범위 조회	O(log n)	지원 안 함
iterator 안정성	삽입 무효화 없음	rehash 시 모두 무효
메모리 오버헤드	노드당 ~60B (8B 키-값 기준)	버킷 + 노드
캐시 친화성	낮음 (트리 노드 분산)	보통 (버킷 배열은 연속)
키 요구사항	Compare (정렬 가능)	Hash + equal_to (해시 + 비교)
사용 예	정렬 사전, 시간순 이벤트	인메모리 캐시, 빠른 룩업

---

7. 코드 예제 — 기본 사용 / Custom Compare / emplace

7-1. 기본 사용법

#include <map>
#include <iostream>
#include <string>

int main() {
    std::map<std::string, int> ages;

    // 삽입 — 4가지 방법
    ages["Alice"] = 30;                          // operator[]
    ages.insert({"Bob", 25});                    // insert
    ages.insert(std::make_pair("Carol", 35));
    ages.emplace("Dave", 40);                    // emplace (in-place)

    // 조회
    if (auto it = ages.find("Alice"); it != ages.end())
        std::cout << it->first << ": " << it->second << "\n";

    // 안전 접근
    try {
        int age = ages.at("Eve");                // 없으면 예외
    } catch (const std::out_of_range& e) {
        std::cout << "not found\n";
    }

    // 삭제
    ages.erase("Bob");

    // 순회 (정렬 순서)
    for (const auto& [name, age] : ages)
        std::cout << name << ": " << age << "\n";

    // 크기/빈 여부
    std::cout << "size: " << ages.size() << "\n";
    std::cout << "empty: " << ages.empty() << "\n";
}

7-2. Custom Compare — 정렬 기준 변경

// 내림차순 정렬 — std::greater 사용
std::map<int, std::string, std::greater<int>> desc;
desc[1] = "one";
desc[3] = "three";
desc[2] = "two";

for (const auto& [k, v] : desc)
    std::cout << k << ": " << v << "\n";
// 3: three
// 2: two
// 1: one

// 람다로 커스텀 비교 (대소문자 무시 정렬)
auto ci_less = [](const std::string& a, const std::string& b) {
    return std::lexicographical_compare(
        a.begin(), a.end(), b.begin(), b.end(),
        [](char ca, char cb) { return std::tolower(ca) < std::tolower(cb); }
    );
};

std::map<std::string, int, decltype(ci_less)> m(ci_less);
m["Alice"] = 1;
m["bob"]   = 2;
m["CAROL"] = 3;
// 정렬 시 대소문자 무시: alice → bob → CAROL

7-3. structured binding (C++17)

std::map<std::string, int> m = {{"Alice", 30}, {"Bob", 25}};

// C++17 이전
for (auto it = m.begin(); it != m.end(); ++it)
    std::cout << it->first << ": " << it->second << "\n";

// C++17 이후 — 훨씬 간결
for (const auto& [name, age] : m)
    std::cout << name << ": " << age << "\n";

// insert 결과 분해
auto [it, inserted] = m.insert({"Carol", 35});
if (inserted)
    std::cout << "newly inserted\n";

7-4. emplace vs insert vs operator[]

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

// 1) operator[] — default 생성 후 대입 (2단계, 비효율적일 수 있음)
m["A"] = std::vector<int>{1, 2, 3};
//   ↑ 1) m["A"] 가 default vector 삽입
//     2) 그 자리에 새 vector 대입 (이동)

// 2) insert — 임시 pair 생성
m.insert({"B", std::vector<int>{4, 5, 6}});
//   ↑ pair 임시 객체 생성 + vector 복사·이동

// 3) emplace — in-place 생성 (가장 효율적)
m.emplace("C", std::vector<int>{7, 8, 9});
//   ↑ pair 의 두 인자를 받아 노드 안에서 직접 구성

// 4) try_emplace (C++17) — 키 있으면 아무 일도 안 함
auto [it, inserted] = m.try_emplace("A", std::vector<int>{99, 99});
// "A" 이미 존재 → vector 인자조차 만들지 않음
// inserted == false, it 는 기존 ("A", {1,2,3}) 가리킴

// 5) insert_or_assign (C++17) — 있으면 대입, 없으면 삽입
m.insert_or_assign("D", std::vector<int>{10, 11});
// 의도가 명확 — operator[] 의 default 삽입 트랩 회피

7-5. try_emplace 의 진짜 가치

// operator[] 함정
std::map<std::string, std::unique_ptr<Resource>> resources;

resources["key1"] = std::make_unique<Resource>("data1");
// 만약 "key1" 이 이미 있으면? → 기존 unique_ptr 파괴 + 새 unique_ptr 대입
// 의도가 "있으면 그대로 두고 없을 때만 만들기" 라면 버그!

// try_emplace 로 의도 명확화
auto [it, inserted] = resources.try_emplace("key1", std::make_unique<Resource>("data1"));
if (!inserted) {
    // 이미 존재 → make_unique 도 호출되지 않음 ★
}

C++17 의 try_emplace 는 임시 인자 생성 자체를 회피해 무브-온리 타입(unique_ptr) 에서 특히 유용합니다.

7-6. 키 객체에 < 정의하기

struct Point {
    int x, y;
    bool operator<(const Point& other) const {
        return std::tie(x, y) < std::tie(other.x, other.y);
    }
};

std::map<Point, std::string> places;
places[{1, 2}] = "A";
places[{3, 1}] = "B";
places[{1, 5}] = "C";
// 정렬: (1,2) → (1,5) → (3,1)

해시맵은 키에 std::hash 특수화 + operator== 가 필요하지만, 트리맵은 operator< 만 있으면 됩니다 — 이게 정렬 컨테이너의 작은 편의성.

---

8. 면접 단골 꼬리물기

8-1. map vs unordered_map 언제 어떤 걸?

map 선택:
  - 키 정렬이 결과적으로 필요 (정렬 출력, 범위 조회)
  - 최악 시간 보장이 필요 (실시간 시스템, SLA)
  - 키에 해시 함수 정의가 어려움 (복잡한 사용자 정의 타입)
  - 메모리 효율보다 안정성 우선

unordered_map 선택:
  - 순서 무관 (인메모리 캐시, 룩업 테이블)
  - 평균 처리량 최대화 (게임 엔진, DB 인덱스)
  - 키가 해시 함수에 잘 분포 (정수, 문자열, ID)
  - rehash 무효화를 신경 안 써도 되는 워크로드

8-2. RB-Tree 회전은 몇 종류?

4가지 케이스 (LL, LR, RL, RR) ─ 회전 자체는 2종류:
  - Right Rotation (오른쪽 회전) : LL 케이스에서 사용
  - Left Rotation (왼쪽 회전)    : RR 케이스에서 사용
  - LR : 먼저 Left → 그 다음 Right (이중 회전)
  - RL : 먼저 Right → 그 다음 Left (이중 회전)

삽입 복구 시 회전 횟수: 최대 2회
삭제 복구 시 회전 횟수: 최대 3회

8-3. 메모리 오버헤드 — map 노드는 얼마나 큰가?

// libstdc++ 기준 노드 메모리 (x86_64):
//   color  4~8B (정렬 패딩 포함)
//   parent 8B
//   left   8B
//   right  8B
//   data   sizeof(pair<const Key, T>)
//   힙 헤더 ~16B (allocator 마다 다름)

// std::map<int, int>:
//   8 + 8 + 8 + 8 + (4+4+패딩 4) + 16 ≈ 60 바이트
//   데이터 8바이트(int 키-값) → 효율 ~13%

// std::map<string, string> (각 string 32B 가정):
//   8 + 8 + 8 + 8 + 64 + 16 = 112 바이트
//   데이터 64바이트 → 효율 ~57%

13번에서 본 list 의 분석과 동일한 패턴 — 작은 키-값일수록 노드 헤더 오버헤드가 비대합니다.

8-4. 캐시 친화성 — map 은 vector 보다 느린가?

같은 N개 정수 순회:
  std::vector<int>          : ~1 ms  (1M 원소)  ← 13번
  std::list<int>            : ~100 ms          ← 13번
  std::map<int, int>        : ~50 ms 정도      ← 트리 노드 분산
  std::unordered_map<int,int>: ~10 ms 정도     ← 버킷 + 체이닝

순서:
  vector ≫ unordered_map > map > list

map 은 노드가 힙에 분산되지만 트리 구조라 부분적 지역성(부모-자식이 비교적 가까움) 이 있어 list 보다는 캐시 친화적입니다. 다만 vector 와는 비교 불가.

8-5. operator[] 가 const map 에서 안 되는 이유

const std::map<int, int> cm = {{1, 100}};
int x = cm[1];           // ❌ 컴파일 에러

operator[] 의 시그니처:

T& operator[](const Key& k) {
    auto it = find(k);
    if (it == end())
        return insert({k, T{}}).first->second;   // ★ 없으면 default 삽입 (mutating)
    return it->second;
}

키가 없을 때 자동으로 default 값을 삽입하므로 const 객체에서 호출 불가. const 에서는 at(k) 또는 find(k) 를 써야 합니다.

이 함정은 13번 vector::operator[] (경계 검사 안 함) 과 함께 면접 단골 — STL 의 “편의 vs 안전” 트레이드오프 사례.

8-6. 왜 빨강·검정 두 색만? 더 많이 쓰면 안 되나?

빨강·검정 두 색만으로도 트리 높이 2 log(n+1) 보장에 충분합니다. 색을 늘려도 균형 보장에 추가 이득이 거의 없고, 노드당 메모리만 늘어납니다(색 정보가 ~1비트에서 더 커짐).

8-7. 새 노드는 왜 빨강으로 삽입하나?

검정으로 삽입하면:
  → 그 경로의 black height 가 1 증가
  → 속성 5 (모든 경로 black height 동일) 위반
  → 다른 모든 경로의 black height 도 맞춰야 함 → 비싸다

빨강으로 삽입하면:
  → black height 변화 없음 (속성 5 유지)
  → 위반 가능성은 속성 4 (R-R 금지) 뿐
  → 부모가 검정이면 끝, 빨강이면 회전·재색칠로 국소 복구

따라서 새 노드는 항상 빨강 — 복구 비용 최소화의 영리한 트릭.

8-8. AVL 과 RB 중 뭐가 더 좋나?

워크로드 분석:
  검색 위주 (조회 ≫ 삽입/삭제) → AVL — 트리 높이 약간 낮음
  갱신 위주 (삽입·삭제 자주)   → RB  — 회전 횟수 적음
  범용 (둘 다 자주)            → RB — 표준 라이브러리들이 채택

STL/Linux 커널/Java TreeMap 모두 RB 채택 — 범용성 + 회전 비용 균형이 좋아서.
DB 인덱스(B-Tree 변형) 같은 디스크 자료구조는 다른 트리 사용.

8-9. unordered_map 의 rehash 는 언제 일어나나?

조건: load_factor() > max_load_factor()
       (size / bucket_count > 1.0 보통)

rehash 동작:
  1) 새 버킷 배열 할당 (보통 2배 크기, 소수 근처로 반올림)
  2) 모든 원소를 새 해시값으로 다시 분배
  3) 기존 버킷 배열 해제

비용: O(n) — 13번 vector 재할당과 동일한 패턴

회피: u.reserve(n) 으로 미리 버킷 확보 → 한 번에 충분한 크기 할당

8-10. 해시 충돌이 심하면 어떻게 되나?

// 모든 키가 같은 해시값을 가지는 악의적 입력:
struct BadHash {
    size_t operator()(int k) const { return 0; }   // 항상 0 반환
};

std::unordered_map<int, int, BadHash> u;
for (int i = 0; i < 1000; ++i)
    u.insert({i, i});

// 모든 원소가 bucket[0] 에 체인됨 → 사실상 연결 리스트
u.find(999);   // O(n) — 1000번 비교

악의적 입력이 가능한 환경(웹 서버 등) 에서는 해시 DoS 공격이 가능 — Java/Python 은 SipHash 같은 cryptographic 해시로 방어. C++ 표준은 명시 안 함.

8-11. multimap 에서 같은 키 순서는 보장되나?

C++11 이후로 삽입 순서가 보장됩니다 (안정성, stability).

std::multimap<int, std::string> mm;
mm.insert({1, "first"});
mm.insert({1, "second"});
mm.insert({1, "third"});

auto [from, to] = mm.equal_range(1);
for (auto it = from; it != to; ++it)
    std::cout << it->second << " ";
// first second third  ← 삽입 순서 보장

C++03 이전엔 보장 없었으나 C++11 이후 표준화.

---

9. 언리얼 TMap vs STL

핵심 한 문장

언리얼의 TMap 은 std::unordered_map 대응의 해시 테이블입니다. STL std::map 에 직접 대응하는 RB-Tree 컨테이너는 1급으로 두지 않았고, 정렬이 필요하면 TSortedMap 을 사용합니다 — 캐시 친화 우선 철학.

9-1. TMap<KeyType, ValueType> — 해시 기반

TMap<FString, int32> Ages;

Ages.Add("Alice", 30);              // std::unordered_map::insert 대응
Ages.Add("Bob", 25);
Ages["Carol"] = 35;                 // operator[] (없으면 default 삽입은 동일)

// 조회
if (int32* PAge = Ages.Find("Alice"))
    UE_LOG(LogTemp, Log, TEXT("Alice: %d"), *PAge);

// 삭제
Ages.Remove("Bob");

// 순회 (해시 순서 — 정렬 X)
for (const auto& Pair : Ages)
    UE_LOG(LogTemp, Log, TEXT("%s: %d"), *Pair.Key, Pair.Value);

내부 구조:

• 해시 테이블 + open addressing 변형 (체이닝 아님 — 캐시 친화 위해)
• GetTypeHash(Key) 로 해시 계산 — 사용자 정의 타입은 이 함수 오버로드 필요
• 평균 O(1) insert/find/remove

9-2. TSortedMap — 정렬된 맵 (RB-Tree 가 아님)

TSortedMap<int32, FString> Events;
Events.Add(300, TEXT("C"));
Events.Add(100, TEXT("A"));
Events.Add(200, TEXT("B"));

// 자동 정렬 순회
for (const auto& Pair : Events)
    UE_LOG(LogTemp, Log, TEXT("%d: %s"), Pair.Key, *Pair.Value);
// 100: A
// 200: B
// 300: C

• 내부적으로 정렬된 TArray — RB-Tree 가 아님
• 삽입: O(n) (정렬 위치에 끼워 넣기)
• 조회: O(log n) (이진 탐색)
• 작은 N + 조회 위주에서 캐시 친화로 더 빠를 수 있음

게임 엔진 철학 — “트리 노드 분산 할당보다 정렬 배열 + 이진 탐색이 캐시상 더 빠를 때가 많다”.

9-3. TMultiMap — 중복 키 허용

TMultiMap<FString, int32> Scores;
Scores.Add("Alice", 85);
Scores.Add("Alice", 92);
Scores.Add("Alice", 78);

TArray<int32> AliceScores;
Scores.MultiFind("Alice", AliceScores);
// AliceScores: {85, 92, 78}

std::multimap + std::unordered_multimap 의 통합 대응. 내부는 해시 기반.

9-4. UPROPERTY · GC 통합

UCLASS()
class AInventory : public AActor {
    GENERATED_BODY()
public:
    UPROPERTY()
    TMap<FName, UItem*> Items;       // GC 가 모든 value UObject 자동 추적

    UPROPERTY()
    TMap<int32, AActor*> ActorsById; // 키-값 모두 추적
};

• UPROPERTY() 로 선언하면 GC 가 컨테이너 안 UObject 까지 자동 추적
• 블루프린트 노출, 디테일 패널 편집 가능
• std::map<FName, UItem*> 은 GC 가 추적 못 해 언리얼에서는 절대 쓰지 않음

9-5. STL ↔ 언리얼 컨테이너 종합표

카테고리	STL	언리얼	비고
정렬 맵 (RB-Tree)	std::map	(없음) — TSortedMap 으로 대체	RB 트리 미채택
해시 맵	std::unordered_map	TMap ★ 1급 시민	open addressing
정렬 셋 (RB-Tree)	std::set	(없음) — TSortedSet? TArray::Sort
해시 셋	std::unordered_set	TSet ★ 1급 시민
중복 키 맵	std::multimap / unordered_multimap	TMultiMap

언리얼은 TArray(vector) + TMap(unordered_map) + TSet(unordered_set) 이 1급 시민이고, 트리 기반 정렬 컨테이너는 보조적입니다 — 13번에서 본 std::list 처럼 “캐시 적대적 자료구조 회피” 철학이 일관됩니다.

9-6. TMap vs std::unordered_map 차이점

	std::unordered_map	TMap
충돌 해결	Separate Chaining (체인)	open addressing 변형
캐시 친화	보통 (체인 노드 분산)	더 좋음 (배열 인접 슬롯)
메모리 오버헤드	버킷 + 노드 (next 포인터)	슬롯 배열만
GC 통합	없음	UPROPERTY 로 자동 추적
리플렉션	없음	블루프린트 자동 노출
해시 함수	std::hash<K> 특수화	GetTypeHash(K) 오버로드
비교 함수	std::equal_to<K>	operator== 오버로드

9-7. Algo:: 와 정렬

TArray<TPair<FString, int32>> Pairs;
Pairs.Add({"Alice", 30});
Pairs.Add({"Bob", 25});

// 키 기준 정렬 — std::sort 대응
Algo::Sort(Pairs, [](const auto& A, const auto& B) {
    return A.Key < B.Key;
});

// 이진 탐색
auto Idx = Algo::BinarySearchBy(Pairs, FString("Alice"),
    [](const auto& P) { return P.Key; });

정렬된 배열 + 이진 탐색 = 사실상 TSortedMap 의 내부 구조.

---

10. 회귀 다리 — 다른 CS 파일 연결

10-1. 13번 [vector vs list] 와의 연결

노드 안정성의 동일한 맥락

13번에서 list 가 vector 대비 정직한 강점이라 본 노드 안정성이 map 에도 그대로 적용됩니다.

std::map<int, std::string> m = {{1,"a"}, {2,"b"}, {3,"c"}};
auto it = m.find(2);

m.insert({4, "d"});       // ✅ it 그대로 유효 (list 와 동일)
m.erase(1);               // ✅ it 그대로 유효
m.erase(it);              // ❌ it 무효화 — 본인 삭제

// vector 였다면 push_back 한 번에 모든 iterator 가 무효화 가능

이는 분산 노드 자료구조의 공통 강점 — 트리든 연결 리스트든 노드를 힙에 분산 할당하기에 따라옵니다.

캐시 친화성 — 13번의 핵심 트레이드오프

순회 성능:
  vector ≫ unordered_map > map > list

13번에서 본 vector 의 캐시 친화성이 map 에는 부분적으로만 적용됨.
트리 노드는 부모-자식이 비교적 가깝지만 분산 할당 자체는 피할 수 없음.

→ 정렬·범위 조회가 필요 없으면 unordered_map 이 항상 더 빠르고, 더 나아가 작은 N 에서는 정렬된 vector + 이진 탐색 이 가장 빠른 경우가 많음.

10-2. 11번 [스마트 포인터] 와의 연결

map<Key, unique_ptr<T>> 패턴

std::map<std::string, std::unique_ptr<Resource>> resources;

resources.emplace("config", std::make_unique<Resource>("config.dat"));
resources.try_emplace("save", std::make_unique<Resource>("save.dat"));

// 객체 자체는 힙에 고정 → 외부 포인터 안정성
Resource* p = resources["config"].get();
resources.erase("save");                    // ✅ p 여전히 유효
resources.emplace("temp", ...);             // ✅ p 여전히 유효 (map 노드만 추가됨)

13번의 vector<unique_ptr<T>> 패턴이 map 에서는 더 자연스럽습니다 — map 은 어차피 노드 안정성을 가지므로 객체 안정성도 자동 따라옴.

try_emplace 와 unique_ptr

// operator[] 함정 — 임시 unique_ptr 생성 후 키 있으면 파괴
m["key"] = std::make_unique<Resource>("data");
// 만약 "key" 가 이미 있으면? → 기존 unique_ptr 파괴 + 새 것 대입

// try_emplace — 키 있으면 인자 자체를 만들지 않음
auto [it, inserted] = m.try_emplace("key", std::make_unique<Resource>("data"));
if (!inserted) {
    // 이미 존재 — make_unique 도 호출되지 않음 ★
}

C++17 의 진짜 가치 — 무브-온리 타입에서 의도 명확한 삽입.

10-3. 12번 [복사 금지·move-only] 와의 연결

노드 단위 안정성 → 복사·이동 비용 분석

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

m.emplace("A", /* BigObject 인자 */);  // 노드 안에서 in-place 생성
m.emplace("B", /* BigObject 인자 */);  // 다른 노드 — 기존 노드 영향 없음

// vector 와 달리 재할당이 없으므로 BigObject 의 noexcept move 여부 무관
// → 복사·이동 의미론에 덜 민감

12번에서 본 vector 의 noexcept move 요구사항은 map 에서는 거의 무관 — 노드를 옮길 일이 없으니까요.

10-4. 10번 [댕글링 포인터] 와의 연결

unordered_map rehash 무효화 = 댕글링

std::unordered_map<int, int> u;
auto* p = &u[1];                    // p 가 (1, 100) 의 value 가리킴

for (int i = 0; i < 10000; ++i)
    u.insert({i, i});               // ★ rehash 발생 → 모든 포인터 무효

*p = 99;                            // ❌ 댕글링 — 10번에서 본 패턴

13번 vector 재할당과 동일한 패턴 — 연속 메모리/버킷 배열 자료구조의 공통 함정.

→ map 은 노드 안정성으로 이 함정이 없음 — 트리맵을 선택하는 또 하나의 안전성 이유.

10-5. 09번 [RAII] 와의 연결

map 자체가 RAII:

{
    std::map<std::string, std::unique_ptr<Resource>> resources;
    resources.emplace("a", std::make_unique<Resource>(...));
    resources.emplace("b", std::make_unique<Resource>(...));
    // ...
}   // 스코프 종료 → map 소멸자 → 모든 노드 + 모든 unique_ptr 자동 해제

• 컨테이너 자체가 자원 관리
• 안의 스마트 포인터가 객체 수명 관리
• 두 RAII 가 합쳐져 누수 0 보장

13번 vector 와 동일한 RAII 사례.

10-6. 04-29(오늘) 회고 — 13번 → 14번 자연 흐름

13번 핵심 개념                  14번에서의 활용
────────────────────────────────────────────────────────────
연속 메모리 vs 분산 노드     →  map(분산 트리), unordered_map(분산+버킷)
캐시 친화성 (vector 압승)    →  vector ≫ unordered_map > map > list
iterator 무효화 트레이드오프 →  map 노드 안정 > unordered_map rehash 무효
amortized O(1) (push_back)   →  map insert(hint) 도 amortized O(1)
"의심스러우면 vector"        →  "의심스러우면 unordered_map" — 정렬 필요시만 map

14번은 13번의 캐시·복잡도 분석 프레임을 연관 컨테이너에 적용한 응용편입니다. 다음 주제(STL 알고리즘·정렬·해시 함수) 로 자연스럽게 이어집니다.

---

11. 꼬리질문 예상 경로

메인 질문 답변 후 예상 흐름

"std::map 은 어떻게 동작하나요?"
         │
         ├─ 내부 자료구조 (★ 가장 깊이)
         │    ├─ "Red-Black Tree 가 뭔가요?"
         │    │    └─ "5가지 속성을 다 말해보세요"
         │    ├─ "왜 BST 가 아닌 자기 균형 BST 인가요?"
         │    ├─ "AVL 과 비교하면?"
         │    └─ "회전 종류는?"
         │
         ├─ 시간 복잡도
         │    ├─ "왜 O(log n) 인가요?"
         │    ├─ "operator[] 가 O(log n) 인 이유?"
         │    └─ "lower_bound / upper_bound 는?"
         │
         ├─ unordered_map 비교 (★ 가장 자주)
         │    ├─ "언제 어떤 걸 쓰나요?"
         │    ├─ "unordered_map 최악이 O(n) 인 이유?"
         │    ├─ "rehash 가 뭔가요?"
         │    └─ "범위 조회는?"
         │
         ├─ iterator / 안정성
         │    ├─ "삽입할 때 iterator 가 무효화되나요?"
         │    └─ "vector 와 어떻게 다르죠?" (★ 13번 회귀)
         │
         ├─ operator[]
         │    ├─ "const map 에서 왜 못 쓰나요?"
         │    └─ "at 과 차이는?"
         │
         ├─ 메모리 오버헤드
         │    ├─ "노드 하나의 크기는?"
         │    └─ "캐시 친화성은?"
         │
         └─ 언리얼
              ├─ "TMap 은 std::map 인가요?"
              ├─ "TSortedMap 은?"
              └─ "왜 RB-Tree 컨테이너가 1급이 아닌가요?"

각 꼬리질문 30초 답변

Q: std::map 의 내부 자료구조는?

거의 모든 표준 라이브러리 구현에서 Red-Black Tree (자기 균형 BST).
노드에 빨강/검정 색깔을 부여하고 5가지 속성을 유지해
트리 높이를 항상 O(log n) 로 보장.

→ insert / erase / find 모두 O(log n) 최악 보장.

Q: Red-Black Tree 5가지 속성?

1) 모든 노드는 빨강 또는 검정
2) 루트는 항상 검정
3) 모든 NIL (리프) 은 검정
4) 빨강 노드의 자식은 반드시 검정 (R-R 금지)
5) 임의 노드 → 후손 NIL 까지 경로의 검정 노드 수 동일 (black height)

이 속성들로 트리 높이가 최악 2 log(n+1) 로 제한됨.

Q: AVL 과 RB 트리 중 뭐가 더 좋은가요?

AVL — 더 엄격한 균형 (높이 차 1 이하) → 검색 약간 빠름
RB  — 느슨한 균형 (색깔 5속성) → 회전 횟수 적음, 삽입/삭제 빠름

STL map/set 이 RB 를 선택한 이유는 일반 목적이고 갱신도 자주 있어서.
검색 비중이 압도적이면 AVL, 갱신도 많으면 RB.

Q: 새 노드는 왜 빨강으로 삽입하나요?

검정으로 삽입하면 그 경로의 black height 가 1 증가 → 속성 5 위반 →
다른 모든 경로도 맞춰야 해 비싸짐.

빨강으로 삽입하면 black height 변화 없음 → 위반 가능성은 R-R 뿐 →
국소적인 회전·재색칠로 복구 가능.

복구 비용 최소화의 영리한 선택.

Q: map 과 unordered_map 언제 어떤 걸 쓰나요? (★ 가장 자주)

map 선택:
  - 키 정렬이 결과적으로 필요
  - 범위 조회 (lower_bound / upper_bound)
  - 최악 시간 보장 필요 (실시간 시스템)
  - 키에 해시 함수 정의 어려움

unordered_map 선택:
  - 순서 무관, 최대 처리량 우선
  - 키가 해시 함수에 잘 분포 (정수, 문자열)
  - 평균 O(1) 의 이점 충분히 활용
  - rehash 무효화를 신경 안 써도 됨

요약: 정렬·범위·최악 보장 → map / 빠른 조회 → unordered_map

Q: unordered_map 의 최악 O(n) 은 왜 발생하나요?

해시 충돌 — 다른 키가 같은 버킷에 매핑됨.
체이닝 방식이라 같은 버킷의 원소가 연결 리스트로 묶임.
모든 키가 같은 버킷에 몰리면 사실상 연결 리스트 → O(n).

악의적 입력 (해시 DoS) 또는 나쁜 해시 함수가 원인.
방어: 좋은 해시 함수 + 적절한 max_load_factor.

Q: rehash 가 뭔가요?

unordered_map 의 load_factor (size / bucket_count) 가 임계값 초과 시:
  1) 더 큰 버킷 배열 할당 (보통 2배)
  2) 모든 원소를 새 해시값으로 재배치
  3) 기존 버킷 배열 해제

비용 O(n) — 13번 vector 재할당과 동일한 패턴.
모든 iterator·포인터·참조 무효화 — 댕글링 위험.
회피: u.reserve(n) 으로 미리 버킷 확보.

map 은 이런 일이 없음 — 노드 안정성이 결정적 차이.

Q: lower_bound 와 upper_bound 차이?

lower_bound(k) — k 이상인 첫 원소의 iterator
upper_bound(k) — k 초과인 첫 원소의 iterator
equal_range(k) — [lower, upper) 쌍 반환

예: m = {1, 3, 5, 7}
  lower_bound(3) → 3
  upper_bound(3) → 5
  lower_bound(4) → 5
  upper_bound(4) → 5
  → equal_range(3) = [3, 5), equal_range(4) = [5, 5) (빈 범위)

해시맵에는 없는 강력한 연산 — 정렬 컨테이너의 정직한 강점.

Q: vector 의 iterator 무효화와 어떤 차이? (★ 13번 회귀)

vector — 재할당 시 모든 iterator/포인터/참조 무효
         insert/erase 시 위치 이후 무효
map    — 삽입은 무효화 없음 (★)
         삭제는 삭제된 노드만 무효

13번에서 본 list 의 노드 안정성과 동일 — 분산 노드 자료구조의 공통 강점.
이 차이로 map 은 외부에 iterator 를 저장해 두는 패턴이 안전함.

Q: operator[] 가 const map 에서 못 쓰는 이유?

operator[](k) 는 키가 없으면 default(T) 를 자동 삽입.
즉 mutating 연산이라 const 객체에서는 호출 불가.

const map 에서는 at(k) 사용 — 없으면 std::out_of_range 예외.
또는 find(k) 로 iterator 받고 != end() 체크.

이 함정 때문에 가능하면 operator[] 보다 try_emplace / find / at 권장.

Q: TMap 은 std::map 인가요?

아닙니다 — TMap 은 해시 기반으로 std::unordered_map 에 더 가까워요.

std::map (RB-Tree) 에 직접 대응하는 1급 컨테이너는 없고,
정렬이 필요하면 TSortedMap 을 사용. 단 TSortedMap 도 RB-Tree 가 아닌
정렬된 TArray 기반 — 작은 N 에서 캐시 친화적.

언리얼이 RB-Tree 를 1급으로 두지 않은 이유는 게임 엔진 특성상
캐시 친화성이 우선이라 트리 노드 분산을 피하려는 의도.

Q: try_emplace 가 emplace 와 다른 점?

emplace(k, args...) — 항상 노드 생성 시도, 키 있으면 무시되지만
                       args 로 만든 임시 객체는 이미 생성됨

try_emplace(k, args...) (C++17) — 키 있으면 args 자체를 만들지 않음
                                  무브-온리 타입(unique_ptr 등) 에서 특히 유용

operator[] 의 default 삽입 트랩 회피 + emplace 의 임시 객체 트랩 회피
→ "있으면 그대로, 없을 때만 삽입" 의도를 가장 명확하게 표현.

---

12. 모의면접 답변 템플릿 (1분 / 3분)

12-1. 1분 버전 — 핵심만

std::map 은 키-값 쌍을 키 기준으로 자동 정렬해 저장하는 연관 컨테이너로,
내부적으로 Red-Black Tree (자기 균형 BST) 를 사용합니다. 그래서
insert / erase / find 모두 O(log n) 최악 보장입니다.

Red-Black Tree 는 노드에 빨강·검정 색깔을 부여하고 5가지 속성으로
트리 높이를 O(log n) 으로 유지합니다. 핵심은 빨강 노드가 연속으로
나올 수 없다는 것과 모든 NIL 까지의 경로의 검정 노드 수가 동일해야
한다는 것이고, 삽입·삭제 시 회전과 재색칠로 이 속성을 복구합니다.

비슷한 영역의 unordered_map 은 해시 테이블 기반으로 평균 O(1)
이지만 정렬이 안 되고 최악은 O(n) 입니다. 따라서 정렬·범위 조회·
최악 시간 보장이 필요하면 map, 순서 무관 + 최대 처리량이 중요하면
unordered_map 을 선택합니다.

iterator 무효화 면에서도 map 은 list 와 같은 노드 안정성을 가져
삽입은 무효화가 전혀 없고 삭제도 삭제된 노드만 무효화됩니다.
이게 vector 의 재할당 무효화와 정반대 트레이드오프입니다.

12-2. 3분 버전 — RB-Tree·unordered·언리얼까지

[1] std::map 은 정렬된 연관 컨테이너입니다.

키-값 쌍을 키 기준으로 자동 정렬해 저장하고 키 중복은 허용하지
않습니다. 내부 자료구조는 거의 모든 표준 라이브러리 구현에서
Red-Black Tree (자기 균형 BST) 입니다. 시그니처는
std::map<Key, T, Compare, Allocator> 이고, 정렬 기준은 기본적으로
std::less<Key> 입니다.

원소 타입이 std::pair<const Key, T> 라는 점이 특징인데, 키가
const 인 이유는 변경하면 트리 정렬 순서가 깨지기 때문입니다.
값만 수정 가능합니다.

[2] 핵심은 Red-Black Tree 의 5가지 속성입니다.

1) 모든 노드는 빨강 또는 검정
2) 루트는 항상 검정
3) 모든 NIL 노드 (리프) 는 검정
4) 빨강 노드의 자식은 반드시 검정 — 즉 빨강 연속 금지
5) 임의 노드에서 후손 NIL 까지의 경로마다 검정 노드 수가 동일 —
   이걸 black height 라고 부릅니다

이 속성들이 트리 높이를 최악 2 log(n+1) 로 제한해 모든 핵심 연산이
O(log n) 보장됩니다. 삽입·삭제 시 속성이 깨지면 회전과 재색칠로
복구하는데, 새 노드는 항상 빨강으로 삽입합니다 — 그래야 black height
가 변하지 않아 복구 비용이 최소화되거든요.

비슷한 자기 균형 BST 인 AVL 과 비교하면, AVL 은 더 엄격한 균형으로
검색이 약간 빠르지만 회전 횟수가 많아 갱신이 느립니다. RB 는 느슨한
균형 대신 회전이 적어 삽입·삭제 위주에서 유리합니다. STL 은 일반
목적이라 RB 를 채택했습니다.

[3] unordered_map 과의 비교가 가장 자주 나옵니다.

unordered_map 은 해시 테이블 기반으로 평균 O(1) 이지만 최악은
O(n) 입니다 (해시 충돌). 정렬이 안 되고, lower_bound 같은 범위 조회도
지원하지 않습니다. 메모리 오버헤드도 버킷 배열 + 체이닝 노드로
더 큽니다.

선택 기준은 명확합니다. 키 정렬이 필요하거나, 범위 조회를 해야 하거나,
최악 시간 보장이 필요한 시스템이면 map. 순서 무관에 최대 처리량이
필요하면 unordered_map. 게임 엔진 같은 환경에서는 거의 항상
unordered_map 입니다.

또 하나 중요한 차이가 iterator 무효화입니다. unordered_map 은 rehash
시 모든 iterator·포인터·참조가 무효화되는데, 이게 vector 재할당과
같은 패턴입니다. map 은 노드 안정성이 강해서 삽입은 무효화가 전혀
없고 삭제도 삭제된 노드만 무효화됩니다 — list 와 같은 강점입니다.

[4] operator[] 함정과 C++17 개선.

operator[] 는 키가 없으면 default 값을 자동 삽입하는 mutating
연산이라 const map 에서는 컴파일 에러가 납니다. 또 무브-온리 타입에서
"있으면 그대로 두고 없을 때만 삽입" 같은 의도를 표현하기 까다롭습니다.

C++17 의 try_emplace 와 insert_or_assign 이 이 문제를 해결합니다.
try_emplace 는 키가 이미 있으면 인자조차 만들지 않아 unique_ptr
같은 무브-온리 타입에서 안전합니다. insert_or_assign 은 "있으면 대입,
없으면 삽입" 의도를 명확히 표현합니다.

[5] 언리얼.

언리얼의 TMap 은 std::unordered_map 에 가까운 해시 기반입니다.
std::map 에 직접 대응하는 RB-Tree 컨테이너는 1급으로 두지 않았고,
정렬이 필요하면 TSortedMap 을 쓰는데, 이것도 RB-Tree 가 아닌 정렬된
TArray 기반입니다.

이유는 13번에서 본 vector vs list 와 같은 캐시 친화 철학입니다.
게임 엔진은 매 프레임 수만 객체를 순회하므로 트리 노드 분산보다
연속 배열 + 이진 탐색이 캐시상 더 빠를 때가 많아서, 1급 시민은
TArray (vector) + TMap·TSet (해시) 만 두고 트리 컨테이너는
보조적으로만 둔 겁니다.

요약하면 — map 은 정렬·범위·최악 보장이 필요할 때, unordered_map 은
빠른 조회가 필요할 때, 그리고 게임 엔진에서는 캐시 친화성을 위해
양쪽 다 신중하게 선택해야 한다 — 가 14번의 핵심입니다.

---

참고

• 13_vector_vs_list.md — 시퀀스 컨테이너의 메모리 레이아웃·CPU 캐시 분석. map 의 노드 안정성은 list 와 동일한 패턴, unordered_map rehash 무효화는 vector 재할당과 동일한 패턴
• 11_smart_pointer.md — map<Key, unique_ptr<T>> + try_emplace (C++17) 패턴. 무브-온리 타입을 연관 컨테이너에 안전하게 담기
• 12_prevent_copy.md — Rule of Five, move-only 타입. map 은 노드 안정성으로 vector 만큼 noexcept move 의존도가 낮음
• 10_pointer_deepdive.md — unordered_map rehash 후 댕글링 포인터 (vector 재할당과 동일 패턴)
• 09_rtti_raii.md — map + 스마트 포인터 합성 RAII
• 00_index.md — CS 면접 인덱스