[C++] Map

1. 개요

std::map은 키-값 쌍을 자동 정렬하여 저장하는 연관 컨테이너입니다. 고유한 키를 기준으로 정렬되며, 내부적으로 이진 탐색 트리(Red-Black Tree)를 사용합니다. <map> 헤더에 정의되어 있습니다.

 #include <map>
 std::map<std::string, int> ages = {{"Alice", 25}, {"Bob", 30}};

2. 주요 특징

• 고유한 키를 기준으로 자동 정렬 (기본: 오름차순)
• 중복 키 허용 안 함
• 연산 시간 복잡도: O(log N)
• 트리 기반: 삽입, 삭제, 탐색 효율적
• 반복자는 키 순서대로 순회

3. 주요 멤버 함수

🔹 크기 관련

함수	설명
empty()	비었는지 확인
size()	요소 수 반환
clear()	모든 요소 제거

🔹 접근

함수	설명
operator[](key)	키로 값 접근 (없으면 생성)
at(key)	키로 값 접근 (없으면 예외 발생)

🔹 삽입/삭제

함수	설명
insert({key, val})	키-값 쌍 삽입
emplace(key, val)	직접 생성하여 삽입
erase(key)	키로 제거
erase(iterator)	반복자로 제거
erase(first, last)	범위 삭제
swap(other)	두 map 교환

🔹 탐색

함수	설명
find(key)	키 검색, 반복자 반환
count(key)	키 존재 여부 (0 또는 1)
lower_bound(key)	key 이상 첫 반복자
upper_bound(key)	key 초과 첫 반복자
equal_range(key)	[lower, upper) 범위 반환

4. 반복자 관련

함수	설명
begin() / end()	정방향 반복자
rbegin() / rend()	역방향 반복자
cbegin() / cend()	const 반복자

5. 예제 코드

 #include <iostream>
 #include <map>
 using namespace std;
 
 int main() {
     map<string, int> age;
     age["Alice"] = 25;
     age["Bob"] = 30;
 
     for (const auto& p : age) {
         cout << p.first << ": " << p.second << endl;
     }
 
     if (age.find("Bob") != age.end()) {
         cout << "Bob exists" << endl;
     }
 
     return 0;
 }

6. 사용자 정의 정렬

 struct Desc {
     bool operator()(const string& a, const string& b) const {
         return a > b;
     }
 };
 
 std::map<std::string, int, Desc> descMap;

7. std::map vs std::unordered_map

항목	std::map	std::unordered_map
내부 구조	트리 (정렬됨)	해시 테이블 (무순서)
시간 복잡도	O(log N)	평균 O(1)
정렬 보장	있음	없음
반복 순서	키 오름차순	임의 순서
커스텀 정렬	가능	불가 (해시 기준)

8. 주의사항

• operator[]는 키가 없으면 기본값으로 생성함
• 중복 키를 허용하려면 std::multimap 사용
• 반복자로 원소 직접 수정 시 주의 필요 (키는 const)