pkglog
EN

C++ map·unordered_map·flat_map: 성능 비교와 선택 기준

작성 · · 39분 읽기 · 수정 중급 개념

💡 초보자를 위한 한 줄: 정렬된 키 순회·lower_bound 범위가 필요하면 map/set, 순서는 상관없고 조회만 빠르면 된다면 unordered_*를 먼저 고려합니다. 해시는 좋은 해시 함수·예약 reserve가 성능을 가릅니다. 10-1 vector·string 다음으로 읽기 좋습니다.

들어가며: map을 썼는데 왜 이렇게 느릴까?

사용자 ID로 정보를 조회하는 시스템을 만들었습니다. std::map을 사용했는데 데이터가 많아지자 느려졌습니다.

문제의 코드에서는 std::map에 사용자 ID를 키로 User를 넣고 find로 조회합니다. std::map은 내부적으로 Red-Black Tree(레드-블랙 트리—균형 이진 탐색 트리로, 삽입·삭제 후에도 높이가 O(log n)으로 유지됨)라서 삽입·검색·삭제가 모두 O(log n)(데이터 n개일 때 대략 log₂n 번 비교. 예: 100만 개면 약 20번)입니다. 100만 개면 find 한 번에 약 20번 정도의 비교가 필요하며, “키로만 빠르게 찾고 순서는 필요 없다”면 unordered_map(내부가 해시 테이블—키를 해시값으로 변환해 버킷에 넣어, 평균 O(1)에 검색)으로 바꿔 평균 O(1) 검색을 쓰는 편이 훨씬 빠릅니다. 당시에는 “map이 연관 배열이므로” 하고 썼다가, 데이터가 커지면서 검색이 병목이 된 뒤 unordered_map으로 바꿨을 때 체감이 크게 나았습니다.

std::map<int, User> users;  // Red-Black Tree

// 100만 개 데이터 삽입
for (int i = 0; i < 1000000; ++i) {
    users[i] = User{...};
}

// 검색
auto it = users.find(123456);  // O(log n) ≈ 20번 비교

std::map은 Red-Black Tree라 삽입·검색·삭제가 O(log n)입니다. 100만 개일 때 find 한 번에 약 20번 비교가 필요하며, 검색이 빈번하면 병목이 됩니다. 키로만 빠르게 찾고 순서가 필요 없으면 unordered_map으로 바꾸면 평균 O(1)로 빨라집니다.

원인:

  • std::map은 Red-Black Tree (균형 이진 탐색 트리)
  • 검색 시간: O(log n)
  • 100만 개면 약 20번 비교 필요

키로 빠르게 찾기만 하면 되고 순서가 필요 없으면 unordered_map이 평균 O(1)로 더 유리합니다. 반대로 키 순서대로 순회하거나, “가장 작은/큰 키”를 자주 써야 하면 map·set이 맞습니다. 실무에서는 “정렬이 필요한가?”와 “키 검색 빈도”를 보고 선택하면 됩니다.

일상 비유: map은 사전처럼 항목이 알파벳(키) 순으로 정렬되어 있어서 “A로 시작하는 단어”부터 찾기 쉽습니다. 반면 unordered_map은 서랍장처럼 각 키에 맞는 칸에 바로 넣어 두어서, “이 단어가 있는지”만 검색할 때는 사전을 한 장씩 넘기는 것보다 훨씬 빠릅니다. 정렬이 필요 없고 “검색만 빠르면” 될 때는 서랍장이 유리합니다.

unordered_map으로 해결:

std::unordered_map<int, User> users;  // Hash Table

// 100만 개 데이터 삽입
for (int i = 0; i < 1000000; ++i) {
    users[i] = User{...};
}

// 검색
auto it = users.find(123456);  // 평균 O(1): 해시 계산 + 버킷 한 곳 확인

std::unordered_map은 해시 테이블이라 평균 O(1)에 검색됩니다. 키 순서는 보장되지 않지만, “키로만 조회”가 목적이면 map보다 빠릅니다. 실제 차이는 키 타입·해시 품질·캐시 상태에 따라 달라지므로 O(log n)과 평균 O(1)의 실제 차이의 벤치마크 코드로 직접 측정해 보는 것이 좋습니다.

“O(log n) 대 O(1)“만 보면 차이가 압도적일 것 같지만, 실제 속도를 좌우하는 것은 메모리 접근 횟수입니다. std::map은 노드마다 따로 할당된 트리라 find 한 번에 약 20개의 노드를 따라가며, 노드가 메모리 여기저기에 흩어져 있어 캐시 미스가 잦습니다. std::unordered_map도 표준의 반복자 안정성 요구 때문에 대부분의 구현이 버킷 배열과 노드 연결 리스트 구조라서, 해시 계산 뒤 버킷을 거쳐 노드로 한 번 더 건너가야 합니다. 그래서 정수 키처럼 비교가 싼 경우에는 차이가 기대보다 작을 수 있고, 반대로 긴 문자열 키는 map이 비교를 20번 하는 비용이 커서 해시 쪽이 크게 유리해집니다.

주의: unordered_map은 키의 순서가 보장되지 않습니다. “키 크기 순으로 순회”나 “가장 작은 키”가 필요하면 map/set을 써야 하며, “키로만 빠르게 찾기”가 목적이면 unordered_map이 적합합니다. 해시 충돌이 많으면 최악의 경우 O(n)이 될 수 있어, 키 분포가 나쁘면 map이 더 나을 수도 있습니다.

이 글은 map/set의 Red-Black Tree와 unordered_map/unordered_set의 해시 테이블 구조를 비교하고, find·insert·erase와 lower_bound·upper_bound 범위 검색, 커스텀 키 타입, 시간 복잡도와 선택 기준, reserve·try_emplace 같은 최적화, 자주 겪는 버그와 프로덕션 패턴까지 다룹니다.

실시간 순위 시스템과 그 밖의 조회 병목

실시간 순위 시스템

게임 점수판에서 “상위 10명”을 자주 조회해야 합니다. unordered_map은 순서가 없어 매번 전체를 정렬해야 하며, std::map은 begin()부터 순회하거나 rbegin()으로 역순 순회가 가능해 O(k)에 상위 k명을 얻을 수 있습니다.

시간대별 이벤트 조회

로그 시스템에서 “2024-01-01 10:00~11:00 사이 이벤트”를 찾을 때, map의 lower_bound/upper_bound로 구간 검색이 O(log n)에 가능합니다. unordered_map은 이런 범위 검색을 지원하지 않아 전체 순회가 필요합니다.

