vector가 정말 90%의 경우에 최선인가요?

네, 맞습니다. 최신 벤치마크에서도 vector의 캐시 친화성이 다른 컨테이너를 압도합니다. 100,000개 요소 순회 시 vector는 0.06ms, list는 2.10ms(35배 느림), map은 4.50ms로 측정되었습니다. 이론적 복잡도보다 캐시 성능이 실제 성능을 지배합니다.

unordered_map은 항상 map보다 빠른가요?

아닙니다. 적절히 튜닝되면 10-30% 빠르지만, 해시 충돌, 재해시 비용, 나쁜 해시 함수로 인해 오히려 느려질 수 있습니다. 순회가 빈번하거나 정렬이 필요하면 map이 더 나을 수 있습니다.

vector의 재할당 비용을 어떻게 줄이나요?

reserve()로 미리 용량을 확보하는 것이 핵심입니다. 재할당은 O(n) 복사/이동 비용이 들고 모든 반복자를 무효화합니다. 예상 크기를 알고 있다면 반드시 reserve()를 호출하세요.

프로덕션에서 가장 먼저 점검할 항목은?

1) 핫 경로의 재할당/재해시 빈도, 2) 반복자 수명(특히 범위 for + 수정), 3) 해시 함수 품질과 최악 입력 가능성입니다. 이 세 가지를 프로파일러와 Sanitizer로 확인하면 대부분의 문제가 드러납니다.

C++ STL 컨테이너 완벽 마스터 | 성능 비교부터 실전 최적화까지

2024년 3월 20일 · 55분 읽기 · 수정 2026년 5월 12일 고급 완벽가이드

이 글의 핵심

STL 컨테이너의 내부 동작부터 극한 성능 최적화까지. 반복자 무효화, 메모리 레이아웃, 캐시 성능, 실측 벤치마크, 프로덕션 튜닝 기법을 망라한 국내 최고 수준의 종합 가이드입니다.

들어가며: 캐시 성능이 Big-O를 이긴다

STL 컨테이너를 선택할 때 우리는 흔히 시간 복잡도 표를 먼저 봅니다. vector는 삽입이 O(n), list는 O(1)이니까 삽입이 빈번하면 list가 낫겠지? 틀렸습니다.

현대 CPU에서는 캐시 성능이 이론적 복잡도보다 훨씬 중요합니다. 최신 벤치마크 결과:

100,000개 요소 순회 (2026년 측정)
- std::vector:  0.06ms
- std::list:    2.10ms (35배 느림!)
- std::map:     4.50ms (75배 느림!)

왜 이런 차이가 날까요? 캐시 미스 때문입니다. 메인 메모리 접근은 L1 캐시보다 50-100배 느립니다. vector는 연속 메모리라 캐시 라인(64바이트)을 최대한 활용하지만, list와 map은 포인터를 따라가며 캐시 미스를 유발합니다.

이 가이드는 STL 컨테이너의 내부 메커니즘부터 실전 최적화까지 완벽하게 다룹니다.

1. 캐시와 메모리 계층 이해

1.1 현대 CPU의 메모리 계층

CPU 레지스터
    ↓ ~1 cycle
L1 캐시 (32-64KB)
    ↓ ~4 cycles
L2 캐시 (256KB-1MB)
    ↓ ~12 cycles
L3 캐시 (8-32MB, 코어 간 공유)
    ↓ ~40 cycles
메인 메모리 (GB)
    ↓ ~200 cycles (50배 이상 느림!)

핵심: 캐시 미스 1회 = 50-100 사이클 손실. 데이터를 순차적으로 접근하면 캐시 프리페칭(prefetching)이 작동하여 성능이 극대화됩니다.

1.2 캐시 라인 (Cache Line)

대부분의 x86-64 시스템에서 캐시 라인은 64바이트입니다.

// 한 번의 메모리 접근으로 64바이트 전체가 캐시로 로드됨
int arr[16];  // 16 * 4 = 64바이트 = 정확히 1 캐시 라인

arr[0] = 1;   // 메인 메모리 접근 (캐시 미스)
              // 이때 arr[0]부터 arr[15]까지 전부 캐시로 로드
arr[1] = 2;   // 캐시 적중! (이미 로드됨)
arr[15] = 3;  // 캐시 적중!

시사점:

vector: 연속 메모리 → 캐시 라인 최대 활용
list: 노드가 흩어짐 → 매번 캐시 미스
map: 트리 노드가 흩어짐 → 매번 캐시 미스

