vector·map·unordered_map 내부 구조와 복잡도·재할당 최적화

개요 — STL 컨테이너 선택의 중요성

STL 컨테이너 선택은 알고리즘 복잡도와 캐시 효율에 직접적인 영향을 미칩니다. vector와 map은 동일한 연산을 지원하더라도 내부 구조가 달라 성능 차이가 크게 납니다. 내부 구조를 이해해야 올바른 컨테이너를 선택하고 최적화할 수 있습니다.

---

1. std::vector — 동적 배열

1.1 내부 구조

[size=5, capacity=8]
 data 포인터
    ↓
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │   │   │   │  ← 연속 메모리
└───┴───┴───┴───┴───┴───┴───┴───┘
  0   1   2   3   4   5   6   7
  ←── size=5 ──→←── capacity-size=3 ──→

std::vector<int> v;
// 내부 상태
// data_: 힙에 할당된 배열 포인터
// size_: 실제 원소 수
// capacity_: 할당된 버퍼 크기

// size와 capacity 확인
std::cout << v.size()     << "\n"; // 0
std::cout << v.capacity() << "\n"; // 0 (구현마다 다름)

v.push_back(1);
v.push_back(2);
std::cout << v.size()     << "\n"; // 2
std::cout << v.capacity() << "\n"; // 2 (또는 그 이상)

1.2 재할당 전략

원소 추가 시 size == capacity이면 재할당이 발생합니다. 대부분의 구현에서 capacity를 2배 또는 1.5배로 늘립니다.

// 재할당 과정 (push_back)
// 1. 새 크기로 새 배열 할당
// 2. 기존 원소를 새 배열로 move (noexcept move 있을 때) 또는 copy
// 3. 기존 배열 해제
// 4. 포인터 교체

// 재할당 추적
std::vector<int> v;
v.reserve(1);
int* old_ptr = v.data();

for (int i = 0; i < 20; ++i)
{
    v.push_back(i);
    if (v.data() != old_ptr) {
        std::cout << "재할당 발생: size=" << v.size()
                  << " cap=" << v.capacity() << "\n";
        old_ptr = v.data();
    }
}
// 재할당 발생: size=2  cap=2
// 재할당 발생: size=3  cap=4
// 재할당 발생: size=5  cap=8
// 재할당 발생: size=9  cap=16
// 재할당 발생: size=17 cap=32

1.3 최적화 기법

// 최적화 1: reserve로 사전 할당
std::vector<int> v;
v.reserve(1000); // 재할당 없이 1000개 저장 가능

// 최적화 2: shrink_to_fit으로 여분 메모리 반환
v.shrink_to_fit(); // capacity를 size로 줄임 (보장은 아님)

// 최적화 3: emplace_back으로 불필요한 복사 제거
struct Point { int x, y; };
v.emplace_back(1, 2); // 인플레이스 생성 (push_back보다 효율적)

// 최적화 4: swap trick으로 메모리 완전 해제
std::vector<int> large(10000);
std::vector<int>().swap(large); // capacity = 0

// 최적화 5: 삽입 순서 — 뒤에서 삽입이 O(1), 앞에서 삽입은 O(n)
v.insert(v.begin(), 0); // O(n) — 모든 원소 이동
v.push_back(0);         // O(1) amortized — 빠름

1.4 시간 복잡도

연산	복잡도	비고
operator[], at()	O(1)	인덱스 직접 접근
push_back()	O(1) amortized	재할당 시 O(n)
emplace_back()	O(1) amortized	push_back보다 효율적
insert(iter, v)	O(n)	이후 원소 이동 필요
erase(iter)	O(n)	이후 원소 이동 필요
find (선형)	O(n)	정렬 시 O(log n) 이분탐색
size(), empty()	O(1)

---

2. std::map — 레드블랙트리

2.1 내부 구조

std::map은 **자가 균형 이진 탐색 트리(Red-Black Tree)**로 구현됩니다. 삽입/삭제 후에도 트리 높이가 O(log n)을 유지합니다.

        {4, "d"}         ← 루트 (Black)
       /         \
   {2,"b"}     {6,"f"}   (Red)
   /     \     /     \
{1,"a"}{3,"c"}{5,"e"}{7,"g"}  (Black)

