C++ 컨테이너 선택 가이드 | vector/list/deque/map/set 상황별 선택과 성능 최적화

초보자를 위한 한 줄: 시퀀스 컨테이너는 기본적으로 vector를 쓰면 안전합니다. 맨 앞 삽입이 잦으면 deque, 중간 삽입과 반복자 안정성이 핵심이면 list를 떠올리세요. 연관 컨테이너는 순서나 범위 쿼리가 필요하면 map, 필요 없으면 unordered_map을 씁니다. C++ std::vector 기초: 생성·삽입·삭제와 배열 대신 쓰는 이유·C++ map·unordered_map·flat_map: 성능 비교와 선택 기준과 세트로 보면 좋습니다.

들어가며: 컨테이너를 잘못 골라서 시간 초과가 났습니다

로그를 시간 역순으로 저장하려고 vector의 맨 앞에 insert를 반복했습니다. 데이터가 10만 건 정도만 되어도 눈에 띄게 느려집니다.

vector::insert(begin(), x)는 O(n)입니다. 맨 앞에 넣으면 뒤쪽 원소를 전부 한 칸씩 밀어야 하기 때문입니다. 이것을 n번 반복하면 전체 비용이 O(n²)가 되고, 10만 건이면 원소 이동이 약 50억 번(1+2+…+n) 일어납니다.

// ❌ 나쁜 예: 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

---

앞쪽 삽입, 잘못된 검색, 재할당 폭발: 컨테이너 선택 실수 사례

시나리오 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 — 재할당 폭발

증상: 원소가 큰 객체이거나 이동 생성자가 noexcept가 아닌데 push_back을 대량으로 반복하니 예상보다 느림. 원인: vector는 capacity가 부족하면 더 큰 버퍼를 할당하고 기존 원소를 모두 옮깁니다(libstdc++·libc++는 2배, MSVC는 1.5배 성장). 성장 배수 덕분에 전체 비용은 amortized O(1)이지만, 재할당마다 할당과 복사/이동이 일어나고 기존 포인터·반복자가 무효화됩니다. 이동 생성자가 noexcept가 아니면 이동 대신 복사가 쓰여 비용이 더 커집니다. 해결: 개수를 예측할 수 있으면 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)에 가까워집니다. 해시 함수를 아는 공격자가 충돌하는 키만 골라 보내는 공격도 가능합니다. 해결: 외부 입력을 키로 받는다면 최악 O(log n)이 보장되는 std::map을 쓰거나, 무작위 시드를 섞은 커스텀 해시를 씁니다. reserve는 재해시 횟수를 줄여줄 뿐 충돌 공격은 막지 못합니다.

---

시퀀스 컨테이너: 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). 메모리 오버헤드 큼, 캐시 비친화.

---

연관 컨테이너: 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]

---

DP, BFS, LRU 캐시, 범위 쿼리별 컨테이너 예제

예제 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: unordered_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");

---

vector 앞쪽 삽입 TLE, 정렬된 배열에 find 같은 선택 에러

에러 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;
    }
}

어떤 연산이 무엇을 무효화하는지는 컨테이너마다 다르고, “반복자”와 “참조·포인터”가 따로 무효화되기도 합니다. 순회 중 수정하는 코드를 쓸 때는 아래 규칙을 기준으로 판단합니다.

컨테이너	삽입 시	삭제 시
vector	재할당이 일어나면 전부, 아니면 삽입 위치 이후	삭제 위치 이후 (끝 반복자 포함)
deque	양 끝 삽입은 반복자 전부(참조는 유지), 중간 삽입은 반복자·참조 전부	양 끝 삭제는 지운 원소만(pop_back은 끝 반복자도), 중간 삭제는 전부
list, map, set	없음	지운 원소만
unordered_*	rehash가 일어나면 반복자 전부(참조는 유지), 아니면 없음	지운 원소만

unordered_map에 원소를 넣으면서 반복자를 들고 있는 코드는 테스트처럼 원소가 적을 때는 rehash가 일어나지 않아 멀쩡하다가 데이터가 늘면 깨지므로, 미리 reserve해 두거나 삽입과 순회를 분리하는 편이 안전합니다.

에러 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();
}

---

앞쪽 삽입, 검색, 순회 벤치마크

벤치마크 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 없이	수 ms 수준	재할당 약 20회(2배 성장 기준)
reserve(1000000)	그보다 조금 빠름	재할당 0회

결론: int 같은 작은 원소에서는 amortized O(1) 덕분에 차이가 크지 않습니다. 원소가 크거나 포인터·반복자를 보관해야 할 때 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 고려.

---

슬라이딩 윈도우, Top-K, 이벤트 스케줄러, 객체 풀

패턴 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(),
         [](const std::pair<int, int>& a, const std::pair<int, int>& b) { 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>
struct User {
    int id;
    std::string name;
};
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);
    }
};

---

컨테이너를 다룰 때의 코드 습관

const 참조로 전달

// ❌ 값 복사 (큰 컨테이너에 비효율)
void process(std::vector<int> v);
// ✅ const 참조
void process(const std::vector<int>& v);

범위 기반 for와 auto

