이 내용을 실무에서 언제 쓰나요?

C++ STL map·set·unordered_map 완벽 가이드. Red-Black Tree vs Hash Table 내부 구조, 시간 복잡도 O(log n) vs O(1), 정렬 필요 여부, 해시 충돌 처리, multimap·multiset 사용 시점 등. 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

선행으로 읽으면 좋은 글은?

각 글 하단의 이전 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

더 깊이 공부하려면?

cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

[2026] C++ map vs unordered_map (STL 시리즈) | 어떤 걸 써야 하죠? 선택 기준과 성능 비교

2026년 2월 23일 · 22분 읽기 · 수정 2026년 4월 7일 중급 개념

이 글의 핵심

C++ map vs unordered_map (STL 시리즈): 어떤 걸 써야 하죠? 선택 기준…. map을 썼는데 왜 이렇게 느릴까?부터 핵심 개념·패턴·실무 함정을 코드 예제로 풉니다.

🎯 이 글을 읽으면 (읽는 시간: 22분)

TL;DR: C++ STL의 map과 unordered_map을 완벽하게 이해하고 올바르게 선택합니다. O(log n) vs O(1), 정렬 vs 해시, 실무 성능 최적화까지 마스터합니다. 이 글을 읽으면:

✅ map (Red-Black Tree) vs unordered_map (Hash Table) 완벽 이해
✅ 시간복잡도 O(log n) vs O(1) 선택 기준 마스터
✅ 정렬 필요 여부에 따른 최적 컨테이너 선택 실무 활용:
🔥 빠른 검색 (사용자 조회, 캐싱)
🔥 정렬된 데이터 관리 (범위 쿼리)
🔥 성능 최적화 (100만 개 데이터 처리) 난이도: 중급 | 실습 코드: 15개 | 성능 비교: 포함

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

“100만 개 데이터 검색이 너무 느려요”

사용자 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으로 바꿨을 때 체감이 크게 나았습니다. 아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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으로 해결: 아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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) ≈ 1번 비교

위 코드 설명: std::unordered_map은 해시 테이블이라 평균 O(1)에 검색됩니다. 키 순서는 보장되지 않지만, “키로만 조회”가 목적이면 map보다 훨씬 빠르고, 100만 개 기준으로 검색 속도가 수 배~수십 배 차이 날 수 있습니다. 결과: 검색 속도 10배 이상 빠름 주의: unordered_map은 키의 순서가 보장되지 않습니다. “키 크기 순으로 순회”나 “가장 작은 키”가 필요하면 map/set을 써야 하고, “키로만 빠르게 찾기”가 목적이면 unordered_map이 적합합니다. 해시 충돌이 많으면 최악의 경우 O(n)이 될 수 있어, 키 분포가 나쁘면 map이 더 나을 수도 있습니다. 이 글을 읽으면:

map, set, unordered_map의 내부 구조를 이해할 수 있습니다.
각 컨테이너의 시간 복잡도를 알 수 있습니다.
상황에 맞는 컨테이너를 선택할 수 있습니다.
실전에서 성능을 최적화할 수 있습니다.

추가 문제 시나리오

시나리오 1: 실시간 순위 시스템
게임 점수판에서 “상위 10명”을 자주 조회해야 합니다. unordered_map은 순서가 없어 매번 전체를 정렬해야 하고, std::map은 begin()부터 순회하거나 rbegin()으로 역순 순회가 가능해 O(k)에 상위 k명을 얻을 수 있습니다. 시나리오 2: 시간대별 이벤트 조회
로그 시스템에서 “2024-01-01 10:00~11:00 사이 이벤트”를 찾을 때, map의 lower_bound/upper_bound로 구간 검색이 O(log n)에 가능합니다. unordered_map은 이런 범위 검색을 지원하지 않아 전체 순회가 필요합니다. 시나리오 3: 중복 제거 후 정렬 출력
파일에서 단어를 읽어 중복을 제거하고 알파벳 순으로 출력할 때, std::set을 쓰면 삽입 시 자동 정렬·중복 제거가 되고, unordered_set은 중복 제거만 되고 정렬하려면 별도 vector로 복사 후 정렬해야 합니다. 시나리오 4: 해시 충돌로 인한 성능 저하
unordered_map에 커스텀 키를 넣을 때 해시 함수가 나쁘면(예: 항상 같은 값 반환) 한 버킷에 몰려 최악 O(n)이 됩니다. map은 키 분포와 무관하게 O(log n)을 보장합니다. 시나리오 5: operator[]로 의도치 않은 삽입
”키가 있는지 확인만 하려고” if (m[key] > 0)을 썼는데, 없던 키가 0으로 삽입되어 map 크기가 커지고, 나중에 “왜 이 키가 있지?” 하는 버그가 발생합니다. 실무 적용 경험: 이 글은 대규모 C++ 프로젝트에서 실제로 겪은 문제와 해결 과정을 바탕으로 작성되었습니다. 책이나 문서에서 다루지 않는 실전 함정과 디버깅 팁을 포함합니다.