설정 파일의 키 순서를 유지해야 할 때

JSON/YAML 설정을 파싱해 컨테이너에 넣을 때 사용자가 쓴 키 순서를 그대로 유지해야 하는 경우가 있습니다. 이때 흔히 map을 떠올리지만, map은 키의 사전순으로 정렬할 뿐 넣은 순서를 기억하지 않고, unordered_map은 순서 자체가 없습니다. 넣은 순서가 필요하면 std::vector<std::pair<K, V>>나 삽입 순서를 유지하는 별도 컨테이너를 써야 합니다. “정렬된 순서”와 “넣은 순서”를 구분하는 것이 이 선택의 출발점입니다.

중복 제거 후 정렬 출력

파일에서 단어를 읽어 중복을 제거하고 알파벳 순으로 출력할 때, std::set을 쓰면 삽입 시 자동 정렬·중복 제거가 되고, unordered_set은 중복 제거만 되고 정렬하려면 별도 vector로 복사 후 정렬해야 합니다.

해시 충돌로 인한 성능 저하

unordered_map에 커스텀 키를 넣을 때 해시 함수가 나쁘면(예: 항상 같은 값 반환) 한 버킷에 몰려 최악 O(n)이 됩니다. map은 키 분포와 무관하게 O(log n)을 보장합니다.

operator[]로 의도치 않은 삽입

“키가 있는지 확인만 하려고” if (m[key] > 0)을 썼는데, 없던 키가 0으로 삽입되어 map 크기가 커지고, 나중에 “왜 이 키가 있지?” 하는 버그가 발생합니다.

map과 set: Red-Black Tree 기반 정렬 컨테이너

map: 키-값 쌍 저장

std::map은 키-값 쌍을 저장하며, 키 기준으로 자동 정렬됩니다. operator[]로 키를 넣거나 조회할 수 있으며, 없던 키를 []로 접근하면 기본 생성된 값이 삽입됩니다. find는 반복자를 반환하므로 end()와 비교해 존재 여부를 확인한 뒤 it->first, it->second로 키와 값에 접근합니다. 순회하면 키가 정렬된 순서로 나옵니다.

// 복사해 붙여넣은 뒤: g++ -std=c++17 -o map_basic map_basic.cpp && ./map_basic
#include <map>
#include <iostream>
#include <string>

int main() {
    std::map<std::string, int> ages;

    // 삽입
    ages["Alice"] = 25;
    ages["Bob"] = 30;
    ages.insert({"Charlie", 35});
    ages.emplace("David", 40);
    
    // 접근
    std::cout << ages["Alice"] << "\n";  // 25
    
    // 검색
    auto it = ages.find("Bob");
    if (it != ages.end()) {
        std::cout << it->first << ": " << it->second << "\n";
    }
    
    // 삭제
    ages.erase("Charlie");
    
    // 순회 (정렬된 순서)
    for (const auto& [name, age] : ages) {
        std::cout << name << ": " << age << "\n";
    }
}

ages[“Alice”]=25처럼 operator[]로 삽입·조회하며, insert/emplace로도 넣을 수 있습니다. find는 반복자를 돌려주므로 it != ages.end()로 존재 여부를 확인한 뒤 it->first, it->second로 키와 값에 접근합니다. 순회하면 키(이름) 기준 정렬된 순서로 나옵니다.

실행 결과 (알파벳 순서로 정렬됨):

Alice: 25
Bob: 30
David: 40

set: 중복 없는 집합

std::set은 중복이 없는 키만 저장하는 컨테이너입니다. 같은 값을 다시 insert해도 한 개만 유지되고, 내부적으로 역시 키 순서로 정렬됩니다. count(key)는 0 또는 1을 반환하므로 존재 여부 확인에 쓸 수 있으며, 순회하면 정렬된 순서로 원소를 얻습니다.

// 복사해 붙여넣은 뒤: g++ -std=c++17 -o set_basic set_basic.cpp && ./set_basic
#include <set>
#include <iostream>

int main() {
    std::set<int> numbers;
    
    // 삽입
    numbers.insert(5);
    numbers.insert(2);
    numbers.insert(8);
    numbers.insert(2);  // 중복, 무시됨
    
    // 검색
    if (numbers.count(5) > 0) {
        std::cout << "5 exists\n";
    }
    
    // 순회 (정렬된 순서)
    for (int num : numbers) {
        std::cout << num << " ";
    }
    // 2 5 8
}

set은 중복을 허용하지 않아 insert(2)를 두 번 해도 한 개만 들어갑니다. count(5)는 0 또는 1을 반환하므로 존재 여부 확인에 쓰며, 순회하면 키(숫자)가 정렬된 순서(2, 5, 8)로 나옵니다. 내부적으로 map과 같은 Red-Black Tree 구조입니다.

실행 결과 (정렬된 순서로 출력):

5 exists
2 5 8

map/set 내부 구조: Red-Black Tree

        [Bob:30]
       /        \
  [Alice:25]  [David:40]
                /
           [Charlie:35]

특징:

  • 자동 정렬 (키 기준)
  • 균형 유지 (높이 차이 최대 2배)
  • 삽입/삭제/검색: O(log n)

Red-Black Tree 동작 시각화

flowchart TB
    subgraph RB["Red-Black Tree (map 내부)"]
        N1["(Bob:30)"]
        N2["(Alice:25)"]
        N3["(David:40)"]
        N4["(Charlie:35)"]
        N1 --> N2
        N1 --> N3
        N3 --> N4
    end
    O1["삽입: O(log n)br/균형 유지"]
    O2["검색: O(log n)br/이진 탐색"]
    O3["순회: O(n)br/중위 순회 = 정렬 순서"]
    RB --> O1
    RB --> O2
    RB --> O3

위 다이어그램 설명: map은 Red-Black Tree로 구현되어 삽입·삭제 시 균형을 유지합니다. 검색은 이진 탐색으로 O(log n)이고, 중위 순회 시 키가 정렬된 순서로 나옵니다.

unordered_map과 unordered_set: 해시 테이블 기반 컨테이너

unordered_map: 해시 테이블

std::unordered_map은 해시 테이블 기반이라 키 순서가 유지되지 않습니다. 삽입·삭제·검색이 평균 O(1)이라, 키로만 빠르게 찾으면 되고 순서가 필요 없을 때 map보다 유리합니다. 사용법은 map과 비슷하지만, for로 순회할 때 나오는 순서는 구현에 따라 달라지며 예측하지 않는 것이 좋습니다.