// ✅ 읽기 전용
for (const auto& x : v) { ... }
// ✅ 복사 필요 시
for (auto x : v) { ... }
// ✅ 인덱스 필요 시
for (size_t i = 0; i < v.size(); ++i) { ... }

구조화된 바인딩 (C++17)

for (const auto& [k, v] : map) {
    std::cout << k << " -> " << v << "\n";
}

알고리즘 + 람다 활용

// 조건에 맞는 요소 개수
int cnt = std::count_if(v.begin(), v.end(), [](int x) { return x > 0; });
// 조건 만족하는 첫 위치
auto it = std::find_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });

nth_element로 k번째 원소만

// 전체 정렬 O(n log n) 대신 O(n) 평균
std::nth_element(v.begin(), v.begin() + k, v.end());
int kth = v[k];

---

자주 쓰는 알고리즘의 시간복잡도

컨테이너를 골랐다면 그 위에서 돌릴 알고리즘의 비용도 함께 봐야 합니다. 특히 binary_search·lower_bound·upper_bound는 정렬된 범위에서만 의미가 있고, 정렬되지 않은 범위에 쓰면 에러 없이 틀린 답이 나옵니다. 전체 정렬이 필요 없다면 partial_sort(상위 k개)나 nth_element(k번째 원소만)로 비용을 줄일 수 있습니다.

알고리즘	시간복잡도	비고
sort	O(n log n)	안정 정렬 아님
stable_sort	O(n log n), 추가 메모리 없으면 O(n log² n)	같은 값의 원래 순서 유지
partial_sort	O(n log k)	상위 k개만 정렬
nth_element	평균 O(n)	k번째 원소만 제자리에
find, find_if, count	O(n)	선형 검색
binary_search, lower_bound, upper_bound	O(log n)	정렬된 범위 전용
merge	O(n + m)	두 정렬 구간 병합
unique	O(n)	인접 중복만 제거, 정렬 후 erase와 함께

lower_bound를 std::list나 std::set의 반복자에 쓰면 비교 횟수는 O(log n)이지만 반복자 이동이 O(n)이라 전체가 선형이 됩니다. set/map에서는 자유 함수가 아니라 멤버 함수 s.lower_bound(x)를 써야 트리를 따라 O(log n)에 찾습니다.

컨테이너 선택과 성능 체크리스트

선택 단계

• 인덱스 접근이 필요한가? → 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 고려

---

FAQ

”기본적으로 뭘 쓰면 되나요?”

시퀀스는 vector, 키-값 매핑은 순서가 필요 없으면 unordered_map, 필요하면 map을 씁니다. 잘 모르겠으면 vector가 안전한 기본값입니다.

”list는 언제 쓰나요?”

(1) LRU 캐시처럼 splice로 O(1) 이동이 필요할 때, (2) 반복자 무효화 없이 중간 삽입/삭제가 많을 때. 대부분의 경우 vector나 deque로 충분합니다.

”unordered_map이 map보다 항상 빠른가요?”

평균적으로는 그렇지만, 해시 충돌이 많으면 느려질 수 있습니다. 키 개수가 적으면(수백 개 이하) map이 나을 수도 있으며, 데이터에 따라 프로파일링이 필요합니다. O(1)은 평균 복잡도라서 충돌이 한 버킷에 몰리면 연산이 O(n)까지 느려지는데, 정수 키에 대한 기본 해시가 사실상 항등 함수인 구현이 많아 충돌을 노린 입력(코딩 테스트의 해킹 데이터 등)에 취약하고, reserve 없이 대량 삽입하면 rehash도 반복됩니다. 키 범위가 작으면 배열로 대체하고, 최악의 경우에도 O(log n)을 보장받아야 하면 map을 쓰거나 무작위 시드를 섞은 커스텀 해시로 충돌을 피합니다.

”reserve를 얼마나 잡아야 하나요?”

정확한 개수를 모르면 “대략 최대치”만 예상해도 효과가 큽니다. 너무 크게 잡으면 메모리만 낭비하므로, 로그나 히스토리로 상한을 추정하는 것이 좋습니다.

”정렬된 vector와 set 중 뭘 쓰나요?”

한 번 만들고 검색만 많이 한다면 정렬된 vector와 lower_bound 조합이 캐시 친화적이라 빠를 수 있습니다. 삽입과 삭제가 계속 반복된다면 각 연산이 O(log n)인 set이 유리합니다.

---

참고 자료

• cppreference - Containers
• cppreference - vector
• cppreference - map
• cppreference - unordered_map

---

이전 글: C++ std::function | 콜백·전략 패턴과 함수 객체
다음 글: (시리즈 목차 참고)

---

같이 보면 좋은 글

• C++ vector 성능: 캐시 친화성, 용량 성장 전략, reserve 최적화
• C++ map·unordered_map·flat_map: 성능 비교와 선택 기준
• C++ std::vector 기초: 생성·삽입·삭제와 배열 대신 쓰는 이유
• C++ 람다 표현식 | [=]·[&] 캡처와 sort·find_if에서 람다 활용법
• C++ std::function | 콜백·전략 패턴과 함수 객체
• C++ STL 컨테이너: 연산별 성능 비교와 상황별 선택 기준