해설 — std::vector 재할당·증가 정책과 반복자/포인터 무효화

난이도: 중

요약

vector는 연속 메모리에 요소를 담고, 용량(capacity)이 가득 찬 상태에서 push_back 하면 더 큰 버퍼를 새로 할당해 기존 요소를 옮기고 옛 버퍼를 해제한다(재할당). libstdc++/g++는 대개 2배 증가 정책이라 용량이 1→2→4→8→16… 으로 커진다. 재할당이 일어나면 옛 버퍼를 가리키던 모든 반복자·포인터·참조가 무효화된다.

예측 출력 (g++/libstdc++)

realloc at size=1 cap=1
realloc at size=2 cap=2
realloc at size=3 cap=4
realloc at size=5 cap=8
realloc at size=9 cap=16
within reserve: 1 1
cap now=8

• 빈 벡터의 data()는 nullptr일 수 있어 첫 push에서 이동 감지. 이후 용량이 부족해지는 push(size=2,3,5,9)마다 2배로 재할당.
• w는 reserve(4)로 cap=4 확보 → push 1~4는 재할당 없음 → ref,p 유효(1 1). push 5에서 cap 4→8 재할당(cap now=8).

핵심 개념

• amortized O(1): 2배 증가면 N번 push의 총 이동 비용이 N+N/2+N/4+… ≈ 2N → 1회당 상수. 1씩 증가시키면 O(N²)이 된다.
• capacity vs size: size는 요소 수, capacity는 재할당 없이 담을 수 있는 최대 수. reserve(n)은 capacity만 키우고 size는 그대로.

단계별 내부 동작

• push_back 시 size == capacity면: 새 capacity(≈2배) 버퍼 할당 → 기존 요소를 이동(가능하면 move, 아니면 copy) → 옛 버퍼 파괴/해제 → 새 버퍼로 교체. 이 순간 기존 포인터/반복자/참조는 옛 버퍼를 가리켜 dangling.
• 무효화된 ref/p 접근은 use-after-free(UB): 쓰레기 값·크래시. ASan이면 heap-use-after-free.

무효화 규칙 정리

• 재할당(용량 증가)을 유발하는 push_back/insert/emplace_back: 모든 반복자·포인터·참조 무효화.
• 용량 내 push_back: 끝(end) 반복자만 개념상 갱신, 기존 요소 포인터는 유지.
• insert/erase(중간): 삽입/삭제 지점 이후의 반복자·포인터 무효화(erase는 최소 지운 위치 이후).
• reserve/ shrink_to_fit: 재할당하면 전부 무효화.
• move_if_noexcept: 요소 이동 생성자가 noexcept가 아니면 강한 예외 보장을 위해 복사로 옮긴다(재할당 성능에 영향).

흔한 오해·함정

• "요소 포인터를 캐시해두고 push_back 계속" → 재할당으로 dangling. 게임서버에서 엔티티 배열에 흔한 버그. 인덱스나 안정적 핸들(슬롯+세대)로 참조하라.
• vector<bool>은 비트 팩킹 특수화라 &v[i]가 일반 포인터가 아니다(별도 주의).
• reserve는 size를 바꾸지 않는다 — reserve 후 v[i] 접근은 여전히 UB(값이 없음).

면접 포인트

• 2배 증가가 왜 amortized O(1)인가(기하급수 합).
• 어떤 연산이 반복자/포인터를 무효화하는가, 게임 루프에서 요소 포인터 캐싱의 위험.
• reserve로 재할당·무효화를 어떻게 예방하나, move_if_noexcept와 예외 안전.