std::map과 std::set
std::unordered_map과 std::unordered_set
find·insert·erase 완전 가이드
lower_bound·upper_bound 범위 검색
커스텀 키 타입 (map vs unordered_map)
시간 복잡도 비교
컨테이너 선택 가이드
실전 최적화 팁
자주 발생하는 문제와 해결법
베스트 프랙티스
프로덕션 패턴

map vs unordered_map 선택 흐름도

아래 코드는 mermaid를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

flowchart TD
    A[키-값 저장 필요] --> B{정렬된 순서가\n필요한가?}
    B -->|예| C[map / set]
    B -->|아니오| D{범위 검색\nlower_bound 등?}
    D -->|예| C
    D -->|아니오| E{빠른 검색이\n최우선인가?}
    E -->|예| F[unordered_map / unordered_set]
    E -->|아니오| G{데이터 양이\n적은가?}
    G -->|예| H["둘 다 가능br/map이 더 단순"]
    G -->|아니오| F

위 다이어그램 설명: 정렬·범위 검색이 필요하면 map/set, 키로만 빠르게 찾고 순서가 무관하면 unordered_map/unordered_set을 선택합니다. 데이터가 적으면 map도 충분하고, 대량이면 unordered가 유리합니다.

1. std::map과 std::set

map: 키-값 쌍 저장

std::map은 키-값 쌍을 저장하고, 키 기준으로 자동 정렬됩니다. operator[]로 키를 넣거나 조회할 수 있고, 없던 키를 []로 접근하면 기본 생성된 값이 삽입됩니다. find는 반복자를 반환하므로 end()와 비교해 존재 여부를 확인한 뒤 it->first, it->second로 키와 값에 접근합니다. 순회하면 키가 정렬된 순서로 나옵니다. 다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 복사해 붙여넣은 뒤: 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을 반환하므로 존재 여부 확인에 쓸 수 있고, 순회하면 정렬된 순서로 원소를 얻습니다. 다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 복사해 붙여넣은 뒤: 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

아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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

특징:

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

Red-Black Tree 동작 시각화

다음은 mermaid를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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)이고, 중위 순회 시 키가 정렬된 순서로 나옵니다.

2. std::unordered_map과 std::unordered_set

unordered_map: 해시 테이블

std::unordered_map은 해시 테이블 기반이라 키 순서가 유지되지 않습니다. 삽입·삭제·검색이 평균 O(1)이라, 키로만 빠르게 찾으면 되고 순서가 필요 없을 때 map보다 유리합니다. 사용법은 map과 비슷하지만, for로 순회할 때 나오는 순서는 구현에 따라 달라지며 예측하지 않는 것이 좋습니다. 다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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)로 유리합니다.

해시 테이블 내부 구조

다음은 간단한 text 코드 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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

특징:

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

해시 테이블 동작 시각화

아래 코드는 mermaid를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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)이 됩니다.

3. find·insert·erase 완전 가이드

map/set의 find·insert·erase

std::map과 std::set에서 검색·삽입·삭제는 모두 O(log n)입니다. find는 반복자를, insert는 (반복자, 성공 여부) 쌍을, erase는 삭제된 개수(또는 다음 반복자)를 반환합니다. 다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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"})`로 “삽입 시도 후 반복자 얻기” 패턴에 자주 씁니다.

4. 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에서 같은 키를 가진 모든 원소를 순회할 때 유용합니다. 다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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에서는 같은 키에 여러 값이 매핑되므로, 이 구간을 순회해 모두 처리할 수 있습니다.

실전 예: 점수 구간별 조회

아래 코드는 cpp를 사용한 구현 예제입니다. 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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`로 “해당 점수보다 큰 첫 경계”를 찾고, 한 칸 왼쪽으로 가면 해당 구간의 등급을 얻습니다.

5. 커스텀 키 타입 (map vs unordered_map)

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

std::map의 키는 비교 가능해야 합니다. operator<가 있거나, 세 번째 템플릿 인자로 비교 함수 객체를 넘깁니다. 아래 코드는 cpp를 사용한 구현 예제입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며. 코드를 직접 실행해보면서 동작을 확인해보세요.

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==)가 필요합니다. 아래 코드는 cpp를 사용한 구현 예제입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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==`가 필요합니다.

6. 시간 복잡도 비교

연산별 시간 복잡도

연산	map/set	unordered_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를 수행하면 map은 약 500ms, unordered_map은 약 150ms로 수 배 차이가 납니다. 다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 벤치마크 예시: 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이 유리합니다.

일상 비유로 이해하기: 시간 복잡도는 책에서 원하는 페이지를 찾는 방법으로 비유할 수 있습니다. O(1)은 목차를 보고 바로 찾기, O(log n)은 이진 탐색처럼 중간을 펼쳐 앞뒤 판단하기, O(n)은 첫 페이지부터 하나씩 넘기기, O(n²)은 모든 페이지 조합을 확인하기입니다.

7. 컨테이너 선택 가이드

map을 쓰는 경우

