std::map

std::map은 C++ 표준 라이브러리에서 제공하는 핵심적인 연관 컨테이너(associative container) 중 하나다.
키(Key)와 값(Value)을 쌍으로 묶어 저장하며, 키를 기반으로 값을 효율적으로 검색, 삽입, 삭제할 수 있게 해준다.

1. 이론

1.1. std::map의 개념과 특징

std::map은 데이터를 키-값(Key-Value) 쌍으로 저장한다. 사전에서 단어(키)를 찾아 뜻(값)을 찾는 것과 유사하다.

주요 특징은 다음과 같다.

• 고유한 키: std::map 내의 모든 키는 유일해야 한다. 중복된 키를 허용하지 않는다.
• 자동 정렬: 삽입되는 모든 원소는 키를 기준으로 자동 정렬된다. 기본적으로는 오름차순(std::less)으로 정렬되며, 사용자가 정렬 기준을 직접 지정할 수도 있다.
• 연관 컨테이너: 배열처럼 인덱스를 통해 원소에 접근하는 것이 아니라, 키를 통해 값에 접근한다.

1.2. 내부 구현과 계층 구조 (Red-Black Tree)

std::map은 일반적으로 레드-블랙 트리(Red-Black Tree)라는 자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)로 구현된다.

레드-블랙 트리의 5가지 규칙

1. 모든 노드는 레드(Red) 또는 블랙(Black) 색상을 가진다.
2. 루트 노드는 항상 블랙이다.
3. 모든 리프 노드(NIL, nullptr)는 블랙이다.
4. 레드 노드의 자식은 반드시 블랙이다. (즉, 레드 노드가 연속으로 나타날 수 없다.)
5. 임의의 노드에서부터 그 자손인 리프 노드에 이르는 모든 경로에는 동일한 개수의 블랙 노드가 존재한다.

이 규칙들 덕분에 트리는 항상 유사 균형(Approximately Balanced) 상태를 유지한다. 트리의 높이가 O(log N) (N은 노드의 개수)으로 유지되므로, 검색, 삽입, 삭제 연산의 시간 복잡도가 O(log N)임을 보장할 수 있다.

동작 계층 구조

1. 사용자 영역 (User Code): my_map[key] = value;와 같은 코드를 작성.
2. C++ 표준 라이브러리 (<map>):
   • operator[] 호출 시, std::map 내부의 레드-블랙 트리에서 key를 탐색.
   • 키 존재 시: 해당 노드의 값(value)에 대한 참조를 반환.
   • 키 부재 시:
     • 새로운 (키, 기본값) 쌍으로 노드를 생성.
     • std::allocator를 사용해 힙(Heap) 메모리에 노드를 할당.
     • 레드-블랙 트리의 규칙에 맞게 트리를 재조정(회전, 색상 변경)하여 균형을 맞춤.
     • 새로 생성된 값에 대한 참조를 반환.
3. C 런타임 라이브러리 (CRT): std::allocator는 내부적으로 new 연산자를 호출하고, 이는 다시 malloc()과 같은 저수준 메모리 할당 함수를 호출한다. CRT는 자체적인 메모리 풀을 관리하며 효율적인 할당을 시도한다.
4. 운영체제 (OS Kernel): CRT의 메모리 풀이 부족해지면, 운영체제에 시스템 콜(System Call, 예: Windows의 VirtualAlloc, Linux의 brk 또는 mmap)을 통해 추가적인 메모리 페이지를 요청한다. 커널은 물리 메모리를 프로세스의 가상 주소 공간에 매핑해준다.
5. 하드웨어 (MMU): CPU의 메모리 관리 장치(MMU)가 가상 주소를 실제 물리 주소로 변환하여 최종적으로 메모리에 접근한다.

1.3. std::map vs std::unordered_map

특징	std::map	std::unordered_map
내부 구현	레드-블랙 트리 (자가 균형 이진 탐색 트리)	해시 테이블 (Hash Table)
정렬	키에 따라 자동 정렬됨	정렬되지 않음 (무작위 순서)
시간 복잡도	검색, 삽입, 삭제: O(log N)	검색, 삽입, 삭제: 평균 O(1), 최악 O(N)
메모리 사용	노드마다 포인터(부모, 자식)를 저장하므로 추가 오버헤드 발생	해시 테이블 구조로 인해 더 많은 메모리를 사용할 수 있음
주요 사용처	- 데이터의 정렬된 순회가 필요할 때 - 범위 기반 검색(lower_bound, upper_bound)이 필요할 때 - 예측 가능한 성능이 중요할 때	- 가장 빠른 평균 속도로 데이터를 조회해야 할 때 - 데이터의 순서가 중요하지 않을 때 - 캐싱(Caching) 구현 등