#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> ages;
    
    ages["Alice"] = 25;
    ages["Bob"] = 30;
    ages["Charlie"] = 35;
    
    // 순회 (순서 보장 안 됨)
    for (const auto& [name, age] : ages) {
        std::cout << name << ": " << age << "\n";
    }
    // 출력 순서: 예측 불가 (Bob, Alice, Charlie 등)
}

사용법은 map과 비슷하게 operator[], insert, emplace를 씁니다. for로 순회할 때 나오는 순서는 구현·해시값에 따라 달라지며 보장되지 않습니다. 키로 빠르게 찾기만 하면 되고 정렬이 필요 없을 때 사용합니다.

unordered_set: 해시 집합

std::unordered_set은 set과 같이 중복 없는 집합이지만, 내부가 해시 테이블이라 순서가 없고 검색이 평균 O(1)입니다. “이 값이 있는지”만 빠르게 확인하면 될 때 유용합니다.

#include <unordered_set>

int main() {
    std::unordered_set<int> numbers = {5, 2, 8, 2};
    
    // 검색 O(1)
    if (numbers.count(5) > 0) {
        std::cout << "5 exists\n";
    }
    
    // 순회 (순서 보장 안 됨)
    for (int num : numbers) {
        std::cout << num << " ";
    }
    // 출력: 8 2 5 (예시, 실제 순서는 다를 수 있음)
}

unordered_set도 중복은 없으며, count로 존재 여부를 O(1)에 확인할 수 있습니다. 순회 순서는 보장되지 않습니다. “이 값이 있는지”만 빠르게 보면 될 때 set 대신 쓰면 검색이 평균 O(1)로 유리합니다.

해시 테이블 내부 구조

Bucket 0: [Alice:25] → [David:40]
Bucket 1: [Bob:30]
Bucket 2: (empty)
Bucket 3: [Charlie:35]

특징:

  • 순서 없음
  • 해시 충돌 시 체이닝
  • 삽입/삭제/검색: O(1) (평균)

해시 테이블 동작 시각화

flowchart LR
    subgraph Hash[unordered_map 내부]
        K1["키: Alice"] --> H1["hash(Alice) % N"]
        K2["키: Bob"] --> H2["hash(Bob) % N"]
        H1 --> B1["Bucket 0"]
        H2 --> B2["Bucket 1"]
        B1 --> V1["(Alice:25)"]
        B2 --> V2["(Bob:30)"]
    end
    subgraph Perf[성능]
        P1["평균 O(1)"]
        P2["최악 O(n)br/해시 충돌 많을 때"]
    end
    Hash --> Perf

위 다이어그램 설명: unordered_map은 키를 해시값으로 변환해 버킷에 넣습니다. 해시 충돌이 적으면 평균 O(1)에 검색되지만, 충돌이 많으면 체인을 따라가야 해서 최악 O(n)이 됩니다.

find, insert, erase와 insert 반환값 활용

map/set의 find·insert·erase

std::map과 std::set에서 검색·삽입·삭제는 모두 O(log n)입니다. find는 반복자를, insert는 (반복자, 성공 여부) 쌍을, erase는 삭제된 개수(또는 다음 반복자)를 반환합니다.

std::map<int, std::string> m;
m.insert({1, "one"});
m.insert({2, "two"});
auto [it, ok] = m.insert({1, "ONE"});  // 중복, ok=false, 기존 유지

auto mit = m.find(1);
if (mit != m.end()) std::cout << mit->first << " -> " << mit->second << "\n";

m.erase(2);  // 키로 삭제

// 순회 중 삭제: it = m.erase(it)로 다음 반복자 받기
for (auto it = m.begin(); it != m.end(); ) {
    if (it->second.empty()) it = m.erase(it);
    else ++it;
}

insert는 중복 시 기존 값을 유지합니다. 순회 중 삭제할 때는 it = m.erase(it)로 다음 반복자를 받아야 합니다.

unordered_map/unordered_set의 find·insert·erase

unordered_map/unordered_set도 동일한 인터페이스를 제공하며 평균 O(1)에 동작합니다. insert, emplace, erase 사용법은 map/set과 같으며, operator[]는 map에만 있습니다.

insert 반환값 활용

insert는 std::pair<iterator, bool>을 반환합니다. bool이 true면 새로 삽입된 것이며, false면 이미 존재하는 키입니다. C++17 구조화 바인딩 auto [it, inserted] = m.insert({1, "first"})로 “삽입 시도 후 반복자 얻기” 패턴에 자주 씁니다.

lower_bound·upper_bound 범위 검색

정렬된 std::map과 std::set에서는 lower_bound, upper_bound, equal_range로 구간 검색이 가능합니다. unordered_*에는 이 연산이 없습니다.

lower_bound / upper_bound 의미

  • lower_bound(key): key 이상인 첫 원소의 반복자 (key 포함)
  • upper_bound(key): key 초과인 첫 원소의 반복자 (key 미포함)
  • 구간 [a, b]: [lower_bound(a), upper_bound(b)) — a 이상 b 이하
// g++ -std=c++17 -o range_search range_search.cpp && ./range_search
#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> m = {
        {10, "ten"}, {20, "twenty"}, {30, "thirty"},
        {40, "forty"}, {50, "fifty"}
    };

    // 25 이상 45 이하 구간 검색
    auto lo = m.lower_bound(25);  // 30 이상 첫 원소 -> 30
    auto hi = m.upper_bound(45);  // 45 초과 첫 원소 -> 50

    std::cout << "25~45 구간: ";
    for (auto it = lo; it != hi; ++it) {
        std::cout << it->first << " ";
    }
    // 출력: 30 40
}

lower_bound(25)는 25 이상인 첫 원소(30)를, upper_bound(45)는 45 초과인 첫 원소(50)를 가리킵니다. [lo, hi) 구간을 순회하면 25 이상 45 이하인 키만 얻습니다.

equal_range

