C++ std::map: 키, 값, 조회, 삽입

키로 값 찾기

vector는 위치로 인덱싱할 때—요소 0, 요소 1 등—훌륭합니다. 하지만 위치가 없는 경우가 많습니다. 가진 것은 이름이고, 거기에 연결된 것을 원하죠. 사용자 이름과 그 점수, 단어와 그 출현 횟수, 국가 코드와 그 수도처럼요. 일치하는 항목을 찾으려고 vector를 훑는 것은 O(n)이며 금세 느려집니다.

std::map이 이를 해결합니다. 키-값 쌍을 저장하고 키로 정렬된 상태를 유지하며, 키로 값을 O(log n) 시간에 조회할 수 있게 해줍니다. 사용하려면 <map>을 포함하세요.

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

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

    scores["Ada"] = 90;
    scores["Grace"] = 100;
    scores["Linus"] = 75;

    cout << "Grace scored " << scores["Grace"] << "\n";
}

map<string, int>는 "string 키에서 int 값으로 가는 map"으로 읽습니다. 키는 고유하며, 같은 키에 두 번 대입하면 두 번째 값이 이깁니다. 내부적으로 map은 균형 이진 탐색 트리이며, 이 때문에 모든 것이 정렬된 상태로 유지되고 조회가 상수가 아닌 로그 시간이 됩니다.

요소 삽입하기

항목을 넣는 방법은 몇 가지가 있고, 그 차이가 중요합니다. 가장 흔한 것은 operator[]로, 키가 없으면 생성하고 대입할 수 있는 참조를 반환합니다.

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

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

    inventory["apples"] = 12;     // 생성 + 대입
    inventory["apples"] += 3;     // 읽기-수정-쓰기, 이제 15

    cout << "apples: " << inventory["apples"] << "\n";
}

기존 키를 덮어쓰기를 거부하는 삽입을 원한다면 insert나 emplace를 사용하세요. 둘 다 pair를 반환하며, 그 .second는 삽입이 실제로 일어났는지 알려주는 bool입니다.

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

int main() {
    map<string, int> ages;
    ages["Ada"] = 36;

    auto result = ages.insert({"Ada", 99});   // Ada는 이미 존재함
    cout << "inserted? " << result.second << "\n";   // 0 (false)
    cout << "Ada is still " << ages["Ada"] << "\n";  // 36, 변경 없음
}

"마지막 쓰기가 이긴다"가 원하는 동작이면 []를, 기존 키를 그대로 두어야 하면 insert/emplace를 사용하세요.

operator[]의 함정: 읽을 때 삽입한다

이것은 단연 가장 흔한 map 버그입니다. operator[]는 순수한 읽기가 아닙니다. 키가 없으면 기본 생성된 값(int이면 0, string이면 "" 등)으로 조용히 삽입하고 그에 대한 참조를 반환합니다. 따라서 []로 키를 단지 확인하기만 해도 map이 변경됩니다.

map<string, int> m;
if (m["maybe"] == 0) {   // 버그: 이것은 방금 "maybe" -> 0 을 생성했다
    // ...
}
cout << m.size();        // 0이 아니라 1 - 실수로 키를 삽입했다

이것은 const map에서도 발목을 잡습니다. operator[]는 삽입이 필요할 수 있기 때문에 아예 컴파일조차 되지 않습니다. 삽입 없이 읽으려면 find, count/contains, 또는 at을 사용하세요.

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

int main() {
    map<string, int> m = {{"a", 1}, {"b", 2}};

    // find: 반복자를 반환, 없으면 == end()
    auto it = m.find("c");
    cout << "found c? " << (it != m.end()) << "\n";   // 0

    // contains (C++20) 또는 count (모든 버전)
    cout << "has a? " << m.contains("a") << "\n";      // 1
    cout << "count z: " << m.count("z") << "\n";       // 0

    // at: 없으면 std::out_of_range를 던짐 - 절대 삽입하지 않음
    cout << "a = " << m.at("a") << "\n";
}

경험칙: 읽으려는 의도라면 절대 []에 손대지 마세요. 키가 반드시 존재해야 하면 at을, 없을 수도 있으면 find/contains를 사용하세요.

정렬된 순서로 순회하기

map은 트리 기반이므로, 순회하면 키를 오름차순 정렬된 순서로—언제나, 공짜로—방문합니다. 각 요소는 pair<const Key, Value>이므로 구조적 바인딩을 사용해 키와 값을 깔끔하게 풀어내세요.

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

int main() {
    map<string, int> wordCount;
    for (const string& w : {"sky", "blue", "sky", "sea", "blue", "sky"}) {
        wordCount[w]++;   // 없는 키는 0에서 시작한 뒤 ++
    }

    for (const auto& [word, count] : wordCount) {
        cout << word << ": " << count << "\n";
    }
}

바인딩의 키가 const임에 주목하세요. auto&로 루프에서 값은 바꿀 수 있지만, 키를 제자리에서 바꾸는 것은 절대 안 됩니다(정렬 순서가 깨지기 때문). 출력은 어떤 정렬 단계도 없이 알파벳 순서(blue, sea, sky)로 나오는데, 이것이 바로 정렬된 순회가 중요할 때 해시 테이블 대신 map을 고르는 이유입니다.

이 wordCount[w]++ 관용구는 접근 시 삽입 동작의 정석적인 사용이기도 합니다. 여기서는 없는 키가 0에서 시작하기를 원하므로 []가 올바른 도구입니다.

요소 제거와 크기 측정

키로 제거하려면 erase를 사용하며, 제거된 요소 수(map에서는 0 또는 1)를 반환합니다. find에서 얻은 반복자로도 제거할 수 있습니다. 컨테이너의 상태는 size()와 empty()로 확인하세요.

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

int main() {
    map<string, int> m = {{"x", 1}, {"y", 2}, {"z", 3}};

    cout << "removed: " << m.erase("y") << "\n";   // 1
    cout << "removed: " << m.erase("q") << "\n";   // 0 (없었음)

    cout << "size: " << m.size() << "\n";          // 2
    cout << "empty? " << m.empty() << "\n";        // 0

    for (const auto& [k, v] : m) cout << k << " ";  // x z
    cout << "\n";
}

루프 안에서 제거할 때의 함정: m.erase(it)는 it을 무효화하므로 그 뒤에 ++it을 할 수 없습니다. C++11 이후의 안전한 패턴은 다음 요소를 가리키는 반복자를 반환하는 it = m.erase(it)입니다. map 전체에 걸친 일회성 조건부 제거에는 std::erase_if(m, predicate)(C++20)가 더 깔끔합니다.

다음: unordered_map

std::map은 정렬된 키와 예측 가능한 O(log n) 연산을 제공하지만, 그 정렬의 대가를 모든 조회마다 치릅니다. 키 순서는 신경 쓰지 않고 그저 가능한 한 가장 빠른 조회만 원한다면, unordered_map이 정렬된 트리를 해시 테이블로 바꿔—평균 O(1) 접근을 제공합니다. 다음에는 그것이 어떻게 동작하는지, 평균 상수 시간이 map의 로그를 언제 이기는지, 그리고 그에 따르는 해싱의 함정(사용자 정의 키 타입, 최악의 경우 충돌)을 살펴보겠습니다.