std::map

std::map

• 키 - 값 (Key - Value) 쌍을 저장하는 컨테이너
  (내부 원소 타입은 pair<>)
  
  • 일반적으로 ‘유일 키’ 방식
    
• 정렬된 상태 유지
  
  • 내부적으로 Red-Black Tree를 기반으로 하기에
    균형 이진 탐색 트리를 지향
    

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

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

    // 삽입 1: operator[]
    scores["Alice"] = 90;    // 존재하지 않으면 새 노드 생성 후 90 대입
    scores["Bob"]   = 80;

    // 삽입 2: insert
    scores.insert(std::make_pair("Charlie", 85));
    scores.insert({"Dave", 95});

    // 값 접근
    std::cout << "Alice: " << scores["Alice"] << '\n';

    // 키 존재 여부는 find 사용 (operator[]는 없으면 생성해버림!)
    if (auto it = scores.find("Eve"); it != scores.end())
    {
        std::cout << "Eve: " << it->second << '\n';
    }
    else
    {
        std::cout << "Eve not found\n";
    }

    // 정렬된 순서로 순회
    for (const auto& [name, score] : scores)
    {
        std::cout << name << " : " << score << '\n';
    }

    return 0;
}

• 각 원소가 ‘독립적인 노드’로 할당 (포인터 기반으로 연결)
  
  • 그렇기에 데이터가 ‘연속적’이지 않음
    
  • Iterator 역시 포인터 개념이기에
    이전에 보았던 std::list 처럼
    원소 삽입/삭제 상황에서도 Iterator가
    비교적 안정적임
    
• Key 순서대로 원소가 정렬되기에
  begin()->end() 순회시 오름차순으로 순회함
  
  • 그렇기에 map에 집어넣는 key 값은
    ‘비교 연산자’ 등이 구현되어 있어야 함
    

Red-Black Tree (RB Tree)

• RB Tree는 균형 이진 탐색 트리의 한 종류
  

• 다음과 같은 규칙을 기반으로
  Tree의 높이를 항상 일정하게 유지함
  

1. 각 노드는 빨간(red) 또는 검은(black) 색을 가진다.

2. 루트 노드는 항상 검은색이다.

3. 리프(NIL) 노드는 검은색으로 간주한다.
(일반적으로 nullptr 대신 검은색 NIL 노드를 상정)

4. 빨간 노드의 자식은 항상 검은색이다.
→ 빨간 노드가 연속해서 나올 수 없음 (red-red 금지).

5. 어떤 노드에서 리프(NIL)까지 가는 모든 경로에 대해,
   지나가는 검은 노드의 개수는 모두 같다.
   → “black height”가 일정.

비슷한 BST(Binary Search Tree) 중 비슷하게 자동 정렬을 하는 것은
AVL Tree가 존재함

AVL Tree

AVL Tree?

• 모든 노드에서 자신의 ‘왼쪽 자식 트리’와
  ‘오른쪽 자식 트리’의 높이의 차가 1 이하여야 하는 트리
  
  • Balanced Factor라는 수치를 사용하여
    각 노드의 값을 {-1,0,1}로 조정
    
• 균형을 맞추기 위하여
  ‘Tree’를 ‘회전’시키는 방법을 사용함
  
  • 특정한 노드를 기준으로 회전시킨다면
    자신의 ‘자식’을 부모로 삼으며
    그 과정에서 부모를 가리키는 포인터 등을 조정
    
  • 균형이 깨짐에 따라
    LL,RR,LR,RL 별로 회전을 적용
    

RB Tree와의 비교표

비교 항목	AVL Tree	Red-Black Tree (std::map)
균형 기준	엄격함 (높이 차이 1 이하)	느슨함 (경로 길이 차이 2배 이하)
탐색 속도	더 빠름 (트리가 더 얕음)	빠름 (AVL보단 미세하게 느림)
삽입/삭제 속도	느림 (Rebalancing 자주 발생)	더 빠름 (회전 빈도 낮음)
메모리 사용	각 노드에 정수형 높이(Height) 저장	각 노드에 1비트 색상(Color) 저장
주요 용도	검색이 압도적으로 많은 데이터베이스	삽입/삭제/검색이 골고루 일어나는 범용 컨테이너 (C++ Map)

std::unordred_map ?

• map과 비슷하게 key-value 쌍을 가지는 자료구조
  (역시 내부 원소 타입은 pair<>)
  

• Hash Table을 기반으로 하는 자료구조이며
  map과는 다르게 ‘정렬하지 않음’(unordered!)
  (Hash Table?)
  

• 삽입/삭제/접근이 O(1)!
  
  • 다만 ‘해시 충돌’이 나지 않았을 때의 이야기!
    
  • 충돌이 발생하는 경우 Chaining 방식을 채택하여 해결
    (다만, 충돌이 발생하면 점점 성능이 저하되므로 주의가 필요)
    

• bucket count라는 내부 요소가 존재하며
  현재 Size가 이를 초과하게 되면
  ‘rehash’가 발생하게 되어
  iterator가 무효화되므로 주의가 필요!
  (reserve 함수를 호출하여 bucket count 초기 설정이 가능함)
  

• rehash 발생 시, bucket count를 늘리고
  모든 요소를 전부 ‘해싱’처리를 다시 하게 됨
  
  • (hash(특정 키)) / bucket count -> 방 배정
    
  • 모든 요소를 해싱하기에 O(N) 이상의 시간 복잡도 소요
    
  • reserve를 습관화 하자…
    

#include <iostream>
#include <unordered_map>

int main()
{
    std::unordered_map<std::string, int> scores;

    scores["Alice"] = 100;
    scores["Bob"] = 80;

    scores.insert({"Charlie", 90});

    // fast lookup
    if (auto it = scores.find("Alice"); it != scores.end())
    {
        std::cout << it->first << " : " << it->second << '\n';
    }

    // 순서는 무작위
    for (auto& [name, score] : scores)
    {
        std::cout << name << " : " << score << '\n';
    }
}

unordered_map vs TMap(Unreal)?

• TMap은 unordered_map과 유사하게
  Hash 기반임
  
  • 둘 다 정렬은 안됨!
    
• 다만 게임에 특화되어 있기에
  노드별 할당이 아닌 ‘배열’ 기반의
  ‘연속적’인 할당을 통해 ‘캐시 히트율’을 높임!
  
  • Unreal GC 의 관리를 받음
    

요약 표

특징	std::unordered_map (STL)	TMap (Unreal Engine)
자료구조	Hash Table	Hash Table (Sparse Array 기반)
정렬 여부	정렬 안 됨	정렬 안 됨 (Key 순서 보장 X)
충돌 처리	Chaining (연결 리스트)	Open Addressing 유사 (데이터 연속 저장)
메모리 효율	낮음 (노드마다 포인터 오버헤드 + 파편화)	높음 (연속된 메모리 사용)
속도 (Iteration)	느림 (포인터 타고 이동)	빠름 (배열 순회와 동일)
Key 요구사항	std::hash, operator==	GetTypeHash, operator==
GC 연동	불가능	UPROPERTY 지정 시 GC 대상 관리 가능