[C++] STL map

C++ STL의 map은 Key-Value(키-값) 쌍을 저장하는 연관 컨테이너(associative container)이다. map을 제대로 이해하려면, 그 기반이 되는 pair부터 짚고 넘어가는 것이 좋다.

pair

std::pair는 서로 다른 두 개의 값을 하나의 객체로 묶어주는 구조체이다. STL에서 아주 자주 사용되며, map의 내부 요소 타입도 pair이다.

pair의 선언과 사용

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

int main() {
    pair<int, string> p = {1, "apple"};

    cout << p.first << "\n" << p.second;

    return 0;
}

🔽 출력 :

1
apple

first: 첫 번째 값

second: 두 번째 값

pair는 언제 쓰일까?

• 두 값을 하나로 묶어 관리하고 싶을 때
• 좌표 (x, y)
• (인덱스, 값)
• (key, value) 형태의 데이터

특히 map에서는 모든 원소가 pair<const Key, Value> 형태로 저장된다.

map

std::map은 Key를 기준으로 정렬된 상태를 유지하는 컨테이너이다. 내부적으로는 이진 탐색 트리(보통 Red-Black Tree)로 구현되어 있다.

핵심 특징

• Key는 중복 불가
• 자동 정렬 (기본: 오름차순)
• 삽입/삭제/탐색: O(logn)

map의 헤더와 선언

#include <map>

map<int, string> m;

int: Key

string: Value

주요 멤버 함수

함수명	설명
insert({k, v})	(k, v) 쌍을 map에 삽입
m[k]	k에 해당하는 value 접근
find(k)	key k를 가리키는 iterator 반환
erase(k)	key k에 해당하는 원소 삭제
size()	저장된 원소 개수 반환
empty()	map이 비어 있는지 확인
begin() / end()	시작 / 끝 iterator 반환

예시 코드

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

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

    m.insert({1, "apple"});
    m.insert({3, "banana"});
    m.insert({2, "orange"});

    for (auto it = m.begin(); it != m.end(); it++) {
        cout << it->first << ": " << it->second << "\n";
    }

    return 0;
}

🔽 출력 :

1: apple
2: orange
3: banana

Key 기준으로 자동 정렬되어 출력되는 것을 확인할 수 있다.

operator[] 사용 시 주의점

map<int, int> m;

m[10] = 5;
cout << m[10]; // 5

주의

m[key] 형태로 접근할 때, key가 존재하지 않을 경우 자동으로 생성된다.

map<int, int> m;

cout << m[1]; // 0 (자동 삽입)

값 타입의 기본값으로 삽입되며, 단순 조회 목적이라면 find()를 사용하는 것이 안전하다.

find() 사용 예시

if (m.find(2) != m.end()) {
    cout << "존재함";
}
else {
    cout << "존재하지 않음";
}

map 순회 (향상된 for 문)

for (auto p : m) {
    cout << p.first << " " << p.second;
}

여기서 p는 pair<const Key, Value> 타입이다.

map 정렬 기준 바꾸기

기본은 오름차순이지만, 비교 함수를 지정할 수 있다.

map<int, int, greater<int>> m;

-> Key 기준 내림차순 정렬

실전

https://www.acmicpc.net/problem/20291

map에 대한 개념을 점검해볼 수 있는 좋은 문제인 것 같다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    
    map<string, int> m;
    
    for (int i = 0; i < N; i++) {
        string name;
        cin >> name;
        
        for (int j = 0; j < name.length(); j++) {
            if (name[j] == '.') {
                string extension = name.substr(j + 1, name.length());
                m[extension]++;
                
                break;
            }
        }
    }
    
    for (const auto& p : m) {
        cout << p.first << " " << p.second << "\n";
    }
    
    return 0;
}

마무리

map은 pair 기반의 연관 컨테이너이다. Key는 중복이 불가하며, 자동으로 Key 기준으로 정렬된다. 삽입/삭제/탐색 시간은 O(logn)이며, 단순 조회할 때는 find()가 안전하다.

Key로 정렬되는 사전(Dictionary)이라고 생각하면 편하다.