pkglog

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

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

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

사용자 ID로 정보를 조회하는 시스템을 std::map으로 만들면, 데이터가 많아질수록 조회가 병목이 되는 경우가 있습니다. std::map은 내부가 레드-블랙 트리(삽입·삭제 후에도 높이가 O(log n)으로 유지되는 균형 이진 탐색 트리)라서 삽입·검색·삭제가 모두 O(log n)입니다. 원소가 100만 개면 find 한 번에 대략 log₂(10⁶) ≈ 20번 비교합니다.

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::unordered_map(해시 테이블: 키를 해시값으로 바꿔 버킷에 넣는 구조)으로 바꿔 평균 O(1) 검색을 쓸 수 있습니다. 반대로 키 순서대로 순회하거나 “가장 작은/큰 키”, 구간 검색이 필요하면 map·set이 맞습니다. 이 글은 10-1 vector·string에 이어지는 내용입니다.

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): 해시 계산 + 버킷 한 곳 확인

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

순서가 필요한 상황들

게임 점수판에서 “상위 10명”을 자주 조회해야 한다면, 순서가 없는 unordered_map은 매번 전체를 훑어 정렬하거나 std::partial_sort로 골라내야 합니다. 점수를 키로 하는 std::multimap(같은 점수가 여럿일 수 있으므로)이라면 rbegin()부터 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로 복사해 정렬해야 합니다.

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";
    }
}

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

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
}

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

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 <iostream>
#include <string>
#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 등)
}

unordered_set: 해시 집합

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

#include <iostream>
#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 (예시, 실제 순서는 다를 수 있음)
}

해시 테이블 내부 구조

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[]와 at()은 map과 unordered_map에만 있으며 set 계열과 multimap에는 없습니다.

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);  // 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이면 동일 키로 간주되므로, 위 예제처럼 나이만 비교하면 이름이 달라도 나이가 같은 두 사람은 같은 키가 되어 뒤의 삽입이 무시됩니다. 구분해야 하는 필드를 모두 비교하려면 std::tie(age, name) < std::tie(other.age, other.name)처럼 씁니다.

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> 특수화가 해시값 계산을 맡습니다. 여기서 쓴 XOR 조합은 간단하지만 분포가 좋지 않으므로, 실제로는 아래 복합 키 절의 방식을 쓰는 편이 낫습니다.

set의 커스텀 키

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

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

(id, name)처럼 필드가 여러 개인 키는 각 필드의 해시를 하나로 합쳐야 합니다. 흔히 보이는 h1 ^ (h2 << 1)은 동작은 하지만, libstdc++처럼 std::hash<int>가 값을 그대로 돌려주는 구현에서는 (0, 1)과 (2, 0)이 모두 2가 되는 식으로 작은 정수 조합끼리 쉽게 충돌합니다. 시프트 없는 h1 ^ h2라면 필드 순서만 바뀐 키가 항상 충돌하고, 두 값이 같으면 0이 됩니다. 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)이라 상대적으로 일정합니다. 다만 실제 수치는 키 분포, 컴파일러, 최적화 옵션, 하드웨어에 따라 크게 달라지므로 아래처럼 직접 재 보는 것이 정확합니다.

// g++ -std=c++17 -O2 bench.cpp
#include <chrono>
#include <iostream>
#include <map>
#include <unordered_map>

int main() {
    constexpr int N = 1000000;
    std::map<int, int> m1;
    std::unordered_map<int, int> m2;
    m2.reserve(N);  // unordered_map은 reserve로 재해싱 최소화
    long long sum = 0;  // 조회 결과를 사용해야 컴파일러가 find를 지우지 않음

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

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

    std::cout << "map: " << t1 << " ms, unordered_map: " << t2 << " ms (" << sum << ")\n";
}

이 코드의 키는 0부터 순서대로 증가하는 정수라 두 컨테이너 모두에 유리한 조건입니다. map은 순서대로 삽입하면 새 노드가 늘 트리의 오른쪽 끝에 붙고 조회 경로도 캐시에 잘 남으며, std::hash<int>가 값을 그대로 돌려주는 구현에서는 해시 분포도 완벽합니다. 실제 서비스의 키(무작위 ID, 문자열)로 바꿔 재면 결과가 달라질 수 있습니다.

C++23 flat_map: 정렬된 배열 위의 map

C++23의 std::flat_map(<flat_map> 헤더)은 노드를 할당하는 트리 대신, 키와 값을 각각 정렬된 연속 컨테이너(기본은 std::vector)에 담는 컨테이너 어댑터입니다. 검색은 map처럼 이진 탐색이라 O(log n)이지만, 원소가 메모리에 연속으로 있어 캐시 효율이 좋아 조회와 순회가 빠른 경우가 많고 노드마다 붙는 포인터 오버헤드도 없습니다.

#include <flat_map>
#include <iostream>
#include <string>

int main() {
    std::flat_map<int, std::string> fm;
    fm.emplace(3, "c");
    fm.emplace(1, "a");
    fm.emplace(2, "b");

    for (const auto& [k, v] : fm) {      // 키 순서: 1 2 3
        std::cout << k << "=" << v << " ";
    }
    if (auto it = fm.find(2); it != fm.end()) {
        std::cout << "\nfound " << it->second << "\n";
    }
}

