[C++] map / multimap / unordered_map / unordered_multimap

맵(map)

맵은 키-값 쌍을 저장하고 키를 기반으로 데이터를 검색하는 데 사용됩니다.
C++에서는 각 맵 타입의 동작 방식, 특징, 사용 목적에 따라 차이가 있습니다.
주요 map 타입들과 그 차이점을 정리하려 합니다.

---

1. std::map

• 특징:
  • 키-값 쌍을 저장하며 키를 기준으로 정렬된 상태를 유지.
  • 내부적으로 레드-블랙 트리를 사용.
  • 키는 중복 불가능.
  • 키의 정렬 기준은 기본적으로 오름차순이며, 사용자 정의 가능.
• 장점:
  • 정렬된 키 순서로 데이터를 순회 가능.
  • 키 검색, 삽입, 삭제가 O(log N).
• 단점:
  • 중복 키가 필요하면 사용할 수 없음.
  • 삽입/삭제 시 추가적인 정렬 비용 발생.
• 사용 예시:

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;
    myMap[1] = "One";
    myMap[3] = "Three";
    myMap[2] = "Two";

    for (const auto& [key, value] : myMap) {
        std::cout << key << ": " << value << '\n';
    }
    return 0;
}

---

2. std::multimap

• 특징:
  • 키-값 쌍을 저장하며 키를 기준으로 정렬된 상태를 유지.
  • 키는 중복 가능.
  • 내부적으로 레드-블랙 트리를 사용.
• 장점:
  • 중복 키를 지원하므로 동일한 키에 여러 값을 저장 가능.
  • 정렬된 키 순서로 데이터를 순회 가능.
• 단점:
  • 키 검색, 삽입, 삭제가 O(log N).
  • 삽입 후 값 변경이 어려움 (std::map처럼 operator[]가 없음).
• 사용 예시:

#include <iostream>
#include <map>

int main() {
    std::multimap<int, std::string> myMultimap;
    myMultimap.insert({1, "One"});
    myMultimap.insert({2, "Two"});
    myMultimap.insert({1, "Another One"});

    for (const auto& [key, value] : myMultimap) {
        std::cout << key << ": " << value << '\n';
    }
    return 0;
}

---

3. std::unordered_map

• 특징:
  • 키-값 쌍을 저장하며 정렬되지 않은 상태를 유지.
  • 내부적으로 해시 테이블을 사용.
  • 키는 중복 불가능.
• 장점:
  • 검색, 삽입, 삭제가 평균 O(1) (해시 충돌이 적을 경우).
  • 정렬이 필요 없는 경우 성능이 매우 우수.
• 단점:
  • 해시 충돌이 많으면 최악의 경우 O(N).
  • 키 순서가 없으므로 순회 시 순서가 보장되지 않음.
• 사용 예시:

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> myUnorderedMap;
    myUnorderedMap[1] = "One";
    myUnorderedMap[3] = "Three";
    myUnorderedMap[2] = "Two";

    for (const auto& [key, value] : myUnorderedMap) {
        std::cout << key << ": " << value << '\n';
    }
    return 0;
}

---

4. std::unordered_multimap

• 특징:
  • 키-값 쌍을 저장하며 정렬되지 않은 상태를 유지.
  • 키는 중복 가능.
  • 내부적으로 해시 테이블을 사용.
• 장점:
  • 중복 키를 지원하며, 검색, 삽입, 삭제가 평균 O(1).
  • 정렬이 필요 없는 경우 성능이 매우 우수.
• 단점:
  • 해시 충돌이 많으면 최악의 경우 O(N).
  • 키 순서가 없으므로 순회 시 순서가 보장되지 않음.
• 사용 예시:

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_multimap<int, std::string> myUnorderedMultimap;
    myUnorderedMultimap.insert({1, "One"});
    myUnorderedMultimap.insert({2, "Two"});
    myUnorderedMultimap.insert({1, "Another One"});

    for (const auto& [key, value] : myUnorderedMultimap) {
        std::cout << key << ": " << value << '\n';
    }
    return 0;
}

---

맵들의 비교 표

특징	map	multimap	unordered_map	unordered_multimap
정렬 여부	정렬됨 (키 기준)	정렬됨 (키 기준)	정렬되지 않음	정렬되지 않음
키 중복 허용	불가능	가능	불가능	가능
기본 구조	레드-블랙 트리	레드-블랙 트리	해시 테이블	해시 테이블
삽입/삭제/검색 시간	O(log N)	O(log N)	O(1) 평균, O(N) 최악	O(1) 평균, O(N) 최악
정렬된 순회 가능 여부	가능	가능	불가능	불가능

---

요약

• 정렬이 필요하고 키가 중복되지 않으면: std::map
• 정렬이 필요하고 키가 중복되면: std::multimap
• 정렬이 필요 없고 키가 중복되지 않으면: std::unordered_map
• 정렬이 필요 없고 키가 중복되면: std::unordered_multimap

각 상황에 따라 적합한 맵을 선택해 사용하면 됩니다. 😊