map / unordered_map

map이란?

Map은 Key와 Value를 하나의 쌍(pair)으로 묶어서 저장하는 연관 컨테이너(Associative Container)입니다. Key 값을 이용해 Value에 빠르게 접근(검색, 삽입, 삭제)하는 것을 목적으로 합니다.

 

주요 특징은 다음과 같습니다.

• Key-Value 쌍 : 모든 데이터는 Key와 그에 해당하는 Value로 구성됩니다.
• 고유한 Key : Key 값은 중복될 수 없습니다. 만약 중복된 Key로 새로운 값을 추가하면, 기존의 Value가 덮어씌워집니다.
• 빠른 검색 속도 : Key를 기반으로 데이터를 검색하기 때문에 매우 빠른 시간 복잡도를 가집니다. 일반적으로 O(log N) 또는 O(1)의 시간 복잡도를 보입니다.

 

C++과 C#에서의 Map

C++

C++ 표준 라이브러리(STL)에서는 Map을 크게 두 가지로 제공합니다.

 

map

• 기반 자료구조 : 레드-블랙 트리 (Red-Black Tree)
• 특징:
  • Key를 기준으로 자동으로 오름차순 정렬됩니다.
  • 데이터를 삽입, 삭제, 검색할 때 O(log N)의 시간 복잡도를 가집니다.
• 언제 사용하는가? : Key-Value 데이터를 저장하면서, 데이터의 정렬 상태를 유지해야 할 때 유용합니다. 예를 들어, 랭킹 시스템처럼 순위(Key)에 따라 유저 정보(Value)를 정렬된 상태로 관리해야 할 때 적합합니다.

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() 
{
    map<string, int> playerScores;

    // 데이터 삽입
    playerScores["PlayerA"] = 100;
    playerScores["PlayerC"] = 150;
    playerScores["PlayerB"] = 120;

    // ※ Key를 기준으로 자동 정렬되어 출력됨 (PlayerA, PlayerB, PlayerC 순)
    for (const auto& pair : playerScores) 
    {
        cout << pair.first << ": " << pair.second << endl;
    }

    // 데이터 검색
    if (playerScores.find("PlayerA") != playerScores.end()) 
    {
        cout << "PlayerA score: " << playerScores["PlayerA"] << endl;
    }

    return 0;
}

 

unordered_map

• 기반 자료구조 : 해시 테이블 (Hash Table)
• 특징:
  • 데이터가 정렬되지 않습니다. 내부적으로 해시 함수를 통해 Key를 관리합니다.
  • 데이터를 삽입, 삭제, 검색할 때 평균적으로 O(1)의 매우 빠른 시간 복잡도를 가집니다. (최악의 경우 O(N))
• 언제 사용하는가? : 데이터의 정렬이 필요 없고, 최대한 빠른 검색, 삽입, 삭제가 필요할 때 사용합니다. 대부분의 경우 map보다 성능이 좋습니다. 게임에서 몬스터의 고유 ID(Key)를 통해 몬스터 객체(Value)를 관리하는 경우처럼, 순서와 상관없이 빠른 접근이 중요할 때 적합합니다.

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() 
{
    unordered_map<string, int> itemStock;

    // 데이터 삽입
    itemStock["HP Potion"] = 50;
    itemStock["MP Potion"] = 30;
    itemStock["Sword"]     = 1;

    // ※ 정렬되지 않은 상태로 출력됨
    for (const auto& pair : itemStock) 
    {
        cout << pair.first << ": " << pair.second << endl;
    }

    // 데이터 검색 (매우 빠름)
    if (itemStock.count("Sword")) 
    {
       cout << "Sword stock: " << itemStock["Sword"] << endl;
    }

    return 0;
}

 

2. C#

C#에서는 Dictionary가 C++의 unordered_map과 유사한 역할을 하며, 가장 일반적으로 사용됩니다.

 

Dictionary<TKey, TValue>

• 기반 자료구조 : 해시 테이블 (Hash Table)
• 특징:
  • C++의 unordered_map과 거의 동일합니다.
  • 데이터는 정렬되지 않습니다.
  • 삽입, 삭제, 검색 시 평균 O(1)의 시간 복잡도를 가집니다.
• 언제 사용하는가? : C++의 unordered_map과 마찬가지로, 순서에 상관없이 Key-Value 데이터를 매우 빠르게 관리하고 싶을 때 사용합니다. C#에서 Key-Value 쌍을 다룰 때 가장 먼저 고려되는 자료구조입니다.

using System;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        // Dictionary 선언
        Dictionary<string, int> characterLevels = new Dictionary<string, int>();

        // 데이터 추가
        characterLevels.Add("Warrior", 50);
        characterLevels.Add("Mage"   , 60);
        characterLevels.Add("Archer" , 55);

        // ※ 정렬되지 않은 상태로 출력됨
        foreach (var pair in characterLevels)
        {
            Console.WriteLine($"{pair.Key}: {pair.Value}");
        }

        // 데이터 검색
        if (characterLevels.ContainsKey("Mage"))
        {
            Console.WriteLine($"Mage's level: {characterLevels["Mage"]}");
        }
    }
}

참고 : C#에서 정렬된 Map이 필요하다면 SortedDictionary<TKey, TValue>를 사용할 수 있습니다. 이는 C++의 map과 같이 레드-블랙 트리로 구현되어 있으며, Key를 기준으로 자동 정렬됩니다.