- 모든 노드: key, value, color(R/B), left, right, parent 포인터
- 트리 높이: 최대 2*log2(n+1)
- 항상 정렬된 순서 유지

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

// 항상 정렬된 순서로 순회
for (const auto& [k, v] : m)
    std::cout << k << ":" << v << " "; // 1:a 2:b 3:c

// 각 노드는 힙에 독립 할당 — 포인터 3개(left, right, parent) + color
// 캐시 비친화적 (포인터 추적으로 캐시 미스 빈번)

2.2 주요 연산 복잡도

연산	복잡도	비고
find(key)	O(log n)	이진 탐색
insert()	O(log n)	삽입 위치 탐색 + 균형 조정
erase(key)	O(log n)	삭제 + 균형 조정
operator[]	O(log n)	없으면 기본값 삽입
lower_bound()	O(log n)	범위 탐색
begin(), end()	O(1)
순회	O(n)	항상 정렬 순서

2.3 map 최적화 기법

// 최적화 1: find vs operator[] — 없는 키에 operator[]는 기본값 삽입
std::map<std::string, int> m;
// if (m["없는키"] == 0) — 키가 없어도 삽입됨! 위험
auto it = m.find("없는키"); // 찾기만 하고 삽입 안 함
if (it != m.end()) { /* 존재 */ }

// 최적화 2: emplace/try_emplace — 불필요한 복사 제거
m.emplace("key", 42);
m.try_emplace("key", 42); // 키가 없을 때만 삽입 (C++17)

// 최적화 3: lower_bound로 삽입 힌트
auto hint = m.lower_bound("key");
m.insert(hint, {"key", 42}); // 힌트 활용 시 O(1) amortized

// 최적화 4: 노드 이전/추출 (C++17) — 복사 없이 이동
auto node = m.extract("key"); // 노드 추출 (O(log n))
m2.insert(std::move(node));   // 다른 map에 삽입

---

3. std::unordered_map — 해시 테이블

3.1 내부 구조

unordered_map은 **해시 테이블 + 체이닝(Chaining)**으로 구현됩니다.

버킷 배열 (bucket_count개)
[0] → nullptr
[1] → {key1, val1} → {key2, val2} → nullptr  (해시 충돌 → 연결 리스트)
[2] → {key3, val3} → nullptr
[3] → nullptr
...

load_factor = size / bucket_count
rehash 발생 조건: load_factor > max_load_factor (기본 1.0)

std::unordered_map<std::string, int> m;
std::cout << m.bucket_count()   << "\n"; // 초기 버킷 수
std::cout << m.load_factor()    << "\n"; // size / bucket_count
std::cout << m.max_load_factor()<< "\n"; // 기본 1.0

m["Alice"] = 95;
m["Bob"]   = 87;
std::cout << m.bucket("Alice")  << "\n"; // Alice가 속한 버킷 번호

3.2 주요 연산 복잡도

연산	평균 복잡도	최악 복잡도	비고
find(key)	O(1)	O(n)	해시 충돌 최악
insert()	O(1)	O(n)	rehash 발생 시 O(n)
erase(key)	O(1)	O(n)
operator[]	O(1)	O(n)	없으면 기본값 삽입
rehash()	O(n)	O(n)	전체 재해시

3.3 최적화 기법

// 최적화 1: reserve로 rehash 방지
std::unordered_map<std::string, int> m;
m.reserve(1000); // 최소 1000개를 rehash 없이 저장 가능하게 버킷 조정

// 최적화 2: max_load_factor 조정
m.max_load_factor(0.5); // 충돌 줄이기 (메모리 증가 감수)

// 최적화 3: 커스텀 해시
struct StringHash
{
    size_t operator()(const std::string& s) const
    {
        size_t hash = 14695981039346656037ull; // FNV 기반
        for (char c : s)
        {
            hash ^= static_cast<size_t>(c);
            hash *= 1099511628211ull;
        }
        return hash;
    }
};