1.3 공간 지역성 (Spatial Locality)

// ✓ 좋음: 순차 접근 (공간 지역성 활용)
for (size_t i = 0; i < vec.size(); ++i) {
    process(vec[i]);  // 다음 요소가 이미 캐시에 있을 확률 높음
}

// ✗ 나쁨: 랜덤 접근 (캐시 미스 다발)
for (auto* node : linked_list) {
    process(node->data);  // 각 노드가 메모리 곳곳에 흩어져 있음
}

실측 결과: 순차 접근이 랜덤 접근보다 5-10배 빠릅니다.

2. 반복자 무효화 규칙

2.1 왜 중요한가?

무효화된 반복자를 사용하면 Undefined Behavior (UB)가 발생합니다. 디버그 빌드에서는 크래시가 나지만, 릴리즈 빌드에서는 조용히 잘못된 메모리를 읽어 찾기 어려운 버그를 만듭니다.

2.2 시퀀스 컨테이너 무효화 규칙

vector / string

std::vector<int> vec = {1, 2, 3, 4, 5};

// 1. push_back으로 인한 재할당
auto it = vec.begin();
vec.push_back(6);  // capacity 초과 → 재할당
// ❌ it는 무효화됨! 사용하면 UB

// 2. insert로 인한 부분 무효화
vec.clear();
vec = {1, 2, 3, 4, 5};
it = vec.begin() + 2;  // vec[2]를 가리킴
vec.insert(vec.begin() + 1, 99);  // 중간 삽입
// ❌ it는 무효화됨! (삽입 지점 이후 모두 무효)

// 3. erase로 인한 부분 무효화
vec.clear();
vec = {1, 2, 3, 4, 5};
it = vec.begin() + 2;
vec.erase(vec.begin() + 1);  // 중간 삭제
// ❌ it는 무효화됨! (삭제 지점 이후 모두 무효)

안전한 패턴:

// ✓ erase는 다음 유효한 반복자를 반환함
for (auto it = vec.begin(); it != vec.end(); ) {
    if (should_remove(*it)) {
        it = vec.erase(it);  // 반환값으로 갱신
    } else {
        ++it;
    }
}

// ✓ reserve로 재할당 방지
vec.reserve(1000);
for (int i = 0; i < 1000; ++i) {
    vec.push_back(i);  // 재할당 없음, 반복자 안전
}

deque

std::deque<int> dq = {1, 2, 3, 4, 5};

// 양 끝 연산: 참조는 유효, 반복자는 무효화될 수 있음
auto& ref = dq[2];
dq.push_back(6);    // ref는 여전히 유효
// 하지만 반복자는 무효화될 수 있음

// 중간 삽입/삭제: 모든 반복자 무효화
auto it = dq.begin();
dq.insert(dq.begin() + 2, 99);
// ❌ it 무효화!

주의: deque는 “양 끝만 건드리면 안전”이라는 오해가 많습니다. 표준은 양 끝 연산에서도 반복자 무효화를 허용합니다.

list / forward_list

std::list<int> lst = {1, 2, 3, 4, 5};

auto it = lst.begin();
++it;  // 두 번째 요소
lst.erase(it);  // it만 무효화, 다른 반복자는 유효!

// ✓ 노드 기반이라 다른 노드의 반복자는 안전
auto it2 = lst.begin();
lst.push_back(6);  // it2 여전히 유효

장점: 삽입/삭제 시 다른 반복자가 유효하게 유지됨. 단점: 캐시 미스로 인한 성능 저하.

2.3 연관 컨테이너 무효화 규칙

map / set (트리 기반)

std::map<int, std::string> m = {{1, "a"}, {2, "b"}, {3, "c"}};

auto it = m.find(2);
m.insert({4, "d"});  // ✓ it 여전히 유효!
m.erase(1);          // ✓ it 여전히 유효!
m.erase(it);         // ❌ it만 무효화, 다른 것들은 유효

특징: 노드 기반이므로 다른 노드의 반복자는 유효하게 유지됩니다.

unordered_map / unordered_set (해시 테이블)

std::unordered_map<int, std::string> um = {{1, "a"}, {2, "b"}};

auto it = um.find(1);

// 재해시가 발생하지 않으면 it 유효
um.insert({3, "c"});  // load_factor() < max_load_factor()면 OK

// 재해시 발생 시 모든 반복자 무효화!
um.reserve(1000);  // 재해시 발생
// ❌ it 무효화!