언제 무엇을 사용해야 할까?

• std::map: 아이템 ID, 몬스터 ID 순으로 정렬된 목록을 출력해야 하거나, 특정 점수 범위 내의 플레이어를 찾는 등 순서가 중요하고 범위 검색이 필요할 때 적합하다.
• std::unordered_map: 캐릭터의 스킬 쿨타임을 ID로 빠르게 조회하거나, 리소스 파일 경로를 이름으로 즉시 찾아 로드하는 등 순서와 상관없이 최대한 빠른 접근이 필요할 때 좋다.

2. 실습 코드 (게임 인벤토리 관리)

다음은 std::map을 사용하여 게임 캐릭터의 인벤토리를 관리하는 예제다. 아이템의 고유 ID를 키로, 아이템의 수량을 값으로 관리한다. 또한, 아이템의 상세 정보는 별도의 std::map으로 관리하여 데이터베이스처럼 활용한다.

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

// 아이템의 상세 정보를 담는 구조체
struct Item {
    std::string name;
    std::string description;
    int value;
};

// 게임 캐릭터의 인벤토리를 관리하는 클래스
class Inventory {
public:
    // 아이템 데이터베이스에 아이템 원본 정보를 추가하는 함수
    void RegisterItem(int itemID, const std::string& name, const std::string& desc, int value) {
        // 아이템 정보를 생성하여 데이터베이스 맵에 저장
        item_database_[itemID] = {name, desc, value};
    }

    // 인벤토리에 아이템을 추가하는 함수
    void AddItem(int itemID, int quantity = 1) {
        // Q1: 먼저 item_database_.count(itemID)로 아이템이 등록된 정보인지 확인하는 이유는 무엇일까요?
        // 만약 이 확인 절차를 생략한다면 어떤 문제가 발생할 수 있을까요?
        // A. 등록되지 않은 ID를 인벤토리에 넣으려고 하면, 존재하지 않는 아이템을
        // 참조하게 되기 때문.
        // 잘못된 ID로 접근 시 예외 발생
        if (item_database_.count(itemID) == 0) {
            std::cout << "[에러] 등록되지 않은 아이템 ID: " << itemID << std::endl;
            return;
        }

        // Q2: 'item_counts_[itemID] += quantity;' 코드는 맵에 해당 itemID가 없을 때 어떻게 동작할까요?
        // 이 동작이 std::map의 어떤 특징 때문에 가능한지 설명해보세요.
        // A. 기본 값을 넣어준다. int이기 때문에 0이 들어가고 += quantity가 실행됨.
        // std::map의 operator[]가 자동 삽입을 제공해서 가능하다.
        item_counts_[itemID] += quantity;
        std::cout << "'" << item_database_.at(itemID).name << "' " << quantity << "개를 획득했습니다." << std::endl;
    }

    // 인벤토리에서 아이템을 사용하는 함수
    void UseItem(int itemID, int quantity = 1) {
        auto it = item_counts_.find(itemID);

        // Q3: 여기서 'find' 함수를 사용한 결과를 'end()'와 비교하는 이유는 무엇인가요?
        // 'operator[]'나 'at()'을 바로 사용하지 않는 이유는 무엇일까요?
        // A. 키가 없으면 find는 end() 반복자를 반환한다.
        // operator[]를 사용하면 자동 삽입으로 원하지 않는 아이템이 생기고, at()은
        // 없는 키를 조회할 시 'out_of_range' 예외를 발생시킨다.
        if (it != item_counts_.end()) {
            if (it->second >= quantity) {
                it->second -= quantity;
                std::cout << "'" << item_database_.at(itemID).name << "' " << quantity << "개를 사용했습니다." << std::endl;
                
                // 아이템을 모두 사용했다면 인벤토리에서 제거
                if (it->second == 0) {
                    // Q4: 'erase(it)'를 사용하는 것과 'erase(itemID)'를 사용하는 것의 성능상 차이가 있을까요?
                    // 왜 여기서는 반복자(it)를 사용한 버전이 더 효율적일까요?
                    // A. it을 사용하면 검색 과정을 생략하고 바로 삭제가 가능하다.
                    item_counts_.erase(it);
                    std::cout << "'" << item_database_.at(itemID).name << "'을(를) 모두 소진했습니다." << std::endl;
                }
            } else {
                std::cout << "[부족] '" << item_database_.at(itemID).name << "'의 수량이 부족합니다." << std::endl;
            }
        } else {
            std::cout << "[없음] 인벤토리에 해당 아이템이 없습니다." << std::endl;
        }
    }

