C++ 컨테이너 선택 가이드 | vector/list/deque/map/set 상황별 선택과 성능 최적화
이 글의 핵심
C++ 컨테이너 선택 가이드: vector/list/deque/map/set 상황별 선택과 성능 최…. 컨테이너를 잘못 골라서 시간 초과가 났어요부터 핵심 개념·패턴·실무 함정을 코드 예제로 풉니다.
💡 초보자를 위한 한 줄: 기본 시퀀스는
vector가 안전합니다. 맨 앞 삽입이 잦으면deque, 중간 삽입·반복자 안정이 핵심이면list를 떠올리세요. 연관 컨테이너는 순서·범위 쿼리가 있으면map, 없으면unordered_map. 13-1 vector 기초·13-2 map·set과 세트로 보면 좋습니다.
들어가며: 컨테이너를 잘못 골라서 시간 초과가 났어요
”앞에 계속 넣는데 왜 이렇게 느리죠?”
로그를 시간 역순으로 저장하려고 vector의 맨 앞에 insert를 반복했습니다. 데이터가 10만 건만 되어도 수 초가 걸렸습니다.
문제의 코드에서 vector::insert(begin(), x)는 O(n)입니다. 맨 앞에 넣으면 뒤쪽 원소를 전부 한 칸씩 밀어야 하기 때문입니다. 10만 번 반복하면 O(n²)가 되어, 100억 번의 원소 이동이 발생합니다.
// ❌ 나쁜 예: vector 앞쪽 반복 삽입 → O(n²)
// 실행 예제
std::vector<int> logs;
for (int i = 0; i < 100000; ++i) {
logs.insert(logs.begin(), i); // 매번 O(n) 이동
}비유하면 vector는 “한 줄로 서 있는 사람들”입니다. 맨 앞에 새 사람을 넣으려면 뒤에 있는 모든 사람이 한 칸씩 물러나야 합니다. deque는 “앞뒤로 문이 있는 복도”처럼 양쪽에서 O(1)로 넣고 뺄 수 있습니다.
// 실행 예제
flowchart TB
subgraph problem[자주 겪는 실패 시나리오]
P1[vector 앞 삽입 반복 → TLE]
P2[map으로 키 검색만 → 느림]
P3["정렬된데 find 사용 → O(n)"]
P4[reserve 없이 대량 push_back → 재할당 폭발]
end
subgraph solution[올바른 선택]
S1[deque / list]
S2[unordered_map]
S3[lower_bound / binary_search]
S4[reserve로 미리 확보]
end
P1 --> S1
P2 --> S2
P3 --> S3
P4 --> S4
이 글을 읽으면:
- vector, list, deque, map, set의 차이를 이해할 수 있습니다.
- 상황별로 어떤 컨테이너를 쓸지 결정할 수 있습니다.
- 일반적인 실수와 해결법을 알 수 있습니다.
- 성능 벤치마크와 프로덕션 패턴을 활용할 수 있습니다.
실무 적용 경험: 이 글은 대규모 C++ 프로젝트에서 실제로 겪은 문제와 해결 과정을 바탕으로 작성되었습니다. 책이나 문서에서 다루지 않는 실전 함정과 디버깅 팁을 포함합니다.
1. 문제 시나리오와 원인 분석
시나리오 1: 로그 버퍼 — 앞쪽 삽입 반복
증상: 최신 로그를 맨 앞에 넣다 보니 10만 건에서 수 초 소요.
원인: vector::insert(begin(), x)는 O(n). N번 반복 시 O(n²).
해결: deque 사용. push_front는 O(1).
시나리오 2: 사용자 ID 조회 — map이 느림
증상: 100만 명 사용자 DB에서 ID로 조회하는데 응답이 느림.
원인: std::map은 Red-Black Tree로 O(log n). 순서가 필요 없으면 unordered_map이 평균 O(1).
해결: 키 순서가 불필요하면 unordered_map 사용.
시나리오 3: 정렬된 배열 검색 — find 사용
증상: 정렬된 100만 개 배열에서 값 찾는데 선형 탐색으로 시간 초과.
원인: std::find는 O(n). 정렬된 범위에서는 lower_bound가 O(log n).
해결: 정렬된 범위에서는 lower_bound, binary_search 사용.
시나리오 4: 대량 push_back — 재할당 폭발
증상: 100만 개를 push_back만 했는데 10초 걸림.
원인: vector는 capacity 부족 시 2배 재할당. 100만 개면 약 20번 재할당 × 평균 50만 개 복사.
해결: reserve(예상_개수)로 미리 공간 확보.
시나리오 5: 중간 삽입/삭제 — vector가 비효율
증상: 연결 리스트처럼 중간에서 자주 삽입·삭제하는데 vector 사용.
원인: vector::insert/erase(중간)는 O(n). 뒤쪽 원소를 전부 이동.
해결: 반복자 위치를 이미 알고 있고, 인덱스 접근이 거의 없으면 list 고려. 단, 캐시 비친화적이라 작은 원소에서는 vector가 나을 수 있음.
시나리오 6: 반복자 무효화 — 순회 중 삭제
증상: for 루프 안에서 erase 호출 후 크래시 또는 무한 루프.
원인: vector::erase는 삭제된 위치 이후의 반복자를 무효화. ++it로 무효화된 반복자를 사용하면 UB.
해결: it = v.erase(it)처럼 erase가 반환하는 새 반복자를 사용.
시나리오 7: priority_queue 비교자 반대
증상: 최소 힙이 필요한데 최대 힙이 됨.
원인: 기본 std::less는 최대 힙. 최소 힙은 std::greater 필요.
해결:
// 최대 힙 (기본)
std::priority_queue<int> maxHeap;
// 최소 힙
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;시나리오 8: unordered_map 해시 충돌 — worst case O(n)
증상: 특정 입력에서 unordered_map이 극도로 느려짐.
원인: 해시 충돌이 많으면 버킷이 길어져 O(n)에 가까워짐. 악의적 입력으로 공격 가능.
해결: 보안이 중요하면 std::map 사용. 또는 unordered_map에 reserve로 버킷 수 미리 설정.
2. 시퀀스 컨테이너: vector vs list vs deque
연산별 시간복잡도 비교
| 연산 | vector | deque | list |
|---|---|---|---|
| 뒤 추가/삭제 | O(1) amort | O(1) | O(1) |
| 앞 추가/삭제 | O(n) | O(1) | O(1) |
| 중간 삽입/삭제 | O(n) | O(n) | O(1)* |
인덱스 접근 [] | O(1) | O(1) | O(n) |
| 순차 순회 | 캐시 친화 | 보통 | 비친화 |
| * 반복자 위치가 이미 있을 때 |
vector — 기본 선택
특징: 연속 메모리, 캐시 친화적, [] O(1), push_back O(1) amortized.
적합한 경우:
- 인덱스 접근이 많음 (DP, 그리디)
push_back위주- 순차 순회가 주 연산
// vector가 적합: DP, 인덱스 접근
#include <vector>
std::vector<int> dp(1000000);
dp[0] = 1;
for (size_t i = 1; i < dp.size(); ++i) {
dp[i] = dp[i - 1] + (i >= 2 ? dp[i - 2] : 0);
}deque — 앞뒤 삽입/삭제
특징: 앞뒤 push_front/pop_front/push_back/pop_back 모두 O(1). [] O(1).
적합한 경우:
- BFS 큐 (앞에서 pop, 뒤에서 push)
- 슬라이딩 윈도우
- 로그 버퍼 (최신이 앞)
// deque가 적합: BFS
#include <deque>
#include <vector>
void bfs(const std::vector<std::vector<int>>& graph, int start) {
std::deque<int> q;
q.push_back(start);
while (!q.empty()) {
int u = q.front();
q.pop_front(); // O(1)
for (int v : graph[u]) {
q.push_back(v);
}
}
}list — 중간 삽입/삭제 (반복자 유지 시)
특징: insert/erase(위치 알 때) O(1). splice로 O(1) 이동. [] 없음.
적합한 경우:
- LRU 캐시 (순서 유지 + O(1) 삽입/삭제)
- 반복자 무효화 없이 중간 삭제
splice로 구간 이동
// list가 적합: splice로 O(1) 이동
#include <list>
std::list<int> a = {1, 2, 3};
std::list<int> b = {4, 5};
a.splice(a.end(), b); // O(1): b의 원소를 a 끝으로 이동시퀀스 선택 플로우다이어그램
flowchart TD
A[시퀀스 컨테이너 필요] --> B{인덱스 접근 필요?}
B -->|예| C{앞쪽 삽입/삭제 많음?}
B -->|아니오| D{중간 삽입/삭제 많음?}
C -->|예| E[deque]
C -->|아니오| F[vector]
D -->|예| G[list]
D -->|아니오| H[vector 또는 deque]
vector vs deque vs list 메모리 레이아웃
flowchart LR
subgraph vector[vector]
V1[블록1] --> V2[블록2]
V2 --> V3[연속 메모리]
end
subgraph deque[deque]
D1[청크1] --> D2[청크2]
D2 --> D3[청크3]
D3 --> D4[여러 청크]
end
subgraph list[list]
L1[노드1] --> L2[노드2]
L2 --> L3[노드3]
L3 --> L4[분산 메모리]
end
- vector: 한 덩어리 연속 메모리. 캐시 라인 활용 최고.
reserve로 재할당 최소화. - deque: 여러 청크로 나뉜 구조. 앞뒤 확장 시 새 청크만 할당.
- list: 노드마다 포인터 2개(prev, next). 메모리 오버헤드 큼, 캐시 비친화.
3. 연관 컨테이너: map vs set vs unordered
map vs unordered_map
| 연산 | map | unordered_map |
|---|---|---|
| insert, erase, find | O(log n) | O(1) 평균 |
| 순회 | 키 정렬 순 | 순서 없음 |
| 메모리 | 적음 | 해시 버킷 오버헤드 |
map (Red-Black Tree): 키 순서가 필요할 때. lower_bound, upper_bound로 범위 쿼리. | ||
| unordered_map (해시 테이블): 키로만 빠르게 찾고 순서는 필요 없을 때. |
// map: 정렬된 키, 범위 쿼리
#include <map>
std::map<int, std::string> m;
m[1] = "one";
m[2] = "two";
auto it = m.lower_bound(1); // O(log n)// unordered_map: 키 검색만, 순서 불필요
#include <unordered_map>
std::unordered_map<int, std::string> um;
um[1] = "one";
auto it = um.find(1); // O(1) 평균set vs unordered_set
set: 중복 없이 정렬된 순서 유지. lower_bound 사용 가능.
unordered_set: 중복 없이 존재 여부만. O(1) 평균.
// set: 정렬된 순서, 범위 쿼리
#include <set>
std::set<int> s = {3, 1, 2};
for (int x : s) { /* 1, 2, 3 순 */ }// unordered_set: 존재 여부만
#include <unordered_set>
std::unordered_set<int> us;
if (us.count(42)) { /* O(1) 평균 */ }multimap / multiset — 중복 키 허용
multimap: 같은 키에 여러 값. equal_range로 해당 키의 모든 값 조회.
multiset: 중복 원소 허용. 정렬된 순서 유지.
// multimap: 같은 키에 여러 값
#include <map>
std::multimap<std::string, int> mm;
mm.insert({"a", 1});
mm.insert({"a", 2});
auto [lo, hi] = mm.equal_range("a");
for (auto it = lo; it != hi; ++it) {
// ("a", 1), ("a", 2)
}연관 컨테이너 선택 플로우
flowchart TD
A[연관 컨테이너 필요] --> B{키 순서 필요?}
B -->|예| C{중복 키 허용?}
B -->|아니오| D[unordered_map / unordered_set]
C -->|예| E[multimap / multiset]
C -->|아니오| F[map / set]
4. 완전한 컨테이너 선택 예제
예제 1: vector — DP, 인덱스 접근
// 피보나치 DP: vector가 최적
#include <vector>
#include <iostream>
int main() {
int n = 1000000;
std::vector<long long> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
std::cout << dp[n] << "\n";
return 0;
}예제 2: deque — BFS, 로그 버퍼
// 1) BFS: deque
#include <deque>
#include <vector>
void bfs(const std::vector<std::vector<int>>& graph, int start) {
std::deque<int> q;
std::vector<bool> visited(graph.size());
q.push_back(start);
visited[start] = true;
while (!q.empty()) {
int u = q.front();
q.pop_front();
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
q.push_back(v);
}
}
}
}// 2) 로그 버퍼: deque (최신이 앞)
#include <deque>
#include <string>
class LogBuffer {
std::deque<std::string> logs;
static constexpr size_t MAX_SIZE = 10000;
public:
void add(const std::string& msg) {
logs.push_front(msg); // O(1)
if (logs.size() > MAX_SIZE) {
logs.pop_back();
}
}
};예제 3: list — LRU 캐시
// LRU: map + list (get/put O(1))
#include <list>
#include <unordered_map>
class LRUCache {
int capacity;
std::list<std::pair<int, int>> cache;
std::unordered_map<int, std::list<std::pair<int, int>>::iterator> key2it;
public:
explicit LRUCache(int cap) : capacity(cap) {}
int get(int key) {
auto it = key2it.find(key);
if (it == key2it.end()) return -1;
cache.splice(cache.begin(), cache, it->second);
return it->second->second;
}
void put(int key, int value) {
auto it = key2it.find(key);
if (it != key2it.end()) {
it->second->second = value;
cache.splice(cache.begin(), cache, it->second);
return;
}
if (cache.size() == static_cast<size_t>(capacity)) {
key2it.erase(cache.back().first);
cache.pop_back();
}
cache.emplace_front(key, value);
key2it[key] = cache.begin();
}
};예제 4: map — 정렬된 키, 범위 쿼리
// 범위 내 키 개수: map
#include <map>
#include <iostream>
int main() {
std::map<int, int> cnt;
int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};
for (int x : arr) ++cnt[x];
// [2, 5] 구간 내 키 개수
auto lo = cnt.lower_bound(2);
auto hi = cnt.upper_bound(5);
int range_count = 0;
for (auto it = lo; it != hi; ++it) {
range_count += it->second;
}
std::cout << "count in [2,5]: " << range_count << "\n";
return 0;
}예제 5: unordered_map — 키 검색만
// 두 수의 합: unordered_map O(n)
#include <unordered_map>
#include <vector>
std::vector<int> twoSum(const std::vector<int>& nums, int target) {
std::unordered_map<int, int> seen; // 값 -> 인덱스
for (size_t i = 0; i < nums.size(); ++i) {
int need = target - nums[i];
if (auto it = seen.find(need); it != seen.end()) {
return {static_cast<int>(it->second), static_cast<int>(i)};
}
seen[nums[i]] = static_cast<int>(i);
}
return {};
}예제 6: set — 중복 제거 + 정렬
// 중복 제거 후 정렬된 순서: set
#include <set>
#include <vector>
std::vector<int> uniqueSorted(const std::vector<int>& input) {
std::set<int> s(input.begin(), input.end());
return std::vector<int>(s.begin(), s.end());
}상황별 선택 요약 표
| 상황 | 추천 | 이유 |
|---|---|---|
| 인덱스 접근, push_back 위주 | vector | O(1) 접근, 캐시 친화 |
| 앞뒤 삽입/삭제 | deque | 앞뒤 O(1) |
| 중간 삽입/삭제 (반복자 유지) | list | O(1) insert/erase |
| 키 검색만, 순서 불필요 | unordered_map | O(1) 평균 |
| 키 순서·범위 쿼리 | map | O(log n), lower_bound |
| 중복 없이 존재 여부만 | unordered_set | O(1) 평균 |
| 정렬된 순서 유지 | set | O(log n) |
예제 7: vector + 정렬 vs set — 동적 삽입/검색
// 패턴 A: 한 번에 넣고 검색만 → vector + sort + lower_bound
#include <vector>
#include <algorithm>
std::vector<int> v = {3, 1, 4, 1, 5};
std::sort(v.begin(), v.end());
bool found = std::binary_search(v.begin(), v.end(), 4);
// 패턴 B: 삽입/삭제/검색 반복 → set
#include <set>
std::set<int> s = {3, 1, 4, 1, 5}; // 자동 정렬, 중복 제거
s.insert(2);
s.erase(1);
auto it = s.find(4);선택 기준: 삽입·삭제가 드물면 vector + sort. 동적이면 set.
예제 8: emplace_back vs push_back
// 복잡한 객체 삽입 시 emplace_back이 효율적
#include <vector>
#include <string>
struct Item {
int id;
std::string name;
Item(int i, const std::string& n) : id(i), name(n) {}
};
std::vector<Item> items;
// ❌ 임시 객체 생성 후 이동
items.push_back(Item(1, "hello"));
// ✅ 컨테이너 내부에서 직접 생성 (복사/이동 없음)
items.emplace_back(1, "hello");5. 자주 발생하는 에러와 해결법
에러 1: vector 앞쪽 반복 삽입 → TLE
증상: “맨 앞에 추가” 문제에서 시간 초과.
원인: vector::insert(begin(), x)는 O(n). N번 반복 시 O(n²).
해결:
// ❌ 나쁜 예
std::vector<int> v;
for (int i = 0; i < n; ++i) {
v.insert(v.begin(), a[i]);
}
// ✅ 좋은 예 1: deque
std::deque<int> d;
for (int i = 0; i < n; ++i) {
d.push_front(a[i]);
}
// ✅ 좋은 예 2: 뒤에 넣고 reverse
std::vector<int> v;
for (int i = 0; i < n; ++i) v.push_back(a[i]);
std::reverse(v.begin(), v.end());에러 2: 정렬된 배열인데 find 사용
증상: 이진 탐색 문제인데 선형 탐색으로 시간 초과.
원인: std::find는 O(n). 정렬된 범위에서는 lower_bound가 O(log n).
해결:
// ❌ 나쁜 예
auto it = std::find(v.begin(), v.end(), x); // O(n)
// ✅ 좋은 예
auto it = std::lower_bound(v.begin(), v.end(), x); // O(log n)
if (it != v.end() && *it == x) { /* 찾음 */ }에러 3: map을 “존재 여부”만 쓸 때 사용
증상: 키 존재 여부만 확인하는데 map 사용 → 불필요한 O(log n).
원인: 순서가 필요 없으면 unordered_map/unordered_set이 평균 O(1).
해결:
// ❌ 나쁜 예: 순서 불필요한데 map
std::map<int, bool> seen;
if (seen.count(x)) { ....} // O(log n)
// ✅ 좋은 예
std::unordered_set<int> seen;
if (seen.count(x)) { ....} // O(1) 평균에러 4: reserve/resize 미사용으로 재할당
증상: vector에 push_back만 하는데도 느림.
원인: 크기 예측 가능한데 reserve를 안 하면 재할당 발생.
해결:
// ❌ 나쁜 예
std::vector<int> v;
for (int i = 0; i < n; ++i) v.push_back(read());
// ✅ 좋은 예
std::vector<int> v;
v.reserve(n);
for (int i = 0; i < n; ++i) v.push_back(read());에러 5: erase-while-iterate 시 반복자 무효화
증상: 순회 중 삭제 시 크래시 또는 무한 루프.
원인: vector::erase 후 기존 반복자 무효화.
해결:
// ❌ 나쁜 예
for (auto it = v.begin(); it != v.end(); ++it) {
if (condition(*it)) {
v.erase(it); // it 무효화!
}
}
// ✅ 좋은 예: erase 반환값 사용
for (auto it = v.begin(); it != v.end(); ) {
if (condition(*it)) {
it = v.erase(it);
} else {
++it;
}
}에러 6: unordered_map에 커스텀 타입 키 — 해시 미정의
증상: 컴파일 에러.
원인: unordered_map은 키에 대해 hash와 operator== 필요.
해결:
struct Point {
int x, y;
bool operator==(const Point& o) const {
return x == o.x && y == o.y;
}
};
struct PointHash {
size_t operator()(const Point& p) const {
return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
}
};
std::unordered_map<Point, int, PointHash> m;에러 7: 빈 컨테이너에 top/front/back 접근
증상: 런타임 크래시 또는 undefined behavior.
원인: priority_queue::top(), vector::front() 등은 빈 상태에서 호출하면 UB.
해결:
// ❌ 위험
int x = pq.top(); // pq가 비어있으면 UB
// ✅ 안전
if (!pq.empty()) {
int x = pq.top();
}6. 성능 벤치마크
벤치마크 1: 앞쪽 삽입 10만 회
| 컨테이너 | 시간 (대략) | 비고 |
|---|---|---|
| vector (insert begin) | ~10초 | O(n²) |
| deque (push_front) | ~5ms | O(n) |
| list (push_front) | ~8ms | O(n) |
결론: 앞쪽 삽입이 많으면 vector는 피하고 deque 또는 list 사용. |
벤치마크 2: 검색 100만 회 (100만 개 데이터)
| 컨테이너 | 시간 (대략) | 비고 |
|---|---|---|
| map (find) | ~200ms | O(log n) |
| unordered_map (find) | ~50ms | O(1) 평균 |
| vector (find) | ~5000ms | O(n) |
| vector 정렬 + binary_search | ~100ms | O(log n) |
결론: 키 검색만 필요하면 unordered_map. 정렬된 vector + 이진 탐색도 대안. |
벤치마크 3: push_back 100만 회 (reserve 유무)
| 방식 | 시간 (대략) | 비고 |
|---|---|---|
| reserve 없이 | ~500ms | 재할당 20회 |
| reserve(1000000) | ~50ms | 재할당 0회 |
결론: 개수 예측 가능하면 reserve 필수. |
벤치마크 코드 예시
// 앞쪽 삽입 벤치마크 (개념)
#include <chrono>
#include <vector>
#include <deque>
#include <list>
void benchmark_front_insert() {
const int n = 100000;
auto start = std::chrono::high_resolution_clock::now();
std::vector<int> v;
for (int i = 0; i < n; ++i) v.insert(v.begin(), i);
auto end = std::chrono::high_resolution_clock::now();
// vector: 수 초
start = std::chrono::high_resolution_clock::now();
std::deque<int> d;
for (int i = 0; i < n; ++i) d.push_front(i);
end = std::chrono::high_resolution_clock::now();
// deque: 수 ms
}벤치마크 4: 순차 순회 100만 원소
| 컨테이너 | 시간 (대략) | 비고 |
|---|---|---|
| vector | ~5ms | 캐시 친화, 연속 메모리 |
| deque | ~8ms | 청크 단위로 접근 |
| list | ~15ms | 포인터 따라가기, 캐시 미스 |
| 결론: 순회가 주 연산이면 vector가 가장 빠름. |
벤치마크 5: 중간 삽입 1만 회 (10만 개 컨테이너)
| 컨테이너 | 시간 (대략) | 비고 |
|---|---|---|
| vector (중간 insert) | ~500ms | O(n) × 1만 |
| list (반복자 위치 알고 있을 때) | ~5ms | O(1) × 1만 |
| 결론: 중간 삽입이 많고 인덱스 접근이 없으면 list 고려. |
7. 프로덕션 패턴
패턴 1: 슬라이딩 윈도우 + deque
// 구간 [i, i+k) 내 최대값 O(n)
#include <deque>
#include <vector>
std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) {
std::deque<int> dq; // 인덱스 저장, 내림차순 유지
std::vector<int> result;
for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
dq.push_back(i);
if (i >= k - 1) result.push_back(nums[dq.front()]);
}
return result;
}패턴 2: Top-K 빈도 (unordered_map + partial_sort)
// 빈도 상위 k개 원소
#include <unordered_map>
#include <vector>
#include <algorithm>
std::vector<int> topKFrequent(const std::vector<int>& nums, int k) {
std::unordered_map<int, int> freq;
for (int x : nums) ++freq[x];
std::vector<std::pair<int, int>> pairs(freq.begin(), freq.end());
std::partial_sort(pairs.begin(), pairs.begin() + k, pairs.end(),
{ return a.second > b.second; });
std::vector<int> result;
for (int i = 0; i < k; ++i) result.push_back(pairs[i].first);
return result;
}패턴 3: 이벤트 스케줄러 (priority_queue)
// (시간, 이벤트) 최소 힙
#include <queue>
#include <vector>
void processEvents(std::vector<std::pair<int, int>> events) {
std::priority_queue<std::pair<int, int>,
std::vector<std::pair<int, int>>,
std::greater<>> pq(events.begin(), events.end());
while (!pq.empty()) {
auto [t, id] = pq.top();
pq.pop();
// 처리...
}
}패턴 4: 객체 풀 (vector + 재사용)
// 메모리 할당 최소화: vector로 풀 관리
#include <vector>
template<typename T>
class ObjectPool {
std::vector<T> pool;
std::vector<bool> inUse;
public:
explicit ObjectPool(size_t size) : pool(size), inUse(size, false) {}
T* acquire() {
for (size_t i = 0; i < pool.size(); ++i) {
if (!inUse[i]) {
inUse[i] = true;
return &pool[i];
}
}
return nullptr;
}
void release(T* obj) {
size_t idx = obj - pool.data();
inUse[idx] = false;
}
};패턴 5: 다중 키 조회 (map + unordered_map 조합)
// ID로 O(1), 이름으로 O(log n) 조회
#include <map>
#include <unordered_map>
#include <string>
class UserIndex {
std::unordered_map<int, User> byId;
std::map<std::string, int> nameToId;
public:
void add(User u) {
byId[u.id] = u;
nameToId[u.name] = u.id;
}
User* getById(int id) {
auto it = byId.find(id);
return it != byId.end() ? &it->second : nullptr;
}
User* getByName(const std::string& name) {
auto it = nameToId.find(name);
if (it == nameToId.end()) return nullptr;
return getById(it->second);
}
};베스트 프랙티스
1. const 참조로 전달
// ❌ 값 복사 (큰 컨테이너에 비효율)
void process(std::vector<int> v);
// ✅ const 참조
void process(const std::vector<int>& v);2. 범위 기반 for와 auto
// ✅ 읽기 전용
for (const auto& x : v) { ....}
// ✅ 복사 필요 시
for (auto x : v) { ....}
// ✅ 인덱스 필요 시
for (size_t i = 0; i < v.size(); ++i) { ....}3. 구조화된 바인딩 (C++17)
for (const auto& [k, v] : map) {
std::cout << k << " -> " << v << "\n";
}4. 알고리즘 + 람다 활용
// 조건에 맞는 요소 개수
int cnt = std::count_if(v.begin(), v.end(), { return x > 0; });
// 조건 만족하는 첫 위치
auto it = std::find_if(v.begin(), v.end(), { return x % 2 == 0; });5. nth_element로 k번째 원소만
// 전체 정렬 O(n log n) 대신 O(n) 평균
std::nth_element(v.begin(), v.begin() + k, v.end());
int kth = v[k];정리
| 패턴 | 먼저 떠올릴 컨테이너 |
|---|---|
| 인덱스·뒤쪽 삽입 위주 | vector (+ reserve) |
| 앞뒤 삽입 많음 | deque |
| 중간 삽입·반복자 안정 | list |
| 키 조회, 순서·범위 필요 | map / set |
| 키 조회, 순서 불필요 | unordered_map / unordered_set |
핵심 원칙:
- 근거 없이
list를 고르지 않기 vector앞쪽insert남발은 O(n²)로 이어질 수 있음- “정렬된 범위에서만 찾는다”면 정렬
vector+lower_bound후보
초보자를 위한 체크리스트
- 맨 앞 삽입이 많은데
vector를 고집하지 않았는가? -
unordered_*사용 시reserve·해시 품질을 고려했는가? - 순회 중
erase후 반복자를 갱신했는가?
💡 초보자 팁: 아래 8. 구현 체크리스트·1. 문제 시나리오를 함께 보면 선택이 수월합니다.
8. 구현 체크리스트
컨테이너 선택 체크리스트
- 인덱스 접근이 필요한가? → vector
- 앞쪽 삽입/삭제가 많은가? → deque
- 중간 삽입/삭제가 많고 반복자 유지하는가? → list
- 키 검색만 필요하고 순서 불필요한가? → unordered_map/set
- 키 순서·범위 쿼리가 필요한가? → map/set
- vector 사용 시 개수 예측 가능한가? → reserve 호출
- 정렬된 범위에서 검색하는가? → lower_bound, binary_search
- 순회 중 삭제하는가? → erase 반환값으로 반복자 갱신
성능 체크리스트
- vector: reserve로 재할당 최소화
- map vs unordered_map: 순서 필요 여부 확인
- 정렬된 데이터: find 대신 lower_bound
- k번째 원소만 필요: nth_element 고려
실무 팁
개발 시 주의사항
- [팁 1]: [설명]
// 예시 코드 - [팁 2]: [설명]
// 예시 코드 - [팁 3]: [설명]
디버깅 방법
- [방법 1]: [설명]
- [방법 2]: [설명]
- [방법 3]: [설명]
FAQ
Q: “기본적으로 뭘 쓰면 되나요?”
A: 시퀀스는 vector, 키-값 매핑은 unordered_map(순서 불필요 시) 또는 map(순서 필요 시). “모르겠으면 vector”가 안전한 기본값입니다.
Q: “list는 언제 쓰나요?”
A: (1) LRU 캐시처럼 splice로 O(1) 이동이 필요할 때, (2) 반복자 무효화 없이 중간 삽입/삭제가 많을 때. 대부분의 경우 vector나 deque로 충분합니다.
Q: “unordered_map이 map보다 항상 빠른가요?”
A: 평균적으로는 그렇지만, 해시 충돌이 많으면 느려질 수 있습니다. 키 개수가 적으면(수백 개 이하) map이 나을 수도 있고, 데이터에 따라 프로파일링이 필요합니다.
Q: “reserve를 얼마나 잡아야 하나요?”
A: 정확한 개수를 모르면 “대략 최대치”만 예상해도 효과가 큽니다. 너무 크게 잡으면 메모리만 낭비하므로, 로그나 히스토리로 상한을 추정하는 것이 좋습니다.
Q: “정렬된 vector와 set 중 뭘 쓰나요?”
A: (1) 한 번 만들고 검색만 많으면 정렬된 vector + lower_bound가 캐시 친화적이라 빠를 수 있음. (2) 삽입/삭제가 동적으로 반복되면 set이 O(log n)으로 유리.
참고 자료
이전 글: [C++ std::function | 콜백·전략 패턴과 함수 객체](/blog/cpp-series-13-2-function-objects/
다음 글: (시리즈 목차 참고)
같이 보면 좋은 글 (내부 링크)
이 주제와 연결되는 다른 글입니다.
- C++ vector 성능 | “100만 개 넣는데 10초” 문제와 reserve
- C++ map vs unordered_map | “어떤 걸 써야 하죠?” 선택 기준과 성능 비교
- C++ 코테용 STL 컨테이너/알고리즘 시간복잡도 치트시트 [#32-3]
이 글에서 다루는 키워드 (관련 검색어)
C++, STL, vector, list, deque, map, set, unordered_map, 컨테이너선택, 시간복잡도 등으로 검색하시면 이 글이 도움이 됩니다.
관련 글
- C++ vector 기초 완벽 가이드 | 초기화·연산·용량 관리와 실전 패턴
- C++ map·set 완벽 가이드 | ordered vs unordered· 커스텀 키
- C++ 람다 표현식 | [=]·[&] 캡처와 sort·find_if에서 람다 활용법
- C++ std::function | 콜백·전략 패턴과 함수 객체
- C++ vector vs list vs deque |
심화 부록: 구현·운영 관점
이 부록은 앞선 본문에서 다룬 주제(「C++ 컨테이너 선택 가이드 | vector/list/deque/map/set 상황별 선택과 성능 최적화」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(I/O·네트워크·동시성) → 관측의 흐름으로 장애를 나누면 원인 추적이 빨라집니다.
내부 동작과 핵심 메커니즘
flowchart TD A[입력·요청·이벤트] --> B[파싱·검증·디코딩] B --> C[핵심 연산·상태 전이] C --> D[부작용: I/O·네트워크·동시성] D --> E[결과·관측·저장]
sequenceDiagram participant C as 클라이언트/호출자 participant B as 경계(런타임·게이트웨이·프로세스) participant D as 의존성(API·DB·큐·파일) C->>B: 요청/이벤트 B->>D: 조회·쓰기·RPC D-->>B: 지연·부분 실패·재시도 가능 B-->>C: 응답 또는 오류(코드·상관 ID)
- 불변 조건(Invariant): 버퍼 경계, 프로토콜 상태, 트랜잭션 격리, FD 상한 등 단계별로 문장으로 적어 두면 디버깅 비용이 줄어듭니다.
- 결정성: 순수 층과 시간·네트워크·스케줄에 의존하는 층을 분리해야 테스트와 장애 분석이 쉬워집니다.
- 경계 비용: 직렬화, 인코딩, syscall 횟수, 락 경합, 할당·GC, 캐시 미스를 의심 목록에 둡니다.
- 백프레셔: 생산자가 소비자보다 빠를 때 버퍼·큐·스트림에서 속도를 줄이는 신호를 어디에 둘지 정의합니다.
프로덕션 운영 패턴
| 영역 | 운영 관점 질문 |
|---|---|
| 관측성 | 요청 단위 상관 ID, 에러율·지연 p95/p99, 의존성 타임아웃·재시도가 대시보드에 보이는가 |
| 안전성 | 입력 검증·권한·비밀·감사 로그가 코드 경로마다 일관적인가 |
| 신뢰성 | 재시도는 멱등 연산에만 적용되는가, 서킷 브레이커·백오프·DLQ가 있는가 |
| 성능 | 캐시·배치 크기·커넥션 풀·인덱스·백프레셔가 데이터 규모에 맞는가 |
| 배포 | 롤백 룬북, 카나리/블루그린, 마이그레이션·피처 플래그가 문서화되어 있는가 |
| 용량 | 피크 트래픽·디스크·FD·스레드 풀 상한을 주기적으로 검증하는가 |
스테이징은 데이터 양·네트워크 RTT·동시성을 프로덕션에 가깝게 맞출수록 재현율이 올라갑니다.
확장 예시: 엔드투엔드 미니 시나리오
앞선 본문 주제(「C++ 컨테이너 선택 가이드 | vector/list/deque/map/set 상황별 선택과 성능 최적화」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.
- 입력 계약 고정: 스키마·버전·최대 페이로드·타임아웃·에러 코드를 경계에 둔다.
- 핵심 경로 계측: 요청 ID, 단계별 지연, 외부 호출 결과 코드를 로그·메트릭·트레이스에서 한 흐름으로 본다.
- 실패 주입: 의존성 타임아웃·5xx·부분 데이터·락 대기를 스테이징에서 재현한다.
- 호환·롤백: 설정/마이그레이션/클라이언트 버전을 되돌릴 수 있는지 확인한다.
- 부하 후 검증: 피크 대비 p95/p99, 에러율, 리소스 상한, 알림 임계값을 점검한다.
handle(request):
ctx = newCorrelationId()
validated = validateSchema(request)
authorize(validated, ctx)
result = domainCore(validated)
persistOrEmit(result, idempotentKey)
recordMetrics(ctx, latency, outcome)
return result문제 해결(Troubleshooting)
| 증상 | 가능 원인 | 조치 |
|---|---|---|
| 간헐적 실패 | 레이스, 타임아웃, 외부 의존성, DNS | 최소 재현 스크립트, 분산 트레이스·로그 상관관계, 재시도·서킷 설정 점검 |
| 성능 저하 | N+1, 동기 I/O, 락 경합, 과도한 직렬화, 캐시 미스 | 프로파일러·APM으로 핫스팟 확인 후 한 가지씩 제거 |
| 메모리 증가 | 캐시 무제한, 구독/리스너 누수, 대용량 버퍼, 커넥션 미반납 | 상한·TTL·힙/FD 스냅샷 비교 |
| 빌드·배포만 실패 | 환경 변수, 권한, 플랫폼 차이, lockfile | CI 로그와 로컬 diff, 런타임·이미지 버전 핀 |
| 설정 불일치 | 프로필·시크릿·기본값, 리전 | 스키마 검증된 설정 단일 소스와 배포 매트릭스 표준화 |
| 데이터 불일치 | 비멱등 재시도, 부분 쓰기, 캐시 무효화 누락 | 멱등 키·아웃박스·트랜잭션 경계 재검토 |
권장 순서: (1) 최소 재현 (2) 최근 변경 범위 축소 (3) 환경·의존성 차이 (4) 관측으로 가설 검증 (5) 수정 후 회귀·부하 테스트.
배포 전에는 git add → git commit → git push 후 npm run deploy 순서를 권장합니다.