핵심: load_factor()가 max_load_factor()를 초과하면 재해시(rehash)가 발생하여 모든 반복자가 무효화됩니다.

2.4 범위 기반 for의 함정

std::vector<int> vec = {1, 2, 3, 4, 5};

// ❌ 위험한 패턴
for (int x : vec) {
    if (x % 2 == 0) {
        vec.push_back(x * 10);  // 재할당 → UB!
    }
}

// ✓ 안전한 패턴 1: 인덱스 사용
size_t original_size = vec.size();
for (size_t i = 0; i < original_size; ++i) {
    if (vec[i] % 2 == 0) {
        vec.push_back(vec[i] * 10);
    }
}

// ✓ 안전한 패턴 2: 별도 컨테이너
std::vector<int> to_add;
for (int x : vec) {
    if (x % 2 == 0) {
        to_add.push_back(x * 10);
    }
}
vec.insert(vec.end(), to_add.begin(), to_add.end());

3. 컨테이너별 내부 구조

3.1 vector: 연속 메모리 배열

template<typename T>
class vector {
    T* data_;        // 데이터 배열 포인터
    size_t size_;    // 현재 요소 수
    size_t capacity_; // 할당된 용량
};

메모리 레이아웃:

[T0][T1][T2][T3][T4]... (연속된 힙 메모리)

장점:

캐시 친화적 (순차 접근 시 최고 성능)
인덱스 접근 O(1)
data() 포인터로 C API 연동 가능

단점:

중간 삽입/삭제 O(n)
재할당 시 O(n) 복사/이동

3.2 deque: 청크 배열

template<typename T>
class deque {
    T** map_;         // 청크 포인터 배열
    size_t map_size_;
    // 각 청크는 고정 크기 (예: 512바이트)
};

메모리 레이아웃:

map_ → [chunk0*][chunk1*][chunk2*]...
         ↓        ↓        ↓
       [T T T]  [T T T]  [T T T]

장점:

양 끝 삽입/삭제 O(1)
중간 접근도 O(1) (청크 + 오프셋 계산)

단점:

캐시 효율이 vector보다 낮음
메모리 오버헤드 (포인터 배열)

3.3 list: 이중 연결 리스트

template<typename T>
class list {
    struct Node {
        T data;
        Node* prev;
        Node* next;
    };
    Node* head_;
    Node* tail_;
    size_t size_;
};

메모리 레이아웃: 노드들이 힙 메모리에 흩어져 있음 (비연속)

장점:

삽입/삭제 O(1) (위치를 알고 있을 때)
반복자 안정성 (다른 노드 영향 없음)

단점:

심각한 캐시 미스 (35배 느림!)
메모리 오버헤드 (포인터 2개)
인덱스 접근 O(n)

3.4 map: 레드-블랙 트리

template<typename Key, typename Value>
class map {
    struct Node {
        std::pair<Key, Value> data;
        Node* parent;
        Node* left;
        Node* right;
        Color color;  // 레드-블랙 트리 색상
    };
    Node* root_;
    size_t size_;
};

특징:

자가 균형 이진 탐색 트리
키가 항상 정렬됨
탐색/삽입/삭제 O(log n)

장점:

정렬된 순회
범위 쿼리 (lower_bound, upper_bound)
최악의 경우에도 O(log n) 보장

단점:

캐시 미스 (노드가 흩어짐)
메모리 오버헤드 (포인터 3개 + 색상)

3.5 unordered_map: 해시 테이블

template<typename Key, typename Value>
class unordered_map {
    struct Node {
        std::pair<Key, Value> data;
        Node* next;  // 체이닝용
    };
    std::vector<Node*> buckets_;  // 버킷 배열
    size_t size_;
    float max_load_factor_;  // 기본 1.0
};

메모리 레이아웃:

buckets_ → [bucket0*][bucket1*][bucket2*]...
             ↓         ↓         ↓
           [Node]→[Node]  [Node]  nullptr

장점:

평균 O(1) 탐색/삽입/삭제
map보다 10-30% 빠를 수 있음

단점:

해시 충돌 시 O(n)으로 저하
재해시 비용
정렬되지 않음

4. vector 완벽 가이드

4.1 성장 전략 (Growth Factor)

vector가 capacity를 초과하면 재할당이 발생합니다. 얼마나 늘릴까요?

표준은 명시하지 않지만 일반적인 구현:

GCC/Clang: 2배
MSVC: 1.5배

std::vector<int> vec;
vec.reserve(10);
std::cout << vec.capacity() << '\n';  // 10

