C++ 초급 - 11. 표준 라이브러리(STL) (2 - std::map, std::unordered_map (연관 컨테이너))

📌 11.2 std::map, std::unordered_map (연관 컨테이너)

C++에서는 연관 컨테이너(Associative Container)를 사용하여 키-값 쌍을 저장하고 효율적으로 검색할 수 있다.
대표적인 연관 컨테이너로 std::map과 std::unordered_map이 있으며, 각각 이진 검색 트리 기반(정렬 저장)과 해시 기반(빠른 검색)의 차이가 있다.

---

📌 1. std::map (정렬된 키-값 쌍 저장)

🔹 (1) std::map이란?

• 키(Key)에 대해 자동으로 정렬되는 연관 컨테이너.
• 내부적으로 이진 검색 트리(Red-Black Tree)를 사용하여 데이터를 저장.
• 시간 복잡도: 삽입, 삭제, 검색 연산이 O(log N).
• 중복된 키를 허용하지 않음 (std::multimap은 중복 허용).

💡 기본 문법

#include <map>

std::map<int, std::string> myMap;  // 키: int, 값: string

💡 예제: std::map 기본 사용법

#include <iostream>
#include <map>

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

    myMap[1] = "Apple";
    myMap[3] = "Banana";
    myMap[2] = "Cherry";

    std::cout << "키 2의 값: " << myMap[2] << std::endl;

    // 자동 정렬된 출력
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

🔹 출력 결과

키 2의 값: Cherry
1: Apple
2: Cherry
3: Banana

💡 설명

• std::map은 키를 자동으로 정렬 (1 → 2 → 3 순서로 저장됨).
• myMap[2]는 해당 키의 값을 반환.

---

📌 2. std::unordered_map (해시 기반 빠른 검색)

🔹 (1) std::unordered_map이란?

• 해시 테이블(Hash Table)을 기반으로 동작하는 연관 컨테이너.
• 키의 정렬을 보장하지 않음.
• 시간 복잡도: 평균 O(1), 최악의 경우 O(N).
• 중복된 키를 허용하지 않음 (std::unordered_multimap은 중복 허용).

💡 기본 문법

#include <unordered_map>

std::unordered_map<int, std::string> myUnorderedMap;

💡 예제: std::unordered_map 기본 사용법

#include <iostream>
#include <unordered_map>

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

    myUnorderedMap[1] = "Apple";
    myUnorderedMap[3] = "Banana";
    myUnorderedMap[2] = "Cherry";

    std::cout << "키 2의 값: " << myUnorderedMap[2] << std::endl;

    // 무작위 순서로 출력
    for (const auto& pair : myUnorderedMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

🔹 출력 결과 (실행할 때마다 순서가 다를 수 있음)

키 2의 값: Cherry
3: Banana
1: Apple
2: Cherry

💡 설명

• 해시 테이블 기반이므로 O(1)의 빠른 검색이 가능.
• 입력 순서와 상관없이 무작위 순서로 저장됨.

---

📌 3. 삽입, 삭제, 탐색 (insert, erase, find)

🔹 (1) insert를 활용한 요소 추가

💡 예제: insert()를 사용한 요소 추가

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;
    
    myMap.insert({1, "Apple"});
    myMap.insert(std::make_pair(2, "Banana"));

    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

---

🔹 (2) erase를 활용한 요소 삭제

💡 예제: erase()를 사용한 요소 삭제

myMap.erase(1);  // 키 1 제거

---

🔹 (3) find를 활용한 탐색

💡 예제: find()를 사용한 요소 검색

auto it = myMap.find(2);
if (it != myMap.end()) {
    std::cout << "찾은 값: " << it->second << std::endl;
}

---

📌 4. std::map vs std::unordered_map 성능 차이

특징	std::map	std::unordered_map
구조	이진 검색 트리(Red-Black Tree)	해시 테이블(Hash Table)
정렬	자동 정렬 O	정렬되지 않음 X
삽입, 삭제, 검색	O(log N)	평균 O(1), 최악 O(N)
메모리 사용량	상대적으로 적음	상대적으로 많음
적합한 경우	정렬된 데이터를 유지해야 하는 경우	빠른 검색이 필요한 경우

💡 선택 기준

• 정렬된 데이터가 필요하면 std::map 사용.
• 빠른 검색이 필요하면 std::unordered_map 사용.

---

📌 5. 커스텀 비교 함수 및 해시 함수 적용 방법

🔹 (1) std::map에서 사용자 정의 비교 함수 사용

• 기본적으로 std::map은 operator<을 사용하여 정렬하지만, 사용자 정의 비교 함수를 사용할 수도 있다.

💡 예제: 내림차순 정렬

#include <iostream>
#include <map>

struct DescendingOrder {
    bool operator()(int a, int b) const {
        return a > b;  // 내림차순 정렬
    }
};

int main() {
    std::map<int, std::string, DescendingOrder> myMap;
    
    myMap[1] = "Apple";
    myMap[3] = "Banana";
    myMap[2] = "Cherry";

    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

🔹 출력 결과

3: Banana
2: Cherry
1: Apple

---

🔹 (2) std::unordered_map에서 사용자 정의 해시 함수 사용

• 기본적으로 std::unordered_map은 std::hash<T>를 사용하여 해싱하지만, 사용자 정의 해시 함수를 지정할 수도 있다.

💡 예제: 사용자 정의 해시 함수

#include <iostream>
#include <unordered_map>

struct CustomHash {
    size_t operator()(int x) const {
        return x % 10;  // 단순한 해시 함수
    }
};

int main() {
    std::unordered_map<int, std::string, CustomHash> myUnorderedMap;
    
    myUnorderedMap[1] = "Apple";
    myUnorderedMap[12] = "Banana";  // 같은 해시값을 가질 수 있음

    for (const auto& pair : myUnorderedMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

---

📌 6. 정리

개념	설명
std::map	키가 정렬된 상태로 저장되는 연관 컨테이너
std::unordered_map	해시 기반으로 저장되어 빠른 검색 가능
삽입, 삭제, 탐색	insert, erase, find 활용
성능 차이	std::map → O(log N), std::unordered_map → 평균 O(1)
커스텀 정렬 및 해시	std::map은 사용자 정의 비교 함수 가능, std::unordered_map은 사용자 정의 해시 가능