    // 인벤토리 전체를 출력하는 함수
    void PrintInventory() const {
        std::cout << "--- 인벤토리 ---" << std::endl;
        if (item_counts_.empty()) {
            std::cout << "비어있음" << std::endl;
        } else {
            // Q5: 이 반복문은 왜 항상 아이템 ID 순서대로 인벤토리를 출력할까요?
            // std::map의 어떤 내부 구조적 특징 때문인지 설명해보세요.
            // A. 내부적으로 레드 블랙 트리를 사용한다. 그래서 키를 삽입할 때 자동
            // 으로 정렬 상태를 유지한다.
            for (const auto& pair : item_counts_) {
                int itemID = pair.first;
                int quantity = pair.second;
                
                // 아이템 데이터베이스에서 아이템 정보를 가져옴
                const Item& item = item_database_.at(itemID);
                
                std::cout << "  ID: " << itemID << " | 이름: " << item.name
                          << " | 수량: " << quantity << " | 설명: " << item.description << std::endl;
            }
        }
        std::cout << "----------------" << std::endl;
    }

private:
    // 아이템의 원본 정보를 저장하는 맵 (ID -> Item 정보), 일종의 게임 데이터베이스 역할
    std::map<int, Item> item_database_;
    // 캐릭터가 소유한 아이템의 수량을 저장하는 맵 (ID -> 수량)
    std::map<int, int> item_counts_;
};

int main() {
    // 인벤토리 시스템 생성
    Inventory myInventory;

    // 게임에 존재하는 아이템들을 미리 등록
    myInventory.RegisterItem(101, "체력 물약", "체력을 50 회복시켜준다.", 20);
    myInventory.RegisterItem(102, "마나 물약", "마나를 30 회복시켜준다.", 25);
    myInventory.RegisterItem(201, "강철 검", "기본적인 공격을 할 수 있는 검.", 150);
    myInventory.RegisterItem(301, "가죽 방패", "공격을 방어할 수 있는 방패.", 100);

    // 게임 플레이: 아이템 획득
    myInventory.AddItem(101, 5);  // 체력 물약 5개 획득
    myInventory.AddItem(201);     // 강철 검 1개 획득
    myInventory.AddItem(101, 3);  // 체력 물약 3개 추가 획득
    myInventory.AddItem(999);     // 등록되지 않은 아이템 획득 시도

    myInventory.PrintInventory();

    // 게임 플레이: 아이템 사용
    myInventory.UseItem(101, 2);  // 체력 물약 2개 사용
    myInventory.UseItem(201, 2);  // 강철 검 2개 사용 시도 (수량 부족)
    myInventory.UseItem(102);     // 마나 물약 사용 시도 (인벤토리에 없음)

    myInventory.PrintInventory();

    // 게임 플레이: 아이템 모두 사용
    myInventory.UseItem(101, 6);  // 남은 체력 물약 6개 모두 사용

    myInventory.PrintInventory();

    return 0;
}

3. 요약

std::map은 키(Key)와 값(Value)을 하나의 쌍으로 묶어서 저장하는 C++의 연관 컨테이너입니다.

가장 큰 특징은 키를 기준으로 항상 자동으로 정렬된다는 점입니다. 내부적으로는 '레드-블랙 트리'라는 균형 잡힌 이진 탐색 트리로 구현되어 있어서, 데이터가 얼마나 많든 상관없이 검색, 삽입, 삭제 연산을 O(log N)의 안정적인 시간 복잡도로 수행할 수 있습니다.

std::unordered_map과 비교하자면, unordered_map은 해시 테이블을 사용해서 평균 O(1)의 매우 빠른 조회가 가능하지만 순서를 보장하지 않습니다.

반면 std::map은 unordered_map보다 약간 느릴 순 있어도, 데이터를 항상 정렬된 상태로 유지해야 하거나 특정 범위의 데이터를 찾아야 할 때 매우 유용합니다.

예를 들어, 게임에서 아이템 ID 순서대로 인벤토리를 보여주거나, 점수 랭킹 보드를 관리하는 것처럼 데이터의 순서가 중요할 때 std::map을 사용하는 것이 좋습니다.