for (int i = 0; i < 11; ++i) {
    vec.push_back(i);
    std::cout << vec.capacity() << '\n';
}
// 출력 (GCC): 10, 10, ..., 20 (재할당 발생)

4.2 reserve의 중요성

// ❌ 나쁨: 여러 번 재할당
std::vector<int> vec;
for (int i = 0; i < 1000; ++i) {
    vec.push_back(i);  // log2(1000) ≈ 10회 재할당
}

// ✓ 좋음: 한 번에 할당
std::vector<int> vec;
vec.reserve(1000);
for (int i = 0; i < 1000; ++i) {
    vec.push_back(i);  // 재할당 없음!
}

벤치마크:

reserve 없음: ~150μs (재할당 + 복사 비용)
reserve 사용: ~50μs (3배 빠름)

4.3 shrink_to_fit의 함정

std::vector<int> vec(1000000);
vec.clear();  // size는 0, capacity는 여전히 1000000

vec.shrink_to_fit();  // capacity를 size에 맞춤 (요청일 뿐, 강제 아님)

주의:

shrink_to_fit()은 요청(request)일 뿐, 구현이 무시할 수 있음
재할당 비용 발생
대부분의 경우 불필요 (메모리 프로파일링 후 결정)

4.4 emplace_back vs push_back

struct Heavy {
    std::string data;
    Heavy(std::string s) : data(std::move(s)) {}
};

std::vector<Heavy> vec;

// push_back: 임시 객체 생성 → 이동
vec.push_back(Heavy("temp"));  // 1. Heavy("temp") 생성
                               // 2. 이동 생성자 호출

// emplace_back: 제자리 생성 (더 효율적)
vec.emplace_back("temp");      // Heavy가 vector 내부에서 직접 생성

규칙:

새 객체를 생성할 때: emplace_back
이미 존재하는 객체를 복사할 때: push_back

5. unordered_map 최적화

5.1 로드 팩터 (Load Factor)

std::unordered_map<int, std::string> um;

std::cout << um.load_factor() << '\n';      // size() / bucket_count()
std::cout << um.max_load_factor() << '\n';  // 기본 1.0

로드 팩터 = 평균 버킷당 요소 수

낮으면: 메모리 낭비, 하지만 충돌 적음
높으면: 메모리 절약, 하지만 충돌 많음 → 체인 길어짐 → O(n)

5.2 reserve와 rehash

std::unordered_map<int, std::string> um;

// ❌ 나쁨: 재해시 여러 번
for (int i = 0; i < 10000; ++i) {
    um[i] = "value";  // 중간에 여러 번 재해시 발생
}

// ✓ 좋음: 미리 예약
std::unordered_map<int, std::string> um;
um.reserve(10000);  // 재해시 없이 10000개 수용 가능
for (int i = 0; i < 10000; ++i) {
    um[i] = "value";
}

재해시 비용: 모든 요소를 새 버킷 배열로 재배치 → O(n)

5.3 커스텀 해시 함수

기본 std::hash는 일부 타입에서 비효율적일 수 있습니다.