✅ 정렬된 순서가 필요할 때 map은 키를 기준으로 항상 정렬된 상태를 유지하므로, “키 순서대로 출력”하거나 “가장 작은/큰 키”를 쓰는 연산에 적합합니다. 아래처럼 점수를 넣으면 이름(키) 알파벳 순으로 순회할 수 있습니다. 아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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 이하”인 키만 순회하려면 아래처럼 구간 반복자를 구한 뒤 그 사이를 돌면 됩니다. 다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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의 세 번째 템플릿 인자로 비교 함수 객체를 넘깁니다. 자세한 내용은 5. 커스텀 키 타입을 참고하세요.

unordered_map을 쓰는 경우

✅ 빠른 검색이 최우선일 때

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

위 코드 설명: unordered_map은 평균 O(1)에 find가 동작해, 키로 조회가 많을 때 map보다 유리합니다. “빠른 검색”이 최우선이고 정렬이 필요 없으면 unordered_map을 선택하면 됩니다. ✅ 순서가 중요하지 않을 때 다음은 간단한 cpp 코드 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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==를 제공해야 합니다. 커스텀 타입을 키로 쓰는 방법은 5. 커스텀 키 타입 섹션을 참고하세요.

5. 실전 최적화 팁

팁 1: unordered_map에 reserve 사용

unordered_map도 삽입이 많아지면 버킷을 늘리며 재해싱이 일어납니다. 넣을 원소 개수를 대략 알면 reserve(n)으로 버킷 수를 미리 잡아 두면, 재해싱 횟수가 줄어들어 삽입이 더 빨라집니다. 아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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를 해도 기존 원소는 그대로 두고, 새로 만든 값은 버려집니다. 아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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는 “키가 없을 때만” 값을 만들고 삽입합니다. 키가 있으면 두 번째 인자(값 생성에 쓰일 인자)는 사용하지 않아서, 무거운 객체를 넣을 때 유용합니다. 아래 코드는 cpp를 사용한 구현 예제입니다. 에러 처리를 통해 안정성을 확보합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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로 반복자를 확인하는 편이 안전합니다. 아래 코드는 cpp를 사용한 구현 예제입니다. 비동기 처리를 통해 효율적으로 작업을 수행합니다, 에러 처리를 통해 안정성을 확보합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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)의 반복자 쌍을 반환하므로, 해당 키에 연결된 값들을 모두 순회할 수 있습니다. 아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 중복 키 허용
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)을 모두 순회할 수 있습니다. 한 키에 여러 값이 매핑될 때 사용합니다.

9. 자주 발생하는 문제와 해결법

문제 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가 있지만, 사용자 정의 타입은 직접 제공해야 합니다. 해결법: 다음은 cpp를 활용한 상세한 구현 코드입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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가 무효화됩니다. 무효화된 반복자에 ++를 하면 안 됩니다. 해결법: 다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// ❌ 잘못된 사용: 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 없이 삽입하면 재해싱이 반복됩니다. 해결법: 아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// ✅ 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 생성이 무거우면 부담이 됩니다. 해결법: 다음은 cpp를 활용한 상세한 구현 코드입니다. 에러 처리를 통해 안정성을 확보합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// ❌ 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가 되면 안 됩니다.

10. 베스트 프랙티스

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

11. 프로덕션 패턴

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

여러 스레드가 같은 map에 접근할 때는 std::mutex로 보호합니다. 읽기 빈도가 높으면 shared_mutex로 읽기 동시 접근을 허용할 수 있습니다. 다음은 cpp를 활용한 상세한 구현 코드입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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를 반환합니다. 다음은 cpp를 활용한 상세한 구현 코드입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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을 동기화합니다. 다음은 cpp를 활용한 상세한 구현 코드입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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`을 사용합니다. 기존 키에 대한 `++`는 atomic으로 스레드 안전하고, 새 키 추가 시에만 mutex가 필요합니다. 키가 미리 알려진 경우 `reserve`로 넣어 두면 lock 경합이 줄어듭니다.

실전 예시: 캐시·로그·설정 관리

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

키로 빠르게 찾고, “최근 사용” 순서를 유지해야 할 때는 unordered_map과 list를 조합합니다. 다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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가 유리합니다. 아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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 증가합니다. 아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

// 실행 예제
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;
}

정리

항목	map/set	unordered_map/set
내부 구조	Red-Black Tree	Hash Table
정렬	✅ 자동 정렬	❌ 순서 없음
검색 속도	O(log n)	O(1) 평균
범위 검색	✅ 가능	❌ 불가
메모리	노드 오버헤드	버킷 배열
사용 시점	정렬/범위 필요	빠른 검색 필요
선택 기준:

정렬 필요 → map/set
빠른 검색 → unordered_map/unordered_set
범위 검색 → map/set
순서 무관 → unordered_map/unordered_set

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요? A. Red-Black Tree vs Hash Table, O(log n) vs O(1), 정렬 필요 여부, 해시 충돌 처리, multimap 사용 시점 등. 본문 예제와 선택 가이드를 참고하세요.
Q. 선행으로 읽으면 좋은 글은? A. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.
Q. 더 깊이 공부하려면? A. cppreference를 참고하세요. 한 줄 요약: map·set은 정렬/유일 키, unordered_map은 O(1) 조회에 적합합니다. 다음 글: C++ 실전 가이드 #10-3: STL 알고리즘

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.