equal_range(key)는 lower_bound(key)와 upper_bound(key)를 한 번에 반환합니다. std::multimap에서 같은 키를 가진 모든 원소를 순회할 때 유용합니다.

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> m = {
        {10, "A"}, {20, "B"}, {20, "B2"},  // map은 키 유일, B2 무시
        {30, "C"}
    };

    auto [lo, hi] = m.equal_range(20);
    std::cout << "키 20 구간: ";
    for (auto it = lo; it != hi; ++it) {
        std::cout << it->second << " ";
    }
    // map에서는 "B" 하나만 (키 유일)
    // multimap이면 "B" "B2" 모두

    // multimap 예시
    std::multimap<int, std::string> mm;
    mm.insert({1, "a"});
    mm.insert({1, "b"});
    mm.insert({1, "c"});
    auto [r1, r2] = mm.equal_range(1);
    for (auto it = r1; it != r2; ++it)
        std::cout << it->second << " ";  // a b c
}

equal_range는 pair<iterator, iterator>를 반환합니다. multimap에서는 같은 키에 여러 값이 매핑되므로, 이 구간을 순회해 모두 처리할 수 있습니다.

실전 예: 점수 구간별 조회

std::map<int, std::string> scoreToGrade = {
    {90, "A"}, {80, "B"}, {70, "C"}, {60, "D"}, {0, "F"}
};

// 75점이면 어떤 등급? -> 70 이상 80 미만 구간의 값
auto it = scoreToGrade.upper_bound(75);  // 80 초과 첫 원소
if (it != scoreToGrade.begin()) {
    --it;  // 70을 가리키게
    std::cout << "등급: " << it->second << "\n";  // C
}

점수 구간 [90,∞)=A, [80,90)=B, [70,80)=C 등으로 매핑할 때, upper_bound로 “해당 점수보다 큰 첫 경계”를 찾으며, 한 칸 왼으이면 해당 구간의 등급을 얻습니다.

커스텀 키 타입 (map vs unordered_map)

map: 비교 연산자 또는 비교 함수

std::map의 키는 비교 가능해야 합니다. operator<가 있거나, 세 번째 템플릿 인자로 비교 함수 객체를 넘깁니다.

struct Person {
    std::string name;
    int age;
    bool operator<(const Person& other) const { return age < other.age; }
};
std::map<Person, std::string> people;  // operator<로 나이 순 정렬

operator< 또는 비교 함수가 strict weak ordering을 만족해야 합니다. (a < b) == false && (b < a) == false이면 동일 키로 간주됩니다.

unordered_map: 해시 함수와 operator== 필요

std::unordered_map의 키에는 해시 함수와 동등 비교(operator==)가 필요합니다.

struct Point {
    int x, y;
    bool operator==(const Point& other) const { return x == other.x && y == other.y; }
};
namespace std {
    template <> struct hash<Point> {
        size_t operator()(const Point& p) const {
            return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
        }
    };
}
std::unordered_map<Point, std::string> points;

operator==로 동등 비교, std::hash<Point> 특수화로 해시값 계산. 해시 충돌이 적을수록 성능이 좋습니다.

set의 커스텀 키

std::set도 map과 동일하게 비교 연산자 또는 비교 함수가 필요합니다. unordered_set은 해시 함수와 operator==가 필요합니다.

복합 키: 여러 필드의 해시를 조합하기

(id, name)처럼 필드가 여러 개인 키는 각 필드의 해시를 하나로 합쳐야 합니다. 흔히 보이는 h1 ^ (h2 << 1)은 동작은 하지만 두 필드 값이 같으면 결과가 치우치고, 필드 순서만 바뀐 키끼리 자주 충돌합니다. Boost의 hash_combine과 같은 방식으로 섞어 주면 분포가 훨씬 고릅니다.

#include <functional>
#include <string>
#include <unordered_map>

struct CompositeKey {
    int id;
    std::string name;
    bool operator==(const CompositeKey& other) const {
        return id == other.id && name == other.name;
    }
};

inline void hash_combine(std::size_t& seed, std::size_t h) {
    seed ^= h + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

struct CompositeKeyHash {
    std::size_t operator()(const CompositeKey& k) const {
        std::size_t seed = std::hash<int>{}(k.id);
        hash_combine(seed, std::hash<std::string>{}(k.name));
        return seed;
    }
};

int main() {
    std::unordered_map<CompositeKey, int, CompositeKeyHash> cache;
    cache[{1, "Alice"}] = 100;
}

operator==에서 비교하는 필드와 해시에 넣는 필드는 정확히 같아야 합니다. 한쪽에만 필드를 추가하면 아래 문제 7처럼 넣은 키를 다시 찾지 못합니다.

O(log n)과 평균 O(1)의 실제 차이

연산별 시간 복잡도

연산map/setunordered_map/set
삽입O(log n)O(1) 평균, O(n) 최악
삭제O(log n)O(1) 평균, O(n) 최악
검색O(log n)O(1) 평균, O(n) 최악
순회O(n)O(n)
메모리노드당 오버헤드버킷 배열 + 체인

성능 벤치마크

동일한 개수로 삽입·검색을 반복했을 때, map은 O(log n)이라 노드 수가 많을수록 느려지고, unordered_map은 평균 O(1)이라 상대적으로 일정합니다. 100만 개 삽입 후 100만 번 find를 수행하는 아래 코드를 돌려 보면 대체로 unordered_map 쪽이 몇 배 빠르게 나오지만, 정확한 수치는 컴파일러·최적화 옵션·하드웨어에 따라 달라집니다.

// 벤치마크 예시: map vs unordered_map
std::map<int, int> m1;
std::unordered_map<int, int> m2;
m2.reserve(1000000);  // unordered_map은 reserve로 재해싱 최소화

auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < 1000000; ++i) m1[i] = i;
for (int i = 0; i < 1000000; ++i) m1.find(i);
auto t1 = std::chrono::duration_cast<std::chrono::milliseconds>(
    std::chrono::high_resolution_clock::now() - start).count();

start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < 1000000; ++i) m2[i] = i;
for (int i = 0; i < 1000000; ++i) m2.find(i);
auto t2 = std::chrono::duration_cast<std::chrono::milliseconds>(
    std::chrono::high_resolution_clock::now() - start).count();

std::cout << "map: " << t1 << " ms, unordered_map: " << t2 << " ms\n";

“키 검색만 많이 할 때”는 unordered_map이 유리합니다.

정렬이 필요하면 map, 조회만 하면 unordered_map

map을 쓰는 경우

정렬된 순서가 필요할 때

map은 키를 기준으로 항상 정렬된 상태를 유지하므로, “키 순서대로 출력”하거나 “가장 작은/큰 키”를 쓰는 연산에 적합합니다. 아래처럼 점수를 넣으면 이름(키) 알파벳 순으로 순회할 수 있습니다.