struct Point {
    int x, y;
    
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 커스텀 해시
struct PointHash {
    size_t operator()(const Point& p) const {
        // Boost hash_combine 스타일
        size_t seed = 0;
        seed ^= std::hash<int>{}(p.x) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        seed ^= std::hash<int>{}(p.y) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        return seed;
    }
};

std::unordered_map<Point, std::string, PointHash> map;

5.4 보안: 해시 충돌 공격

악의적인 입력으로 모든 키가 같은 버킷에 들어가게 하면 O(1) → O(n) 성능 저하.

대응책:

랜덤 시드 사용 (일부 구현 지원)
입력 검증 (의심스러운 패턴 거부)
map 사용 (최악의 경우에도 O(log n) 보장)

6. map vs unordered_map 선택 가이드

6.1 결정 트리

flowchart TD
    A[컨테이너 선택] --> B{정렬이 필요한가?}
    B -->|예| C[map 사용]
    B -->|아니오| D{범위 쿼리가 필요한가?}
    D -->|예| C
    D -->|아니오| E{순회가 빈번한가?}
    E -->|예| C
    E -->|아니오| F{악의적 입력 가능성?}
    F -->|예| C
    F -->|아니오| G[unordered_map 사용]
    G --> H[reserve 호출 필수!]

6.2 실측 벤치마크 (2026)

테스트 환경: x86-64, GCC 13.2, -O3, 100만 요소

작업	map	unordered_map (기본)	unordered_map (reserve)
삽입	180ms	120ms	85ms
탐색	95ms	35ms	35ms
순회	15ms	45ms	45ms
삭제	170ms	110ms	110ms

결론:

탐색 중심: unordered_map이 2.7배 빠름
순회 중심: map이 3배 빠름
reserve 효과: unordered_map 삽입이 1.4배 빠름

6.3 메모리 사용량

// 100만 개 <int, int> 저장
std::map<int, int>:           ~48MB
std::unordered_map<int, int>: ~36MB (기본 load factor)

unordered_map이 약간 더 적게 사용 (버킷 배열 vs 트리 노드).

7. 실전 벤치마크

7.1 삽입 성능

// 벤치마크 코드
constexpr size_t N = 100000;

// vector (reserve 있음)
std::vector<int> vec;
vec.reserve(N);
auto start = std::chrono::high_resolution_clock::now();
for (size_t i = 0; i < N; ++i) {
    vec.push_back(i);
}
auto end = std::chrono::high_resolution_clock::now();
// 결과: ~1ms

// list
std::list<int> lst;
start = std::chrono::high_resolution_clock::now();
for (size_t i = 0; i < N; ++i) {
    lst.push_back(i);
}
end = std::chrono::high_resolution_clock::now();
// 결과: ~8ms (8배 느림!)

7.2 탐색 성능

// vector: 선형 탐색
auto it = std::find(vec.begin(), vec.end(), target);
// O(n), 하지만 캐시 친화적: ~0.3ms

// map: 이진 탐색 트리
auto it = map.find(target);
// O(log n), 캐시 미스: ~0.08ms

// unordered_map: 해시
auto it = um.find(target);
// O(1) 평균: ~0.02ms (4배 빠름!)

7.3 순회 성능

// vector
for (int x : vec) { sum += x; }
// 결과: 0.06ms (최고!)

// list
for (int x : lst) { sum += x; }
// 결과: 2.10ms (35배 느림!)

// map
for (auto& [k, v] : map) { sum += v; }
// 결과: 4.50ms (75배 느림!)

8. 프로덕션 최적화 패턴

8.1 “vector를 먼저 고려하라”

// ❌ 습관적으로 list 사용
std::list<Item> items;
for (auto& item : source) {
    items.push_back(process(item));
}

// ✓ 대부분의 경우 vector가 더 빠름
std::vector<Item> items;
items.reserve(source.size());
for (auto& item : source) {
    items.push_back(process(item));
}

경험 법칙: N < 10,000이면 vector의 O(n) 삽입도 list보다 빠른 경우가 많음.

8.2 소형 벡터 최적화 (SVO)

// 작은 크기의 데이터에는 vector가 압도적
std::vector<int> small_vec = {1, 2, 3};  // 힙 할당 1회
std::list<int> small_lst = {1, 2, 3};    // 힙 할당 3회 + 노드 오버헤드

8.3 flat_map 패턴

정렬된 vector로 map을 흉내 내는 패턴:

// Boost.Container의 flat_map 스타일
template<typename K, typename V>
class flat_map {
    std::vector<std::pair<K, V>> data_;
    
public:
    auto find(const K& key) {
        auto it = std::lower_bound(data_.begin(), data_.end(), key,
            [](const auto& p, const K& k) { return p.first < k; });
        if (it != data_.end() && it->first == key)
            return it;
        return data_.end();
    }
    // 삽입 시 정렬 유지
};

장점:

순회 시 map보다 10배 빠름 (캐시 친화적)
탐색도 작은 N에서는 더 빠름

단점: 삽입/삭제 O(n)

용도: 읽기 위주, 드물게 수정

8.4 unordered_map 튜닝 체크리스트

std::unordered_map<Key, Value> um;

// 1. 미리 예약
um.reserve(expected_size);

// 2. 로드 팩터 조정 (선택적)
um.max_load_factor(0.75f);  // 충돌 감소, 메모리 증가

// 3. 커스텀 해시 (필요 시)
std::unordered_map<Key, Value, CustomHash> um;

// 4. 재해시 모니터링
auto old_bucket_count = um.bucket_count();
// ... 삽입 ...
if (um.bucket_count() != old_bucket_count) {
    // 재해시 발생! 성능 영향 확인
}

8.5 메모리 풀 패턴

빈번한 할당/해제 시:

// 커스텀 할당자 사용
template<typename T>
class PoolAllocator {
    // 메모리 풀 구현
};

std::vector<int, PoolAllocator<int>> vec;
std::list<int, PoolAllocator<int>> lst;

효과: 힙 할당 오버헤드 제거, 단편화 감소.

8.6 “측정 없이 최적화하지 말라”

// 프로파일링 도구
// - perf (Linux)
// - Instruments (macOS)
// - VTune (Intel)
// - Visual Studio Profiler

// 컨테이너 선택은 항상 벤치마크로 검증

9. 정리 및 권장사항

9.1 컨테이너 선택 플로우차트

flowchart TD
    Start[컨테이너 선택] --> Q1{크기가 고정?}
    Q1 -->|예| Array[std::array]
    Q1 -->|아니오| Q2{순차 접근 위주?}
    Q2 -->|예| Vector[std::vector]
    Q2 -->|아니오| Q3{키-값 쌍?}
    Q3 -->|아니오| Q4{양 끝 삽입/삭제?}
    Q4 -->|예| Deque[std::deque]
    Q4 -->|아니오| Q5{반복자 안정성 필수?}
    Q5 -->|예| List[std::list]
    Q5 -->|아니오| Vector
    
