map

전체 코드

---

📌 1. std::map이란?

• 연관 컨테이너(Associative Container) 중 하나
• Key-Value(키-값) 형태로 데이터를 저장
• 내부적으로 균형 이진 탐색 트리(레드-블랙 트리) 구조로 관리됨
• 자동 정렬 기능 제공 (Key 기준 오름차순 정렬)
• 빠른 탐색, 삽입, 삭제 지원 (O(log n))
• Key 값은 중복 불가

---

📂 2. std::map의 주요 특징

✅ 1) std::vector vs. std::map 비교

비교 항목	std::vector	std::map
데이터 구조	동적 배열	균형 이진 트리 (Red-Black Tree)
삽입 속도	O(1) (끝에 추가 시)	O(log n)
삭제 속도	O(n) (중간 삭제 시 느림)	O(log n)
탐색 속도	O(n) (순차 탐색 필요)	O(log n) (트리 탐색)
정렬 여부	자동 정렬 X	자동 정렬 O
중복 키 허용	가능	불가능

✔ 벡터(vector)는 순차적인 데이터 저장에 적합
✔ 맵(map)은 키를 기반으로 한 빠른 탐색 및 정렬이 필요할 때 적합

---

📜 3. std::map 사용 예제 및 코드 분석

✅ 1) 기본적인 std::map 사용법

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

int main() {
    map<int, string> m;  // Key: int, Value: string

    // 데이터 삽입
    m.insert(make_pair(1, "Alice"));
    m.insert(pair<int, string>(2, "Bob"));
    m[3] = "Charlie";  // [] 연산자로 삽입 가능

    // 데이터 출력
    cout << "Key 1: " << m[1] << endl;
    cout << "Key 2: " << m[2] << endl;
    cout << "Key 3: " << m[3] << endl;

    return 0;
}

🔎 📌 분석

1. map<int, string> m; → 정수(Key)와 문자열(Value)를 저장하는 map 선언
2. insert(make_pair(1, "Alice")); → Key = 1, Value = "Alice" 추가
3. m[3] = "Charlie"; → [] 연산자로 값 추가 가능
4. cout << m[1]; → Key를 사용하여 Value를 조회 가능

📢 주의! [] 연산자를 사용하면 키가 없을 경우 자동으로 기본값이 추가됨

---

✅ 2) std::vector로 데이터 검색하는 문제점

#include <iostream>
#include <vector>
using namespace std;

class Player {
public:
    Player(int id) : _playerId(id) {}
public:
    int _playerId;
};

int main() {
    vector<Player*> players;

    // 100,000명의 플레이어 추가
    for (int i = 0; i < 100000; i++) {
        players.push_back(new Player(i));
    }

    // 특정 ID(10000)를 가진 플레이어 찾기
    bool found = false;
    for (int i = 0; i < players.size(); i++) {
        if (players[i]->_playerId == 10000) {
            found = true;
            break;
        }
    }
    cout << (found ? "찾음" : "못 찾음") << endl;

    return 0;
}

🔎 📌 문제점

1. 순차 탐색(O(n))이 필요 → 데이터가 많아질수록 속도 저하
2. 삭제 시 메모리 정리 문제 발생 → erase를 호출하면 데이터가 이동하여 성능 저하 발생

---

✅ 3) std::map으로 데이터 검색 최적화

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

class Player {
public:
    Player(int id) : _playerId(id) {}
public:
    int _playerId;
};

int main() {
    map<int, Player*> players;

    // 100,000명의 플레이어 추가
    for (int i = 0; i < 100000; i++) {
        players.insert(make_pair(i, new Player(i)));
    }

    // 특정 ID(10000) 플레이어 찾기
    if (players.find(10000) != players.end()) {
        cout << "찾음" << endl;
    } else {
        cout << "못 찾음" << endl;
    }

    return 0;
}

🔎 📌 개선된 점

1. players.find(10000); → O(log n)으로 탐색 가능
2. vector보다 훨씬 빠르게 데이터 찾기 가능

---

✅ 4) map 데이터 추가 및 삭제

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

int main() {
    map<int, int> m;

    // 10만 개 데이터 삽입
    for (int i = 0; i < 100000; i++) {
        m.insert(make_pair(i, i * 100));
    }

    // 5만 개 데이터 삭제
    for (int i = 0; i < 50000; i++) {
        int randValue = rand() % 50000;
        m.erase(randValue);
    }

    return 0;
}

📢 삭제 시 erase() 사용, O(log n) 시간 복잡도

---

✅ 5) map 탐색 및 순회

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

int main() {
    map<int, string> m;
    m.insert(make_pair(1, "Alice"));
    m.insert(make_pair(2, "Bob"));
    m.insert(make_pair(3, "Charlie"));

    // `find()`를 사용하여 검색
    if (m.find(2) != m.end()) {
        cout << "Key 2 찾음!" << endl;
    }

    // `map` 반복문 순회
    for (map<int, string>::iterator it = m.begin(); it != m.end(); ++it) {
        cout << "Key: " << it->first << ", Value: " << it->second << endl;
    }

    return 0;
}

📢 정렬된 상태로 반복자(iterator)를 사용해 순회 가능

---

✅ 6) map에서 operator[] 사용 시 주의점

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

int main() {
    map<int, int> m;
    
    // 존재하지 않는 키에 접근
    cout << m[5] << endl;  // 자동으로 (5, 0) 추가됨

    return 0;
}

📢 주의! [] 연산자를 사용하면 키가 없을 경우 기본값(0)이 추가됨

---