std::map<std::string, int> scores;
scores["Alice"] = 95;
scores["Bob"] = 80;
scores["Charlie"] = 90;

// 알파벳 순서로 출력
for (const auto& [name, score] : scores) {
    std::cout << name << ": " << score << "\n";
}
// Alice: 95
// Bob: 80
// Charlie: 90

map은 키 기준으로 항상 정렬된 상태를 유지하므로, for로 순회하면 이름(키) 알파벳 순으로 출력됩니다. “가장 작은/큰 키”, “키 순서대로 처리”가 필요할 때 map을 쓰면 됩니다.

범위 검색이 필요할 때

정렬된 map에서는 lower_bound(이상인 첫 위치), upper_bound(초과인 첫 위치)로 구간 [a, b]를 쉽게 표현할 수 있습니다. 예를 들어 “2021 이상 2022 이하”인 키만 순회하려면 아래처럼 구간 반복자를 구한 뒤 그 사이를 돌면 됩니다.

std::map<int, std::string> events;
events[2020] = "Event A";
events[2021] = "Event B";
events[2022] = "Event C";
events[2023] = "Event D";

// 2021~2022 범위 검색
auto start = events.lower_bound(2021);
auto end = events.upper_bound(2022);

for (auto it = start; it != end; ++it) {
    std::cout << it->first << ": " << it->second << "\n";
}
// 2021: Event B
// 2022: Event C

lower_bound(2021)은 2021 이상인 첫 원소, upper_bound(2022)는 2022 초과인 첫 원소의 반복자를 줍니다. [start, end) 구간을 순회하면 2021~2022 구간만 얻을 수 있어, 정렬된 map에서 범위 검색할 때 자주 쓰는 패턴입니다.

커스텀 비교 함수가 필요할 때

키 타입에 대해 “크다/작다”를 다르게 정의하고 싶을 때는, map의 세 번째 템플릿 인자로 비교 함수 객체를 넘깁니다. 자세한 내용은 커스텀 키 타입 (map vs unordered_map)을 참고하세요.

unordered_map을 쓰는 경우

빠른 검색이 최우선일 때

std::unordered_map<int, User> users;
// O(1) 검색
auto it = users.find(userId);

unordered_map은 평균 O(1)에 find가 동작해, 키로 조회가 많을 때 map보다 유리합니다. “빠른 검색”이 최우선이고 정렬이 필요 없으면 unordered_map을 선택하면 됩니다.

순서가 중요하지 않을 때

std::unordered_map<std::string, int> wordCount;
wordCount["hello"]++;
wordCount["world"]++;
// 순서 상관없음

단어 빈도처럼 키로만 묶어서 집계하며, 출력 순서가 상관없을 때 unordered_map을 쓰면 됩니다. wordCount[hello]++처럼 없으면 0으로 초기화된 뒤 증가하므로, 카운팅에 자주 쓰는 패턴입니다.

정수/문자열 키를 사용할 때

// 기본 해시 함수 제공
std::unordered_map<int, int> m1;
std::unordered_map<std::string, int> m2;

int, std::string 등 표준 타입은 std::hash가 이미 특수화되어 있어서 별도 설정 없이 unordered_map의 키로 쓸 수 있습니다. 사용자 정의 타입은 해시 함수와 operator==를 제공해야 합니다.

커스텀 타입을 키로 쓰는 방법은 커스텀 키 타입 (map vs unordered_map) 섹션을 참고하세요.

reserve, try_emplace, operator[]와 at() 구분

팁 1: unordered_map에 reserve 사용

unordered_map도 삽입이 많아지면 버킷을 늘리며 재해싱이 일어납니다. 넣을 원소 개수를 대략 알면 reserve(n)으로 버킷 수를 미리 잡아 두면, 재해싱 횟수가 줄어들어 삽입이 더 빨라집니다.

std::unordered_map<int, int> m;
m.reserve(1000);  // 재해싱 방지

for (int i = 0; i < 1000; ++i) {
    m[i] = i;  // 재해싱 없음
}

unordered_map도 원소가 늘면 버킷을 늘리며 재해싱이 일어납니다. 넣을 개수를 대략 알면 reserve(n)으로 버킷 수를 미리 잡아 두면 재해싱 횟수가 줄어들어 삽입이 빨라집니다. vector의 reserve와 같은 개념입니다.

팁 2: emplace vs insert

insert({"key", "value"})는 pair 임시 객체를 만든 뒤 컨테이너에 넣습니다. emplace("key", "value")는 map이 내부에서 키와 값을 직접 생성하므로, pair 복사/이동이 없어 더 효율적일 수 있습니다. 이미 있는 키에 emplace를 해도 기존 원소는 그대로 두며, 새로 만든 값은 버려집니다.

std::map<std::string, std::string> m;

// insert: 임시 객체 생성
m.insert({"key", "value"});

// emplace: 직접 생성 (더 효율적)
m.emplace("key", "value");

insert({“key”, “value”})는 pair 임시 객체를 만든 뒤 넣으며, emplace(“key”, “value”)는 map 내부에서 키와 값을 직접 생성해 pair 복사/이동을 줄입니다. 이미 있는 키에 emplace를 해도 기존 원소는 유지되고 새로 만든 값은 버려집니다.

팁 3: try_emplace (C++17)

키가 이미 있으면 emplace는 값만 생성했다가 버리므로, 값 생성 비용이 크면 낭비입니다. try_emplace는 “키가 없을 때만” 값을 만들고 삽입합니다. 키가 있으면 두 번째 인자(값 생성에 쓰일 인자)는 사용하지 않아서, 무거운 객체를 넣을 때 유용합니다.

std::map<std::string, std::string> m;

// emplace: 키가 이미 있으면 값 생성 후 버림
m.emplace("key", "value1");
m.emplace("key", "value2");  // "value2" 생성 후 버림

// try_emplace: 키가 없을 때만 값 생성
m.try_emplace("key", "value1");
m.try_emplace("key", "value2");  // 값 생성 안 함

emplace는 키가 이미 있어도 값 쪽 인자를 사용해 객체를 만들었다가 버리므로, 값 생성 비용이 크면 낭비입니다. try_emplace는 키가 없을 때만 값을 만들고 삽입하며, 키가 있으면 값 생성 인자를 사용하지 않아 무거운 객체를 넣을 때 유리합니다.

팁 4: operator[] vs at()