    Q3 -->|예| Q6{정렬 필요?}
    Q6 -->|예| Map[std::map]
    Q6 -->|아니오| Q7{순회 빈번?}
    Q7 -->|예| Map
    Q7 -->|아니오| UMap[std::unordered_map
+ reserve]

9.2 핵심 원칙

기본은 vector: 90%의 경우 최선
reserve는 필수: 재할당 비용 제거
캐시가 왕: 이론적 복잡도 < 실제 메모리 접근 패턴
측정하라: 프로파일링 없이 최적화하지 말 것
반복자 수명 관리: 무효화 규칙 숙지

9.3 성능 체크리스트

핫 경로에서 vector reserve 사용
unordered_map에 reserve 호출
불필요한 복사 제거 (emplace_back)
범위 for + 수정 시 반복자 무효화 확인
해시 함수 품질 검증
프로파일러로 캐시 미스 확인

참고 자료

필수 문서

벤치마크 연구

이 가이드가 STL 컨테이너 마스터에 도움이 되길 바랍니다! 질문이나 피드백은 언제든 환영합니다.

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

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

이 글이 도움이 되셨나요?

여러분의 피드백은 더 나은 콘텐츠를 만드는 데 도움이 됩니다

문제가 있거나 개선 제안이 있으시면 연락처로 알려주세요.

이 글의 핵심

들어가며: 캐시 성능이 Big-O를 이긴다

목차

1. 캐시와 메모리 계층 이해

1.1 현대 CPU의 메모리 계층

1.2 캐시 라인 (Cache Line)

1.3 공간 지역성 (Spatial Locality)

2. 반복자 무효화 규칙

2.1 왜 중요한가?

2.2 시퀀스 컨테이너 무효화 규칙

vector / string

deque

list / forward_list

2.3 연관 컨테이너 무효화 규칙

map / set (트리 기반)

unordered_map / unordered_set (해시 테이블)

2.4 범위 기반 for의 함정

3. 컨테이너별 내부 구조

3.1 vector: 연속 메모리 배열

3.2 deque: 청크 배열

3.3 list: 이중 연결 리스트

3.4 map: 레드-블랙 트리

3.5 unordered_map: 해시 테이블

4. vector 완벽 가이드

4.1 성장 전략 (Growth Factor)

4.2 reserve의 중요성

4.3 shrink_to_fit의 함정

4.4 emplace_back vs push_back

5. unordered_map 최적화

5.1 로드 팩터 (Load Factor)

5.2 reserve와 rehash

5.3 커스텀 해시 함수

5.4 보안: 해시 충돌 공격

6. map vs unordered_map 선택 가이드

6.1 결정 트리

6.2 실측 벤치마크 (2026)

6.3 메모리 사용량

7. 실전 벤치마크

7.1 삽입 성능

7.2 탐색 성능

7.3 순회 성능

8. 프로덕션 최적화 패턴

8.1 “vector를 먼저 고려하라”

8.2 소형 벡터 최적화 (SVO)

8.3 flat_map 패턴

8.4 unordered_map 튜닝 체크리스트

8.5 메모리 풀 패턴

8.6 “측정 없이 최적화하지 말라”

9. 정리 및 권장사항

9.1 컨테이너 선택 플로우차트

9.2 핵심 원칙

9.3 성능 체크리스트

참고 자료

필수 문서

벤치마크 연구

관련 글

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

이 글이 도움이 되셨나요?