C++ map·set 완벽 가이드 | ordered vs unordered· 커스텀 키
이 글의 핵심
std::map, std::set, unordered_map, unordered_set 완벽 가이드. Red-Black Tree vs Hash Table, 커스텀 키 타입, 문제 시나리오, 자주 발생하는 에러, 성능 팁, 프로덕션 패턴까지 실전 중심으로 설명합니다.
들어가며: map을 썼는데 왜 이렇게 느릴까?
“100만 개 데이터 검색이 너무 느려요”
사용자 ID로 정보를 조회하는 시스템을 만들었습니다. std::map을 사용했는데 데이터가 많아지자 느려졌습니다.
문제의 코드:
// 문제: std::map은 O(log n)이라 대량 데이터에서 느림
struct User {
int id;
std::string name;
// ...
};
std::map<int, User> users; // Red-Black Tree
for (int i = 0; i < 1000000; ++i) {
users[i] = User{i, "User" + std::to_string(i)};
}
auto it = users.find(123456); // O(log n) ≈ 20번 비교문제의 코드에서는 std::map에 사용자 ID를 키로 User를 넣고 find로 조회합니다. std::map은 내부적으로 Red-Black Tree(레드-블랙 트리—균형 이진 탐색 트리)라서 삽입·검색·삭제가 모두 O(log n)입니다. 100만 개면 find 한 번에 약 20번 비교가 필요하고, “키로만 빠르게 찾고 순서는 필요 없다”면 unordered_map으로 바꿔 평균 O(1) 검색을 쓰는 편이 훨씬 빠릅니다.
일상 비유: map은 사전처럼 항목이 알파벳(키) 순으로 정렬되어 있어서 “A로 시작하는 단어”부터 찾기 쉽습니다. 반면 unordered_map은 서랍장처럼 각 키에 맞는 칸에 바로 넣어 두어서, “이 단어가 있는지”만 검색할 때는 훨씬 빠릅니다.
추가 문제 시나리오
시나리오 1: 설정 파일 파싱 후 키 순서 유지 필요
JSON/YAML 설정을 파싱해 map<string, Value>에 넣을 때, 사용자가 정의한 키 순서를 유지해야 한다면 map이 적합합니다. unordered_map은 순서가 보장되지 않아 출력 시 순서가 뒤섞입니다.
시나리오 2: 중복 키 허용 필요 (멀티맵)
한 사용자 ID에 여러 세션을 매핑할 때, map은 같은 키를 하나만 허용합니다. multimap을 써야 합니다.
시나리오 3: operator[]로 조회만 했는데 map에 항목이 생김
if (config["timeout"] > 0)처럼 “있는지 확인”만 하려고 []를 썼는데, 없던 키가 0으로 삽입되어 설정이 오염됩니다.
시나리오 4: unordered_map에 커스텀 구조체를 키로 쓰려다 컴파일 에러
unordered_map<Point, int>를 선언했는데 “hash specialization” 에러가 납니다. 사용자 정의 타입에는 해시 함수와 operator==가 필요합니다.
시나리오 5: map 순회 중 erase하면 크래시
for 루프 안에서 m.erase(it) 후 ++it를 하면 반복자가 무효화되어 미정의 동작이 발생합니다.
시나리오 6: 범위 검색이 필요한데 unordered_map 사용
”2021년~2023년 이벤트”처럼 연속 구간을 조회해야 할 때, unordered_map은 lower_bound/upper_bound를 지원하지 않아 전체 순회가 필요합니다.
시나리오 7: 중복 키를 허용해야 하는데 map 사용
한 사용자 ID에 여러 로그인 세션을 매핑할 때, map은 같은 키를 하나만 허용해 마지막 값만 남습니다. multimap이 필요합니다.
시나리오 8: unordered_map에 reserve 없이 대량 삽입
100만 개를 reserve 없이 삽입하면 재해싱이 여러 번 발생해 삽입 시간이 2~3배 늘어납니다.
unordered_map으로 해결 (시나리오 1 해결):
// 해결: 키 순서 불필요하면 unordered_map으로 O(1) 검색
std::unordered_map<int, User> users; // Hash Table
for (int i = 0; i < 1000000; ++i) {
users[i] = User{...};
}
auto it = users.find(123456); // O(1) ≈ 1번 비교결과: 검색 속도 10배 이상 빠름
이 글을 읽으면:
map,set,unordered_map,unordered_set의 내부 구조를 이해할 수 있습니다.- ordered vs unordered, 커스텀 키 타입을 상황에 맞게 선택할 수 있습니다.
- 자주 발생하는 에러와 해결법을 알 수 있습니다.
- 성능 최적화와 프로덕션 패턴을 적용할 수 있습니다.
목차
- 문제 중심: map vs unordered_map 선택
- std::map과 std::set 완전 가이드
- std::unordered_map과 std::unordered_set
- 커스텀 키 타입: ordered vs unordered
- 주요 연산과 패턴
- multimap과 multiset
- 자주 발생하는 에러와 해결법
- 모범 사례 (Best Practices)
- 성능 최적화 팁
- 프로덕션 패턴
- 성능 벤치마크
1. 문제 중심: map vs unordered_map 선택
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/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), 순서 없음 |
| 범위 검색 | ✅ lower_bound 등 | ❌ 불가 |
2. std::map과 std::set 완전 가이드
map: 키-값 쌍 저장 (Red-Black Tree)
std::map은 키-값 쌍을 저장하고, 키 기준으로 자동 정렬됩니다. 내부 구조는 Red-Black Tree로, 삽입·삭제 후에도 균형이 유지됩니다.
// 복사해 붙여넣은 뒤: 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;
// 삽입 방법 4가지
ages["Alice"] = 25;
ages["Bob"] = 30;
ages.insert({"Charlie", 35});
ages.emplace("David", 40);
// 접근
std::cout << ages["Alice"] << "\n"; // 25
// 검색 (find 권장: operator[]는 없으면 삽입함)
auto it = ages.find("Bob");
if (it != ages.end()) {
std::cout << it->first << ": " << it->second << "\n";
}
// 삭제
ages.erase("Charlie");
// 순회 (정렬된 순서: Alice, Bob, David)
for (const auto& [name, age] : ages) {
std::cout << name << ": " << age << "\n";
}
}실행 결과 (알파벳 순서로 정렬됨):
25
Bob: 30
Alice: 25
Bob: 30
David: 40주의: operator[]는 키가 없으면 기본값을 삽입합니다. 조회만 할 때는 find 또는 C++20 contains를 사용하세요.
set: 중복 없는 집합
std::set은 중복이 없는 키만 저장합니다. 내부적으로 map과 같은 Red-Black Tree 구조입니다.
// 복사해 붙여넣은 뒤: 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";
}
// 순회 (정렬된 순서: 2, 5, 8)
for (int num : numbers) {
std::cout << num << " ";
}
}실행 결과:
5 exists
2 5 8map/set 내부 구조: Red-Black Tree
[Bob:30]
/ \
[Alice:25] [David:40]
/
[Charlie:35]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에서 범위 검색 (lower_bound, upper_bound)
정렬된 map에서는 lower_bound, upper_bound로 구간 [a, b]를 쉽게 표현할 수 있습니다.
#include <map>
#include <iostream>
int main() {
std::map<int, std::string> events;
events[2020] = "Event A";
events[2021] = "Event B";
events[2022] = "Event C";
events[2023] = "Event D";
// lower_bound(k): k 이상인 첫 원소 반복자
// upper_bound(k): k 초과인 첫 원소 반복자
// [2021, 2022] 구간 = lower_bound(2021) ~ upper_bound(2022)
auto start = events.lower_bound(2021); // 2021 이상인 첫 원소
auto end = events.upper_bound(2022); // 2022 초과인 첫 원소
for (auto it = start; it != end; ++it) {
std::cout << it->first << ": " << it->second << "\n";
}
// 2021: Event B, 2022: Event C
}lower_bound/upper_bound 차이:
lower_bound(2021): 키가 2021이상인 첫 원소 (2021 포함)upper_bound(2022): 키가 2022초과인 첫 원소 (2022 제외)[lower_bound(a), upper_bound(b))= 구간 [a, b].equal_range(k)는 이 쌍을 한 번에 반환.
std::map vs std::unordered_map 완전 비교 예제
#include <map>
#include <unordered_map>
#include <iostream>
void demoOrderedVsUnordered() {
// 1. map: 정렬 순서 보장, 범위 검색 가능
std::map<int, std::string> ordered = {{3,"three"},{1,"one"},{2,"two"},{4,"four"}};
for (const auto& [k, v] : ordered) std::cout << k << " "; // 1 2 3 4
// 2. unordered_map: 순서 없음, O(1) 검색
std::unordered_map<int, std::string> unordered = {{3,"three"},{1,"one"},{2,"two"},{4,"four"}};
for (const auto& [k, v] : unordered) std::cout << k << " "; // 순서 예측 불가
// 3. map만 가능: lower_bound/upper_bound 범위 검색
auto lo = ordered.lower_bound(2), hi = ordered.upper_bound(3);
for (auto it = lo; it != hi; ++it) std::cout << it->first << " "; // 2 3
}3. std::unordered_map과 std::unordered_set
unordered_map: 해시 테이블
std::unordered_map은 해시 테이블 기반이라 키 순서가 유지되지 않습니다. 삽입·삭제·검색이 평균 O(1)입니다.
#include <unordered_map>
#include <iostream>
#include <string>
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";
}
}unordered_set: 해시 집합
#include <unordered_set>
#include <iostream>
int main() {
std::unordered_set<int> numbers = {5, 2, 8, 2};
if (numbers.count(5) > 0) {
std::cout << "5 exists\n";
}
for (int num : numbers) {
std::cout << num << " ";
}
// 출력 순서: 예측 불가
}해시 테이블 내부 구조
Bucket 0: [Alice:25] → [David:40]
Bucket 1: [Bob:30]
Bucket 2: (empty)
Bucket 3: [Charlie:35]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
4. 커스텀 키 타입: ordered vs unordered
map: 커스텀 비교 함수
map의 키로 사용자 정의 타입을 쓰려면, 비교 함수가 필요합니다. operator<를 정의하거나, 세 번째 템플릿 인자로 비교 함수 객체를 넘깁니다.
#include <map>
#include <string>
struct Person {
std::string name;
int age;
};
// 방법 1: operator< 정의
bool operator<(const Person& a, const Person& b) {
return a.age < b.age; // 나이 순 정렬
}
// 방법 2: 비교 함수 객체 (map 세 번째 인자)
struct CompareByAge {
bool operator()(const Person& a, const Person& b) const {
return a.age < b.age;
}
};
int main() {
std::map<Person, std::string, CompareByAge> people;
people[{ "Alice", 25 }] = "Engineer";
people[{ "Bob", 30 }] = "Designer";
// 나이 순으로 정렬됨
}unordered_map: 해시 함수와 operator==
unordered_map의 키로 커스텀 타입을 쓰려면 해시 함수와 operator==가 필요합니다.
#include <unordered_map>
#include <string>
struct Point {
int x, y;
bool operator==(const Point& other) const {
return x == other.x && y == other.y;
}
};
// 방법 1: std::hash 특수화
namespace std {
template <>
struct hash<Point> {
size_t operator()(const Point& p) const {
return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
}
};
}
// 방법 2: 해시 함수 객체를 템플릿 인자로 전달
struct PointHash {
size_t operator()(const Point& p) const {
return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
}
};
int main() {
std::unordered_map<Point, std::string> points; // std::hash 특수화 사용
points[{1, 2}] = "A";
points[{3, 4}] = "B";
// 또는
std::unordered_map<Point, std::string, PointHash> points2;
}해시 함수 설계 원칙:
- 같은 키 → 같은 해시값
- 충돌이 적을수록 성능 좋음
- 빠른 계산이 중요
복합 키 예제: (id, name) 쌍
#include <unordered_map>
#include <string>
#include <functional>
struct CompositeKey {
int id;
std::string name;
bool operator==(const CompositeKey& other) const {
return id == other.id && name == other.name;
}
};
struct CompositeKeyHash {
size_t operator()(const CompositeKey& k) const {
size_t h1 = std::hash<int>()(k.id);
size_t h2 = std::hash<std::string>()(k.name);
return h1 ^ (h2 << 1);
}
};
int main() {
std::unordered_map<CompositeKey, int, CompositeKeyHash> cache;
cache[{1, "Alice"}] = 100;
}5. 주요 연산과 패턴
find / insert / erase 완전 예제
#include <map>
#include <set>
#include <iostream>
#include <string>
void demoFindInsertErase() {
std::map<std::string, int> m;
// === INSERT ===
m["Alice"] = 25; // operator[]: 없으면 삽입, 있으면 덮어씀
m.insert({"Bob", 30}); // pair 삽입
m.emplace("Charlie", 35); // in-place 생성
auto [it, ok] = m.insert({"Alice", 99}); // Alice 있으면 ok=false, 삽입 안 함
// === FIND ===
auto f = m.find("Bob");
if (f != m.end()) {
std::cout << "Bob: " << f->second << "\n";
}
// C++20: if (m.contains("Bob")) { ... }
// === ERASE ===
m.erase("Charlie"); // 키로 삭제
auto it2 = m.find("Bob");
if (it2 != m.end()) {
m.erase(it2); // 반복자로 삭제
}
// set 예제
std::set<int> s = {5, 2, 8, 2, 2}; // 중복 무시 → {2, 5, 8}
s.erase(5);
auto sit = s.find(8);
if (sit != s.end()) s.erase(sit);
}삽입: insert vs emplace vs try_emplace
#include <map>
#include <string>
int main() {
std::map<std::string, std::string> m;
// insert: pair 임시 객체 생성
m.insert({"key1", "value1"});
// emplace: 내부에서 직접 생성 (더 효율적)
m.emplace("key2", "value2");
// try_emplace (C++17): 키가 없을 때만 값 생성
m.try_emplace("key3", "value3");
m.try_emplace("key3", "ignored"); // 키 있으면 값 생성 안 함
}조회: operator[] vs at() vs find()
#include <map>
#include <iostream>
#include <string>
int main() {
std::map<std::string, int> m;
m["a"] = 1;
// operator[]: 키 없으면 기본값 삽입 후 반환 (주의!)
int v1 = m["missing"]; // 0 삽입됨
// at(): 키 없으면 std::out_of_range 예외
try {
int v2 = m.at("missing");
} catch (const std::out_of_range& e) {
std::cerr << "Key not found\n";
}
// find(): 안전한 조회 (권장)
auto it = m.find("a");
if (it != m.end()) {
std::cout << it->second << "\n";
}
}삭제: erase 반복자 무효화 주의
#include <map>
#include <iostream>
int main() {
std::map<int, int> m = {{1, 10}, {2, -5}, {3, 20}, {4, -3}};
// 순회 중 삭제: erase가 다음 반복자 반환
for (auto it = m.begin(); it != m.end(); ) {
if (it->second < 0) {
it = m.erase(it); // ✅ 올바른 패턴
} else {
++it;
}
}
}C++20 contains
#include <map>
#include <string>
int main() {
std::map<std::string, int> m;
m["hello"] = 42;
if (m.contains("hello")) {
// 키 존재 확인
}
}6. multimap과 multiset
같은 키를 여러 번 넣어야 할 때는 std::multimap(또는 multiset)을 씁니다.
#include <map>
#include <iostream>
#include <string>
int main() {
std::multimap<std::string, int> scores;
scores.insert({"Alice", 90});
scores.insert({"Alice", 95});
scores.insert({"Bob", 80});
// 특정 키의 모든 값 찾기
auto range = scores.equal_range("Alice");
for (auto it = range.first; it != range.second; ++it) {
std::cout << it->second << " ";
}
// 90 95
}7. 자주 발생하는 에러와 해결법
문제 1: operator[]로 조회만 했는데 map에 항목이 생김
증상: if (m["userId"] > 0)처럼 조회만 하려 했는데, 없던 키가 0으로 추가됨.
원인: operator[]는 키가 없으면 기본값을 삽입한 뒤 그 참조를 반환합니다.
해결법:
// ❌ 잘못된 사용
if (m["userId"] > 0) { }
// ✅ find 사용
auto it = m.find("userId");
if (it != m.end() && it->second > 0) { }
// ✅ C++20 contains
if (m.contains("userId") && m["userId"] > 0) { }문제 2: unordered_map에 커스텀 타입을 키로 쓰려다 컴파일 에러
증상: std::unordered_map<MyStruct, int> m; 선언 시 “hash specialization” 에러.
원인: unordered_map은 키에 대해 해시 함수와 operator==가 필요합니다.
해결법: 위 커스텀 키 타입 섹션 참고.
문제 3: map 순회 중 erase하면 반복자 무효화
증상: m.erase(it) 후 ++it 시 크래시 또는 미정의 동작.
원인: erase(it) 호출 시 it가 무효화됩니다.
해결법:
// ❌ 잘못된 사용
for (auto it = m.begin(); it != m.end(); ++it) {
if (condition) m.erase(it); // it 무효화!
}
// ✅ 올바른 사용
for (auto it = m.begin(); it != m.end(); ) {
if (condition) {
it = m.erase(it);
} else {
++it;
}
}문제 4: unordered_map이 예상보다 느림 (해시 충돌)
증상: unordered_map을 썼는데 map보다 느리거나, 데이터가 많아질수록 급격히 느려짐.
원인: 해시 충돌이 많거나, reserve 없이 삽입해 재해싱이 반복됨.
해결법:
std::unordered_map<int, Data> m;
m.reserve(1000000); // 넣을 개수 예상
for (int i = 0; i < 1000000; ++i) {
m[i] = data;
}문제 5: map의 operator[]가 무거운 값 타입을 기본 생성함
증상: std::map<K, BigObject>에서 m[key]로 접근할 때, 키가 없으면 BigObject()가 호출되어 비용이 큼.
해결법:
// ❌ operator[]: 키 없으면 BigObject() 호출
BigObject& obj = m[key];
// ✅ try_emplace (C++17)
auto [it, inserted] = m.try_emplace(key, arg1, arg2);문제 6: set/map에 포인터를 키로 넣을 때 주의
증상: std::set<int*>에 넣으면 포인터 값(주소)으로 비교됩니다. 같은 논리적 객체라도 주소가 다르면 다른 키로 취급됩니다.
해결법:
// 포인터 주소 비교 (의도한 경우)
std::set<int*> ptrSet;
// 객체 내용 비교가 필요하면 커스텀 Compare 사용
struct PtrCompare {
bool operator()(const int* a, const int* b) const {
return *a < *b;
}
};
std::set<int*, PtrCompare> valueOrderedSet;문제 7: unordered_map 반복자 순회 중 삽입/삭제
증상: unordered_map을 순회하는 동안 insert/erase를 하면 반복자가 무효화될 수 있습니다.
해결법: 순회 중 수정이 필요하면 먼저 수정할 키 목록을 수집한 뒤, 순회가 끝난 후 일괄 수정합니다.
std::unordered_map<int, int> m;
// ...
std::vector<int> toErase;
for (auto it = m.begin(); it != m.end(); ++it) {
if (it->second < 0) toErase.push_back(it->first); // 조건에 맞는 키 수집
}
for (int k : toErase) m.erase(k);문제 8: multimap에서 operator[] 사용 시도
증상: std::multimap<K, V>에서 m[key]를 쓰려다 컴파일 에러.
원인: multimap은 같은 키에 여러 값이 있을 수 있어 operator[]가 정의되어 있지 않습니다.
해결법:
// ❌ multimap에는 operator[] 없음
// m[key] = value; // 컴파일 에러
// ✅ insert 사용
std::multimap<std::string, int> m;
m.insert({"Alice", 90});
m.insert({"Alice", 95});
// 조회: equal_range
auto [lo, hi] = m.equal_range("Alice");
for (auto it = lo; it != hi; ++it) {
std::cout << it->second << " ";
}8. 모범 사례 (Best Practices)
BP 1: 조회만 할 때는 find 또는 contains 사용
// ❌ operator[]: 키 없으면 기본값 삽입 (설정 오염)
if (config["timeout"] > 0) { }
// ✅ find
auto it = config.find("timeout");
if (it != config.end() && it->second > 0) { }
// ✅ C++20 contains
if (config.contains("timeout") && config["timeout"] > 0) { }BP 2: unordered_map 대량 삽입 전 reserve
std::unordered_map<int, Data> cache;
cache.reserve(expected_size); // 재해싱 최소화
for (const auto& item : source) {
cache[item.id] = item;
}BP 3: 무거운 값 타입은 try_emplace
// ❌ operator[]: 키 없으면 BigObject() 기본 생성
std::map<int, BigObject> m;
m[key] = BigObject(a, b, c); // 키 있으면 대입, 없으면 기본 생성 후 대입
// ✅ try_emplace: 키 없을 때만 생성
m.try_emplace(key, a, b, c);BP 4: 순회 중 삭제 시 erase 반환값 활용
for (auto it = m.begin(); it != m.end(); ) {
if (should_remove(it)) {
it = m.erase(it); // C++11: erase가 다음 유효 반복자 반환
} else {
++it;
}
}BP 5: 커스텀 키는 명시적 해시/비교 함수 사용
// std::hash 특수화는 std 네임스페이스 오염 → 가능하면 피함
std::unordered_map<MyKey, int, MyKeyHash, MyKeyEqual> m;BP 6: const 참조로 순회, 범위 검색 시 map 선택
for (const auto& [k, v] : map) process(k, v); // 복사 방지
// 범위 검색 필요 → map. 단순 조회 → unordered_map9. 성능 최적화 팁
팁 1: unordered_map에 reserve 사용
std::unordered_map<int, int> m;
m.reserve(1000); // 재해싱 방지
for (int i = 0; i < 1000; ++i) {
m[i] = i;
}팁 2: emplace vs insert
// insert: 임시 pair 생성
m.insert({"key", "value"});
// emplace: 직접 생성 (더 효율적)
m.emplace("key", "value");팁 3: try_emplace (C++17)
키가 이미 있으면 값 생성 인자를 사용하지 않아, 무거운 객체 삽입 시 유리합니다.
팁 4: load_factor 조절 (고급)
m.max_load_factor(0.5); // 버킷당 평균 0.5개 이하
m.rehash(2000000); // 버킷 수 미리 늘림팁 5: 정렬 필요 없으면 unordered 선택
“키 순서대로 출력”이 필요 없고 “빠른 검색”이 목적이면 unordered_map이 map보다 수 배 빠를 수 있습니다.
10. 프로덕션 패턴
패턴 1: LRU 캐시 (unordered_map + list)
#include <unordered_map>
#include <list>
#include <optional>
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) {}
std::optional<V> get(const K& key) {
auto it = map_.find(key);
if (it == map_.end()) return std::nullopt;
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();
}
};패턴 2: 시간순 이벤트 로그 (map)
#include <map>
#include <string>
#include <chrono>
using Timestamp = std::chrono::system_clock::time_point;
std::map<Timestamp, std::string> eventLog;
void logEvent(Timestamp t, const std::string& msg) {
eventLog[t] = msg;
}
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->first.time_since_epoch().count()
<< "] " << it->second << "\n";
}
}패턴 3: 단어 빈도 집계 (unordered_map)
#include <unordered_map>
#include <string>
#include <sstream>
std::unordered_map<std::string, size_t> countWords(const std::string& text) {
std::unordered_map<std::string, size_t> counts;
std::istringstream iss(text);
std::string word;
while (iss >> word) {
counts[word]++;
}
return counts;
}패턴 4: 설정 관리자 (map + 기본값)
#include <map>
#include <string>
#include <optional>
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& default_val) const {
auto it = config_.find(key);
return (it != config_.end()) ? it->second : default_val;
}
};위 코드 설명: get은 find를 사용해 조회만 하고, getOrDefault는 없을 때 기본값을 반환합니다. operator[]를 쓰지 않아 설정 오염을 방지합니다.
패턴 5: 스레드 안전 캐시 (mutex + unordered_map)
#include <unordered_map>
#include <mutex>
#include <optional>
template <typename K, typename V>
class ThreadSafeCache {
std::unordered_map<K, V> cache_;
mutable std::mutex mtx_;
public:
std::optional<V> get(const K& key) const {
std::lock_guard lock(mtx_);
auto it = cache_.find(key);
if (it == cache_.end()) return std::nullopt;
return it->second;
}
void put(const K& key, V value) {
std::lock_guard lock(mtx_);
cache_[key] = std::move(value);
}
};11. 성능 벤치마크
#include <chrono>
#include <iostream>
#include <map>
#include <unordered_map>
void benchmark() {
auto run = {
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < n; ++i) m[i] = i;
for (int i = 0; i < n; ++i) m.find(i);
return std::chrono::duration_cast<std::chrono::milliseconds>(
std::chrono::high_resolution_clock::now() - start).count();
};
std::map<int, int> m1;
std::unordered_map<int, int> m2;
m2.reserve(1000000);
std::cout << "map: " << run(m1, 1000000) << " ms\n";
std::cout << "unordered_map: " << run(m2, 1000000) << " ms\n";
}예상 결과: unordered_map이 map보다 3~10배 빠를 수 있습니다.
벤치마크 결과 해석
- map: O(log n). 100만 개 기준 find 한 번에 약 20번 비교. n이 커질수록 로그적으로 증가.
- unordered_map: 평균 O(1).
reserve없이 삽입하면 재해싱 비용 추가. - 작은 데이터(n < 1000): unordered_map이 상대적으로 유리할 수 있음.
- 캐시 지역성: map은 트리 순회로 캐시 미스, unordered_map은 버킷 접근으로 캐시 지역성 우수.
같이 보면 좋은 글 (내부 링크)
이 주제와 연결되는 다른 글입니다.
- C++ vector 성능 | “100만 개 넣는데 10초” 문제와 reserve
- C++ STL 알고리즘 | sort·find·transform 람다와 함께 쓰기 (실전 패턴)
- C++ Move Semantics | std::move로 불필요한 복사 제거하고 성능 최적화
이 글에서 다루는 키워드 (관련 검색어)
C++ map unordered_map, map vs unordered_map, STL map set, Red-Black Tree, 해시 테이블, O(log n) O(1), multimap multiset, 커스텀 키 해시, LRU 캐시, std::map 성능 등으로 검색하시면 이 글이 도움이 됩니다.
정리
| 항목 | map/set | unordered_map/set |
|---|---|---|
| 내부 구조 | Red-Black Tree | Hash Table |
| 정렬 | ✅ 자동 정렬 | ❌ 순서 없음 |
| 검색 속도 | O(log n) | O(1) 평균 |
| 범위 검색 | ✅ 가능 | ❌ 불가 |
| 커스텀 키 | operator< 또는 Compare | hash + operator== |
선택 기준:
- 정렬 필요 →
map/set - 빠른 검색 →
unordered_map/unordered_set - 범위 검색 →
map/set - 순서 무관 →
unordered_map/unordered_set
구현 체크리스트
- 정렬 필요 여부 확인 후 map vs unordered_map 선택
- 조회만 할 때 operator[] 대신 find 또는 contains 사용
- unordered_map에 reserve로 재해싱 최소화
- 무거운 값 타입은 try_emplace 사용
- 순회 중 삭제 시 it = m.erase(it) 패턴 사용
- 커스텀 키: map은 Compare, unordered_map은 hash + operator==
자주 묻는 질문 (FAQ)
Q. 실무에서 언제 쓰나요? ordered vs unordered 선택, 커스텀 키, operator[] 함정, reserve/try_emplace, LRU 캐시·설정 관리 등 프로덕션 패턴을 참고하세요.
Q. 선행으로 읽으면 좋은 글은? C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.
Q. 더 깊이 공부하려면? cppreference를 참고하세요.
한 줄 요약: map·set은 정렬/범위 검색, unordered_map·unordered_set은 O(1) 조회에 적합합니다.
다음 글: C++ STL 알고리즘
관련 글
- C++ 시리즈 전체 보기
- C++ Adapter Pattern 완벽 가이드 | 인터페이스 변환과 호환성
- C++ ADL |
- C++ Aggregate Initialization |