operator[]는 키가 없으면 기본값을 삽입한 뒤 그 참조를 반환합니다. 따라서 “있는지 모르는 키”를 []로 읽기만 해도 map에 항목이 생깁니다. “없으면 예외”가 필요할 때는 at(key)를 쓰며, 없으면 std::out_of_range가 발생합니다. 조회만 하고 넣고 싶지 않을 때는 find로 반복자를 확인하는 편이 안전합니다.

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

// operator[]: 키가 없으면 기본값 삽입
int value1 = m["missing"];  // 0 삽입 후 반환

// at(): 키가 없으면 예외
try {
    int value2 = m.at("missing");  // 예외 발생
} catch (const std::out_of_range& e) {
    std::cerr << "Key not found\n";
}

operator[]는 키가 없으면 기본값(정수면 0)을 삽입한 뒤 그 참조를 반환하므로, 조회만 할 때도 항목이 생깁니다. at(key)는 키가 없으면 out_of_range 예외를 던져, “없으면 예외”가 필요할 때 사용합니다. 넣지 않고 조회만 할 때는 find로 반복자를 확인하는 편이 안전합니다.

팁 5: multimap/multiset

같은 키를 여러 번 넣어야 할 때는 std::multimap(또는 multiset)을 씁니다. equal_range(key)는 그 키를 가진 모든 원소 구간 [first, second)의 반복자 쌍을 반환하므로, 해당 키에 연결된 값들을 모두 순회할 수 있습니다.

// 중복 키 허용
std::multimap<std::string, int> scores;
scores.insert({"Alice", 90});
scores.insert({"Alice", 95});  // 중복 OK

// 특정 키의 모든 값 찾기
auto range = scores.equal_range("Alice");
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->second << " ";
}
// 90 95

multimap은 같은 키를 여러 개 가질 수 있습니다. equal_range(“Alice”)는 그 키를 가진 모든 원소 구간 [first, second)의 반복자 쌍을 반환하므로, 해당 키에 연결된 값들(90, 95)을 모두 순회할 수 있습니다. 한 키에 여러 값이 매핑될 때 사용합니다.

operator[]의 의도치 않은 삽입, 해시 충돌, 비교 함수 규칙 위반

문제 1: operator[]로 조회만 했는데 map에 항목이 생김

증상: “있는지 확인만 하려고” m[key]를 썼는데, 없던 키가 map에 0(또는 기본값)으로 추가됩니다.

원인: operator[]는 키가 없으면 기본값을 삽입한 뒤 그 참조를 반환합니다. 조회만 할 의도였어도 항목이 생깁니다.

해결법:

// ❌ m["key"] → 없으면 삽입됨
// ✅ auto it = m.find("key"); if (it != m.end()) ...
// ✅ C++20: if (m.contains("key")) ...

문제 2: unordered_map에 커스텀 타입을 키로 쓰려다 컴파일 에러

증상: std::unordered_map<MyStruct, int> m; 선언 시 “hash specialization” 관련 에러.

원인: unordered_map은 키에 대해 해시 함수와 operator==가 필요합니다. int, string 등은 std::hash가 있지만, 사용자 정의 타입은 직접 제공해야 합니다.

해결법:

struct MyKey {
    int id;
    std::string name;
    bool operator==(const MyKey& other) const {
        return id == other.id && name == other.name;
    }
};

// 방법 1: std::hash 특수화
namespace std {
    template <>
    struct hash<MyKey> {
        size_t operator()(const MyKey& k) const {
            return hash<int>()(k.id) ^ (hash<std::string>()(k.name) << 1);
        }
    };
}

// 방법 2: 해시 함수 객체를 템플릿 인자로 전달
struct MyKeyHash {
    size_t operator()(const MyKey& k) const {
        return std::hash<int>()(k.id) ^ (std::hash<std::string>()(k.name) << 1);
    }
};
std::unordered_map<MyKey, int, MyKeyHash> m;

operator==로 동등 비교가 가능해야 하며, 해시 함수는 같은 키에 대해 같은 값을 반환해야 합니다. std 네임스페이스에 특수화하거나, 세 번째 템플릿 인자로 해시 함수 객체를 넘깁니다.

문제 3: map 순회 중 erase하면 반복자 무효화

증상: for 루프 안에서 m.erase(it) 후 ++it를 하면 크래시 또는 미정의 동작.

원인: map에서 erase(it)를 호출하면 it가 무효화됩니다. 무효화된 반복자에 ++를 하면 안 됩니다.

해결법:

// ❌ 잘못된 사용: erase 후 it 무효화
for (auto it = m.begin(); it != m.end(); ++it) {
    if (it->second < 0) {
        m.erase(it);  // it 무효화!
        // ++it 시 미정의 동작
    }
}

// ✅ 올바른 사용: erase가 다음 반복자 반환
for (auto it = m.begin(); it != m.end(); ) {
    if (it->second < 0) {
        it = m.erase(it);  // 다음 반복자 받음
    } else {
        ++it;
    }
}

// ✅ C++11 이후: erase에 반복자 전달 시 다음 반복자 반환

map::erase(iterator)는 C++11부터 삭제된 원소의 다음 반복자를 반환합니다. it = m.erase(it)로 받아서 루프를 계속하면 안전합니다.

문제 4: unordered_map이 예상보다 느림 (해시 충돌)

증상: unordered_map을 썼는데 map보다 느리거나, 데이터가 많아질수록 급격히 느려짐.

원인: 키 분포가 나쁘면 해시 충돌이 많아져, 한 버킷에 원소가 몰려 최악 O(n)에 가까워집니다. 또는 reserve 없이 삽입하면 재해싱이 반복됩니다.

해결법:

// ✅ reserve로 재해싱 최소화
std::unordered_map<int, Data> m;
m.reserve(1000000);  // 넣을 개수 예상
for (int i = 0; i < 1000000; ++i) {
    m[i] = data;
}

// ✅ load_factor, max_load_factor로 버킷 수 조절 (고급)
m.max_load_factor(0.5);  // 버킷당 평균 0.5개 이하 유지
m.rehash(2000000);       // 버킷 수 미리 늘림

reserve로 넣을 개수를 미리 알려 주면 재해싱 횟수가 줄어듭니다. load_factor가 높으면 충돌이 많아지므로, max_load_factor를 낮추고 rehash로 버킷 수를 늘릴 수 있습니다.

문제 5: map의 operator[]가 값 타입을 기본 생성함

