[C++ STL] map 컨테이너 완벽 정리: 구조부터 활용까지

1. map이란 무엇인가?

map은 연관 컨테이너(Associative Container) 중 하나로, 노드 기반의 균형 이진 트리(Balanced Binary Tree) 구조를 가지고 있다.

핵심 특징

• Key와 Value의 쌍: 데이터가 pair<key, value> 객체 형태로 저장된다.
• Unique Key: 하나의 map 안에서 키(Key)는 중복될 수 없다. (중복 키가 필요하면 multimap을 사용해야 한다.)
• 자동 정렬: 원소가 삽입되는 동시에 키(Key)를 기준으로 자동 정렬된다.

Q. 오름차순이면 첫 시작이 제일 작은 것인가? A. 그렇다. 기본 설정인 오름차순(less) 기준일 때, begin() 이터레이터가 가리키는 첫 번째 원소의 키 값이 가장 작다.

Q. Value 값 기준으로 정렬되는 것인가? A. 아니다. 무조건 Key를 기준으로 정렬된다. Value는 그저 Key에 매달려 있는 데이터일 뿐이다.

 

2. map의 선언과 생성자

#include <map>

// 1. 기본 선언
map<string, int> m;

// 2. 정렬 기준 설정 (예: 내림차순)
map<int, int, greater<int>> m_desc;

// 3. 복사 생성
map<int, int> m2(m1);

 

 

3. 데이터 삽입 방법 (두 가지)

① insert 멤버 함수 사용

pair 객체를 만들어 인자로 전달해야 한다.

m.insert(pair<string, int>("BlockDMask", 27));
m.insert(make_pair("Gemini", 3));

② [] 연산자 사용 (가장 권장되는 방법)

마치 배열처럼 키를 인덱스로 사용하여 값을 바로 대입할 수 있다. 매우 직관적이다.

m["C++"] = 100;
m["Algorithm"] = 90;

• 특징: 만약 해당 키가 이미 존재한다면 값을 갱신하고, 없다면 새로 삽입한다.

 

 

4. 주요 멤버 함수

• m.begin(), m.end(): 시작과 끝을 가리키는 이터레이터를 반환한다.
• m.find(key): 키를 찾아 이터레이터를 반환한다. 못 찾으면 m.end()를 반환한다. ($O(\log N)$)
• m.count(key): 특정 키가 있는지 확인한다. (있으면 1, 없으면 0 반환)
• m.size(): 현재 저장된 원소의 개수를 반환한다.
• m.erase(key): 해당 키를 가진 원소를 삭제한다.
• m.clear(): 모든 원소를 삭제한다.

 

5. map의 [] 연산자는 "검색+삽입"이다

 

• 탐색: 입력받은 Key가 메모리(트리)에 있는지 찾는다.
• 발견 시: 해당 Key에 연결된 Value의 참조(&)를 반환한다. (값을 수정할 수 있게 된다.)
• 미발견 시: 해당 Key를 새로 만들고, Value는 해당 타입의 기본값(Default)으로 초기화하여 삽입한다. 그 후, 방금 만든 Value의 참조를 반환한다.
  
  **해당 방식은 배열과 벡터에서는 삽입이 안된다.

 

---

5. 배운 점 & 회고 (TIL)

① 데이터 접근의 편의성

map의 가장 큰 매력은 [] 연산자이다. 숫자가 아닌 string이나 다른 객체를 인덱스처럼 써서 데이터를 저장하고 불러올 수 있다는 점이 매우 강력하다.

② 정렬의 기준은 언제나 'Key'

데이터를 넣기만 해도 알아서 정렬해준다는 점은 편리하지만, 그 기준이 반드시 Key라는 점을 잊지 말아야 한다. Value 기준으로 정렬하고 싶다면 별도로 vector에 옮겨 담아 정렬하는 등의 추가 작업이 필요하다.

③ 이진 트리의 효율성

순차적으로 데이터를 찾는 배열(O(N))과 달리, map은 균형 이진 트리 구조이므로 탐색, 삽입, 삭제 모두 O(log N)의 시간 복잡도를 가진다. 데이터가 많아질수록 배열보다 훨씬 빠른 성능을 보여준다.

 

 

"번호표(Key)와 물건(Value)을 세트로 관리하는 스마트한 보관함이 바로 map이다. 특히 문자열로 데이터를 관리해야 하는 상황에서 map은 선택이 아닌 필수 자료구조이다!"