std::unordered_map<std::string, int, StringHash> fast_map;

// 최적화 4: 정수 키는 기본 해시가 효율적
std::unordered_map<int, Data> int_map; // 정수 키는 ID 접근에 매우 빠름

---

4. 컨테이너 선택 가이드

4.1 접근 패턴별 비교

기준	vector	map	unordered_map
임의 접근 속도	O(1)	O(log n)	O(1) avg
순서 유지	삽입 순서	키 정렬 순서	없음
범위 검색	O(n)	O(log n)	불가
메모리 효율	최고	낮음 (노드 포인터)	중간
캐시 친화성	최고	낮음	중간
삽입/삭제 중간	O(n)	O(log n)	O(1) avg

4.2 선택 기준

키-값 저장이 필요한가?
  No  → vector / array / deque
  Yes → 키가 정렬 순서 필요한가?
          Yes → std::map / std::multimap
          No  → std::unordered_map (일반적으로 더 빠름)

자주 삽입/삭제가 중간 위치에서 일어나는가?
  Yes → std::list / std::deque
  No  → std::vector (캐시 효율 최고)

원소 수가 적은가? (< 수십 개)
  Yes → vector (선형 탐색이 캐시 효율상 더 빠를 수 있음)

---

5. 캐시 효율 — vector가 map보다 빠른 이유

// 벤치마크: 10만 개 정수 순차 합산
std::vector<int> v(100000, 1);
std::list<int>   l(100000, 1);

// vector: 캐시 라인(64바이트)에 16개 int가 들어감
// L1 캐시 미스 최소화 → 매우 빠름
int sum_v = 0;
for (int x : v) sum_v += x; // ~캐시 친화적

// list: 각 노드가 다른 힙 위치 → 포인터 추적마다 캐시 미스
// 같은 연산이 vector보다 5~10배 느릴 수 있음
int sum_l = 0;
for (int x : l) sum_l += x; // ~캐시 비친화적

---

6. 실전 최적화 패턴

// 패턴 1: 정렬된 vector로 map 대체 (소규모 데이터)
std::vector<std::pair<int, std::string>> sorted_vec;
sorted_vec.reserve(100);
sorted_vec.emplace_back(1, "a");
sorted_vec.emplace_back(2, "b");
std::sort(sorted_vec.begin(), sorted_vec.end()); // 정렬
// 이분탐색으로 O(log n) 탐색, 캐시 효율은 vector 수준
auto it = std::lower_bound(sorted_vec.begin(), sorted_vec.end(),
                           std::make_pair(2, ""));

// 패턴 2: flat_map (Boost, C++23 예정)
// 정렬 vector 기반 map — map의 인터페이스 + vector의 캐시 효율

// 패턴 3: unordered_map 예비 할당 + clear (재사용)
std::unordered_map<int, int> counter;
counter.reserve(10000);
for (const auto& data : large_dataset)
{
    counter.clear(); // 버킷은 유지, 원소만 삭제 → 재할당 없음
    for (int v : data) ++counter[v];
    // ... 처리
}

---

7. 정리

컨테이너	내부 구조	강점	약점
vector	동적 배열	캐시 효율, O(1) 접근	중간 삽입/삭제 O(n)
deque	블록 배열	양쪽 O(1) 삽입	임의 접근 캐시 비효율
list	이중 연결 리스트	중간 삽입 O(1)	캐시 최악, 오버헤드 큼
map	레드블랙트리	정렬 유지, O(log n)	캐시 비효율, 메모리 큼
unordered_map	해시 테이블	O(1) 평균 탐색	정렬 없음, 최악 O(n)
set	레드블랙트리	정렬된 유일 원소	map과 동일
unordered_set	해시 테이블	O(1) 유일 원소 확인	정렬 없음

핵심 원칙: 기본은 vector, 키-값 탐색은 unordered_map, 정렬 필요 시 map을 선택하고, 항상 실제 데이터로 프로파일링 후 최적화합니다.

참고 자료

• cppreference — std::vector
• cppreference — std::map
• cppreference — std::unordered_map