증상: std::map<K, BigObject>에서 m[key]로 접근할 때, 키가 없으면 BigObject()가 호출되어 비용이 큼.

원인: operator[]는 키가 없으면 값을 기본 생성해 삽입합니다. BigObject 생성이 무거우면 부담이 됩니다.

해결법:

// ❌ operator[]: 키 없으면 BigObject() 호출
BigObject& obj = m[key];  // 키 없으면 기본 생성 후 삽입

// ✅ try_emplace (C++17): 키 없을 때만 값 생성
auto [it, inserted] = m.try_emplace(key, arg1, arg2);
if (inserted) {
    // 새로 삽입됨
} else {
    // 이미 있었음, it->second 사용
}

// ✅ find + insert: 기존 패턴
auto it = m.find(key);
if (it == m.end()) {
    it = m.emplace(key, BigObject(arg1, arg2)).first;
}

try_emplace는 키가 없을 때만 값을 생성하므로, 무거운 객체를 넣을 때 operator[]보다 유리합니다. find로 먼저 확인한 뒤 없을 때만 emplace하는 패턴도 사용합니다.

문제 6: multimap에서 operator[] 사용 시도

증상: std::multimap에서 m[key]를 쓰려다 컴파일 에러.

원인: multimap은 같은 키에 여러 값이 매핑되므로 operator[]가 없습니다.

해결법: insert/emplace로 삽입하며, equal_range(key)로 같은 키의 모든 값을 순회합니다.

문제 7: 해시 함수에서 동등한 키가 다른 해시값 반환

증상: unordered_map에 넣은 키를 find로 찾지 못함.

원인: operator==가 true인 두 키에 대해 해시 함수가 다른 값을 반환하면 검색이 실패합니다.

해결법: a == b이면 반드시 hash(a) == hash(b)여야 합니다. 각 필드를 std::hash로 해시한 뒤 비트 연산으로 조합합니다.

문제 8: set/map의 비교 함수가 strict weak ordering 위반

증상: 런타임 크래시 또는 원소가 사라지거나 중복으로 보임.

원인: 비교 함수가 <=를 사용하거나 a < a가 true가 되면 미정의 동작입니다.

해결법: operator<만 사용하며, (a < b) && (b < a)가 동시에 true가 되면 안 됩니다.

문제 9: set/map에 포인터를 키로 넣었더니 내용이 같은 객체가 따로 저장됨

증상: std::set<Item*>에 내용이 같은 두 객체의 포인터를 넣었는데 원소가 두 개가 됩니다.

원인: 포인터 키는 가리키는 값이 아니라 주소로 비교됩니다. 주소 비교가 의도라면 문제없지만, 내용 기준 중복 제거를 기대했다면 비교 함수가 필요합니다. 이때 비교 기준 필드를 컨테이너에 들어간 뒤에 바꾸면 트리 순서가 깨지므로, 키로 쓰는 동안에는 그 필드를 바꾸지 않아야 합니다.

struct PtrValueLess {
    bool operator()(const int* a, const int* b) const { return *a < *b; }
};
std::set<int*, PtrValueLess> byValue;  // 가리키는 값 기준으로 정렬·중복 제거

문제 10: unordered_map을 순회하면서 원소를 추가함

증상: 순회 중 insert나 operator[]로 새 키를 넣었더니 일부 원소를 건너뛰거나 두 번 방문하고, 가끔 크래시가 납니다.

원인: erase는 지운 원소의 반복자만 무효화하므로 it = m.erase(it) 패턴은 unordered_map에서도 안전합니다. 문제는 삽입입니다. 삽입으로 재해싱이 일어나면 모든 반복자가 무효화되고, 재해싱이 없더라도 새 원소가 이미 지나간 버킷에 들어갈지 앞으로 방문할 버킷에 들어갈지 알 수 없습니다.

해결법: 순회 중에는 바꿀 내용을 따로 모아 두고, 순회가 끝난 뒤 한꺼번에 반영합니다.

std::vector<std::pair<int, int>> toAdd;
for (const auto& [k, v] : m) {
    if (v > 100) toAdd.emplace_back(k + 1000, v / 2);
}
for (auto& [k, v] : toAdd) m.emplace(k, v);

map과 unordered_map 사용 규칙 요약

  1. 조회만 할 때: operator[] 대신 find 또는 C++20 contains 사용. operator[]는 없으면 삽입합니다.
  2. 대량 삽입 시: unordered_map::reserve(expected_size)로 재해싱 최소화.
  3. 무거운 값 타입: try_emplace로 키 없을 때만 값 생성. operator[]는 기본 생성 후 대입합니다.
  4. 순회 중 삭제: it = m.erase(it)로 다음 반복자를 받아야 합니다. 무효화된 반복자에 ++ 금지.
  5. 범위 검색 필요: map/set의 lower_bound/upper_bound 사용. unordered_*에는 없습니다.
  6. 커스텀 키: map은 operator<만, unordered_map은 std::hash + operator== 필요. 해시 품질이 어려우면 map이 안전합니다.

스레드 안전 래퍼, TTL 캐시, 다중 인덱스 패턴

패턴 1: 스레드 안전 래퍼 (mutex + map)

여러 스레드가 같은 map에 접근할 때는 std::mutex로 보호합니다. 읽기 빈도가 높으면 shared_mutex로 읽기 동시 접근을 허용할 수 있습니다.

template <typename K, typename V>
class ThreadSafeMap {
    std::map<K, V> map_;
    mutable std::mutex mtx_;
public:
    std::optional<V> get(const K& key) const {
        std::lock_guard lock(mtx_);
        auto it = map_.find(key);
        return it != map_.end() ? std::optional(it->second) : std::nullopt;
    }
    void set(const K& key, V value) {
        std::lock_guard lock(mtx_);
        map_[key] = std::move(value);
    }
    bool erase(const K& key) {
        std::lock_guard lock(mtx_);
        return map_.erase(key) > 0;
    }
};

패턴 2: 설정 캐시 (map + TTL)

설정값을 메모리에 캐시하며, 일정 시간 후 만료시키는 패턴입니다. 값과 함께 타임스탬프를 저장하며, 조회 시 TTL을 초과하면 삭제 후 nullopt를 반환합니다.