대가는 쓰기 쪽에 있습니다. 중간에 삽입하거나 삭제하면 뒤 원소를 모두 밀어야 하므로 O(n)이고, 삽입·삭제 후에는 다른 원소의 반복자와 참조가 무효화될 수 있습니다. 또 키와 값이 따로 저장되므로 반복자를 역참조하면 std::pair<const Key&, T&> 같은 프록시가 나오고, auto&로는 받을 수 없어 위 예제처럼 const auto&나 auto로 받아야 합니다. 원소를 한 번에 모아 만든 뒤 주로 읽는 데이터(설정 테이블, 정적 매핑)에 잘 맞고, 이미 정렬된 데이터라면 std::sorted_unique 태그를 넘겨 정렬 과정을 건너뛸 수 있습니다. 표준 라이브러리 구현마다 지원 시점이 다르므로, 쓰기 전에 사용하는 컴파일러에서 <flat_map>이 제공되는지 확인해야 합니다. 그 전까지는 정렬된 std::vector<std::pair<K, V>>에 std::lower_bound를 쓰거나 Boost.Container의 flat_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에서는 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

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

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

unordered_map을 쓰는 경우

빠른 검색이 최우선일 때

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

순서가 중요하지 않을 때

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;  // 재해싱 없음
}

팁 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");

팁 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");  // 값 생성 안 함

팁 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";
}

팁 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

set·unordered_set에서 자주 쓰는 패턴

순서를 유지한 중복 제거

set에 넣었다 꺼내거나 정렬 후 std::unique를 쓰면 원래 순서가 사라집니다. 순서를 지키려면 unordered_set<int> seen;을 두고 if (seen.insert(x).second) out.push_back(x);처럼 처음 본 값만 결과에 넣습니다. insert가 돌려주는 pair의 second가 “새로 들어갔는가”를 알려 주므로 count로 한 번 더 찾을 필요가 없습니다.

집합 연산

std::set_intersection·set_union·set_difference는 두 범위가 정렬되어 있다는 전제가 있어 set의 반복자는 그대로 넘길 수 있지만, unordered_set에 쓰면 컴파일은 되고 결과만 틀립니다. 해시 집합끼리는 작은 쪽을 순회하며 큰 쪽에 contains로 포함 여부를 확인하는 편이 간단합니다.

문자열 키의 이질적 조회

키가 std::string이면 find("literal")이나 find(sv)가 매번 임시 std::string을 만듭니다(긴 문자열이면 힙 할당). 정렬 컨테이너는 C++14부터 비교자를 std::less<>로 두면 변환 없이 조회하고, 해시 컨테이너는 C++20부터 해시와 동등 비교 둘 다 is_transparent를 가져야 합니다.

struct SVHash {
    using is_transparent = void;
    std::size_t operator()(std::string_view sv) const noexcept {
        return std::hash<std::string_view>{}(sv);
    }
};
std::set<std::string, std::less<>> ordered;                       // C++14
std::unordered_set<std::string, SVHash, std::equal_to<>> hashed;  // C++20
bool has(std::string_view key) { return hashed.contains(key); }   // 임시 string 없음

std::hash<std::string>과 std::hash<std::string_view>는 같은 문자열에 같은 값을 내도록 규정되어 있어 이 조합이 동작합니다. 둘 중 하나라도 is_transparent가 빠지면 이질적 조회가 꺼집니다. 이때 문자열 리터럴로 조회하면 조용히 임시 std::string을 만들고, std::string_view로 조회하면 std::string으로의 변환이 explicit이라 컴파일 에러가 납니다. 성능이 목적이라면 할당이 실제로 사라졌는지 프로파일러로 확인합니다. map·unordered_map도 같은 규칙입니다.

키 바꾸기와 노드 이동(C++17)

set의 원소와 map의 키는 const라 직접 고칠 수 없습니다. auto nh = s.extract(2); nh.value() = 5; s.insert(std::move(nh));처럼 노드를 떼어 내 수정하면 새 할당 없이 키를 바꿀 수 있고(map은 nh.key()), a.merge(b)는 b의 노드를 복사 없이 a로 옮기되 a에 이미 있는 키의 노드는 b에 남깁니다. 해시 컨테이너에서는 노드를 다시 insert하는 순간 로드 팩터를 넘으면 재해시가 일어나 다른 반복자가 무효화될 수 있습니다.

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)여야 합니다. operator==가 비교하는 필드와 정확히 같은 필드만 해시에 넣고, 조합은 복합 키 절의 hash_combine 방식을 씁니다.

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

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

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

해결법: 비교 함수는 <=가 아니라 <처럼 동작해야 합니다. comp(a, a)는 항상 false여야 하고, comp(a, b)와 comp(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);

스레드 안전 래퍼, 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;
    std::istringstream iss(text);  // #include <sstream>
    std::string word;
    while (iss >> word) counts[word]++;
    return counts;
}

다음 글: C++ STL 알고리즘 기초

참고 자료

같이 보면 좋은 글