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

// 주제: std::vector 의 재할당·증가 정책과 반복자/포인터 무효화
//
// 과제:
//   1) push_back 을 반복하면 size/capacity 가 어떻게 변하는가? 증가 정책(대개 2배)과
//      재할당이 "언제" 일어나는지, 왜 amortized O(1) 인지 설명하라.
//   2) 재할당이 일어나면 기존 요소를 가리키던 반복자·포인터·참조가 어떻게 되는가?
//      무효화된 뒤 접근하면 무슨 일이 생기는가?
//   3) reserve 가 무효화를 어떻게 피하는가? push_back/insert/erase 등에서 무효화가
//      일어나는 연산과 안 일어나는 연산을 정리하라.
//   4) 아래 프로그램의 출력을 예측하라(libstdc++/g++ 기준).

#include <cstdio>
#include <vector>

int main() {
    std::vector<int> v;
    int* base = nullptr;
    for (int i = 0; i < 10; ++i) {
        v.push_back(i);
        if (v.data() != base) {                 // 데이터 버퍼가 이동 = 재할당 발생
            std::printf("realloc at size=%zu cap=%zu\n", v.size(), v.capacity());
            base = v.data();
        }
    }

    std::vector<int> w;
    w.reserve(4);
    w.push_back(1);
    int& ref = w[0];
    int* p = &w[0];
    w.push_back(2); w.push_back(3); w.push_back(4);   // cap=4 이내: 무효화 없음
    std::printf("within reserve: %d %d\n", ref, *p);
    w.push_back(5);                                    // cap 초과 -> 재할당
    std::printf("cap now=%zu\n", w.capacity());
    return 0;
}