template <typename K, typename V>
class ConfigCache {
    std::map<K, std::pair<V, std::chrono::steady_clock::time_point>> cache_;
    std::chrono::seconds ttl_;
public:
    explicit ConfigCache(std::chrono::seconds ttl) : ttl_(ttl) {}
    std::optional<V> get(const K& key) {
        auto it = cache_.find(key);
        if (it == cache_.end()) return std::nullopt;
        if (std::chrono::steady_clock::now() - it->second.second > ttl_) {
            cache_.erase(it);
            return std::nullopt;
        }
        return it->second.first;
    }
    void set(const K& key, V value) {
        cache_[key] = {value, std::chrono::steady_clock::now()};
    }
};

패턴 3: 다중 인덱스 (map + 보조 map)

같은 데이터를 여러 키로 조회할 때, 키별로 map을 따로 유지합니다. ID로 조회하는 map과 이메일로 ID를 찾는 map을 함께 유지하며, 삽입·삭제 시 두 map을 동기화합니다.

struct User { int id; std::string email; std::string name; };

class UserStore {
    std::map<int, User> by_id_;
    std::map<std::string, int> email_to_id_;
public:
    void add(User u) {
        by_id_[u.id] = u;
        email_to_id_[u.email] = u.id;
    }
    std::optional<User> getById(int id) const {
        auto it = by_id_.find(id);
        return it != by_id_.end() ? std::optional(it->second) : std::nullopt;
    }
    std::optional<User> getByEmail(const std::string& email) const {
        auto it = email_to_id_.find(email);
        return it != email_to_id_.end() ? getById(it->second) : std::nullopt;
    }
};

패턴 4: 히트맵/통계 (unordered_map + 원자 카운터)

동시에 여러 스레드가 카운트를 올릴 때 값 타입을 std::atomic으로 둡니다. 이 방식이 락 없이 안전한 것은 맵의 구조가 바뀌지 않을 때뿐입니다. 모든 키를 시작 전에 넣어 두고 이후에는 find로 찾아 ++만 한다면 여러 스레드가 동시에 올려도 됩니다. 실행 중에 새 키를 추가해야 한다면 추가하는 쪽만 mutex를 잡는 것으로는 부족합니다. 삽입이 재해싱을 일으키면 락 없이 find하던 다른 스레드가 해제된 버킷을 읽게 되므로, 조회하는 쪽도 같은 락(읽기가 많다면 std::shared_mutex의 공유 락)을 잡아야 합니다.

패턴 5: 설정 관리자 (map + 기본값)

설정 조회에 operator[]를 쓰면 없는 키가 빈 값으로 삽입되어 설정이 오염됩니다. 조회는 find로만 하고, 없을 때의 동작을 optional이나 기본값 인자로 호출하는 쪽이 정하게 합니다.

#include <map>
#include <optional>
#include <string>

class ConfigManager {
    std::map<std::string, std::string> config_;
public:
    void set(const std::string& key, const std::string& value) { config_[key] = value; }

    std::optional<std::string> get(const std::string& key) const {
        auto it = config_.find(key);
        if (it == config_.end()) return std::nullopt;
        return it->second;
    }

    std::string getOrDefault(const std::string& key, const std::string& fallback) const {
        auto it = config_.find(key);
        return it != config_.end() ? it->second : fallback;
    }
};

get이 const 멤버 함수라서 실수로 operator[]를 쓰면 컴파일 에러가 납니다. 조회 경로를 const로 만들어 두면 이런 오염을 컴파일러가 막아 줍니다.

LRU 캐시, 이벤트 로그, 단어 빈도 집계 예시

예시 1: LRU 캐시 (unordered_map + list)

키로 빠르게 찾으며, “최근 사용” 순서를 유지해야 할 때는 unordered_map과 list를 조합합니다.

#include <unordered_map>
#include <list>

template <typename K, typename V>
class LRUCache {
    size_t capacity_;
    std::list<std::pair<K, V>> list_;
    std::unordered_map<K, typename std::list<std::pair<K, V>>::iterator> map_;

public:
    explicit LRUCache(size_t cap) : capacity_(cap) {}

    V* get(const K& key) {
        auto it = map_.find(key);
        if (it == map_.end()) return nullptr;
        list_.splice(list_.begin(), list_, it->second);
        return &it->second->second;
    }

    void put(const K& key, const V& value) {
        auto it = map_.find(key);
        if (it != map_.end()) {
            it->second->second = value;
            list_.splice(list_.begin(), list_, it->second);
            return;
        }
        if (list_.size() >= capacity_) {
            map_.erase(list_.back().first);
            list_.pop_back();
        }
        list_.emplace_front(key, value);
        map_[key] = list_.begin();
    }
};

unordered_map으로 O(1) 검색, list로 “맨 앞 = 최근 사용” 순서를 유지합니다. get/put 시 해당 항목을 list 맨 앞으로 옮기고, 용량 초과 시 맨 뒤(가장 오래된 것)를 제거합니다.

예시 2: 시간순 이벤트 로그 (map)

타임스탬프를 키로 하고 “특정 구간 이벤트”를 찾을 때 map의 lower_bound/upper_bound가 유리합니다.

std::map<Timestamp, std::string> eventLog;
void getEventsInRange(Timestamp start, Timestamp end) {
    auto it_start = eventLog.lower_bound(start);
    auto it_end = eventLog.upper_bound(end);
    for (auto it = it_start; it != it_end; ++it)
        std::cout << it->second << "\n";
}

예시 3: 단어 빈도 집계 (unordered_map)

순서 없이 “키별 개수”만 빠르게 세면 unordered_map이 적합합니다. counts[word]++는 키가 없으면 0으로 초기화된 뒤 1 증가합니다.

std::unordered_map<std::string, size_t> countWords(const std::string& text) {
    std::unordered_map<std::string, size_t> counts;
    for (std::istringstream iss(text); std::string word; iss >> word)
        counts[word]++;
    return counts;
}

자주 묻는 질문 (FAQ)

  • Q. map과 unordered_map 중 무엇을 기본으로 쓰나요? A. 키 순서대로 순회하거나 lower_bound·upper_bound로 범위를 찾아야 하면 map, 단건 조회·삽입만 많으면 평균 O(1)인 unordered_map이 유리합니다. 다만 unordered_map은 키에 대한 해시 함수가 필요하고, 해시가 한쪽으로 몰리면 최악 O(n)까지 느려질 수 있습니다.
  • Q. 선행으로 읽으면 좋은 글은? A. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.
  • Q. 더 깊이 공부하려면? A. cppreference를 참고하세요.

다음 글: C++ 실전 가이드 #10-3: STL 알고리즘

같이 보면 좋은 글