std::map

map의 본질

• std::map<Key, T>는 키-값(Key-Value) 쌍을 저장하는 정렬 연관 컨테이너입니다.
• 키는 항상 정렬 상태를 유지합니다(기본: 오름차순, 내부는 보통 레드-블랙 트리).
• 키는 중복 불가입니다. (중복 키가 필요하면 std::multimap)
• #include <map>

std::map<int, std::string> players;
players.emplace(100, "Alice");
players.emplace(200, "Bob");

---

기본 사용 패턴

std::map<int, std::string> players;

players.insert({100, "Alice"});     // pair 삽입
players.emplace(200, "Bob");        // in-place 생성 삽입
players[300] = "Carol";             // 없으면 생성 후 대입

• 순회는 키 오름차순으로 진행됩니다.

for (const auto& [id, name] : players) {
    std::cout << id << " : " << name << '\n';
}

---

삽입/갱신 API 차이 (중요)

std::map<int, std::string> mp;

auto [it1, ok1] = mp.insert({1, "one"});      // 키 1 없으면 삽입
auto [it2, ok2] = mp.emplace(1, "uno");       // 키 1 이미 있으면 삽입 안 됨
auto [it3, ok3] = mp.try_emplace(2, "two");   // (C++17) 없을 때만 값 생성

mp.insert_or_assign(1, "ONE");                // (C++17) 있으면 덮어쓰기, 없으면 삽입

• "기존 값 유지 + 없을 때만 생성" -> try_emplace
• "업서트(upsert): 있으면 갱신, 없으면 삽입" -> insert_or_assign

---

조회 API 차이: find / contains / at / operator[]

std::map<int, int> score;
score.emplace(10, 100);

if (auto it = score.find(10); it != score.end()) {
    std::cout << it->second << '\n';
}

bool has10 = score.contains(10);   // C++20
int s = score.at(10);              // 키 없으면 std::out_of_range 예외

score[20] += 5;                    // 키 20 없으면 0으로 생성 후 += 5

핵심 정리:

• find : 가장 일반적인 안전 조회 (end() 비교 필요)
• contains : 존재 여부만 빠르게 확인 (C++20)
• at : 없으면 예외 -> "반드시 있어야 하는 키"에 적합
• operator[] : 없으면 삽입 발생 -> 순수 조회에는 부적합

---

operator[] 함정 (반드시 기억)

std::map<int, std::string> mp;

std::string name = mp[100]; // 키 100이 없으면 {100, ""} 삽입됨

• 의도치 않은 원소 추가로 버그/메모리 증가를 유발할 수 있습니다.
• 조회만 필요하면 find/contains/at를 우선 고려하세요.

요약

조회만 한다            -> find / contains / at
없으면 만들어도 된다   -> operator[]

---

시간 복잡도 + 이터레이터 안정성

연산	복잡도
find, insert, erase(key)	O(log N)
lower_bound, upper_bound	O(log N)
순회 전체	O(N)

이터레이터 안정성:

• insert/emplace는 기존 이터레이터/참조를 무효화하지 않습니다.
• erase는 삭제된 원소의 이터레이터만 무효화됩니다.

---

언제 map을 쓰나?

map이 유리한 경우:

• 키 순서가 항상 필요함 (정렬 순회, 범위 질의)
• lower_bound/upper_bound 같은 순서 기반 연산 사용
• 최악 성능도 안정적으로 관리하고 싶음 (O(log N))

unordered_map이 유리한 경우:

• 순서가 필요 없음
• 평균 조회/삽입 성능을 더 중요하게 봄 (O(1) 평균)

---

C# 대응 + 체크 질문

• C++ std::map ~= C# SortedDictionary<TKey, TValue>
• C++ std::unordered_map ~= C# Dictionary<TKey, TValue>

체크 질문 (스스로 답해보기)

• insert, try_emplace, insert_or_assign의 차이를 설명할 수 있는가?
• operator[]가 조회 코드에서 버그를 만들 수 있는 이유는?
• 순서 기반 쿼리(lower_bound)가 필요할 때 왜 map이 적합한가?

---