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

· 22분 읽기 · 수정 중급 개념
C++ map vs unordered_map (STL 시리즈) | "어떤 걸 써야 하죠?" 선택 기준과 성능 비교

이 글의 핵심

C++ map vs unordered_map (STL 시리즈)에 대한 실전 가이드입니다.

들어가며: 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으로 바꿨을 때 체감이 크게 나았습니다.

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) ≈ 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 크기가 커지고, 나중에 “왜 이 키가 있지?” 하는 버그가 발생합니다.

목차

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

map vs unordered_map 선택 흐름도

flowchart TD
    A[키-값 저장 필요] --> B{정렬된 순서가<br/>필요한가?}
    B -->|예| C[map / set]
    B -->|아니오| D{범위 검색<br/>lower_bound 등?}
    D -->|예| C
    D -->|아니오| E{빠른 검색이<br/>최우선인가?}
    E -->|예| F[unordered_map / unordered_set]
    E -->|아니오| G{데이터 양이<br/>적은가?}
    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로 키와 값에 접근합니다. 순회하면 키가 정렬된 순서로 나옵니다.

// 복사해 붙여넣은 뒤: 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)이고, 중위 순회 시 키가 정렬된 순서로 나옵니다.

2. std::unordered_map과 std::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)이 됩니다.

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

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

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에서 같은 키를 가진 모든 원소를 순회할 때 유용합니다.

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

5. 커스텀 키 타입 (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==가 필요합니다.

6. 시간 복잡도 비교

연산별 시간 복잡도

연산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를 수행하면 map은 약 500ms, unordered_map은 약 150ms로 수 배 차이가 납니다.

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

7. 컨테이너 선택 가이드

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

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==를 제공해야 합니다.

커스텀 타입을 키로 쓰는 방법은 5. 커스텀 키 타입 섹션을 참고하세요.

5. 실전 최적화 팁

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

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가 있지만, 사용자 정의 타입은 직접 제공해야 합니다.

해결법:

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

10. 베스트 프랙티스

  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이 안전합니다.

11. 프로덕션 패턴

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

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

예시 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;
}

정리

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

선택 기준:

  1. 정렬 필요 → map/set
  2. 빠른 검색 → unordered_map/unordered_set
  3. 범위 검색 → map/set
  4. 순서 무관 → 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 알고리즘

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

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

  • C++ 코딩 테스트 | “백준·프로그래머스” 알고리즘 유형별 STL 활용법
  • C++ STL 알고리즘 | sort·find·transform 람다와 함께 쓰기 (실전 패턴)
  • C++ auto와 decltype | 타입 추론으로 코드 간결하게 만드는 방법

이 글에서 다루는 키워드 (관련 검색어)

C++, STL, std::map, std::set, unordered_map, unordered_set, Red-Black-Tree, Hash-Table, 해시테이블, 시간복잡도 등으로 검색하시면 이 글이 도움이 됩니다.

관련 글

  • C++ vector 성능 |
  • C++ STL 알고리즘 | sort·find·transform 람다와 함께 쓰기 (실전 패턴)
  • C++ map·set 완벽 가이드 | ordered vs unordered· 커스텀 키
  • C++ 람다 기초 완벽 가이드 | 캡처·mutable·제네릭 람다와 실전 패턴
  • C++ 람다 심화 | 초기화 캡처·완벽 전달·IIFE·재귀 람다와 실전 패턴
... 996 lines not shown ... Token usage: 63706/1000000; 936294 remaining Start-Sleep -Seconds 3