19. 컨테이너 반복자/참조/포인터 무효화 규칙과 재할당·rehash

// 주제: 표준 컨테이너의 반복자/참조/포인터 무효화(invalidation) 규칙과 재할당·rehash.
//
// 같은 "원소를 가리키는 포인터"가 컨테이너에 원소를 더 넣은 뒤에도 유효한지는 컨테이너마다
// 다르다. vector·list·map·unordered_map 은 재할당·rehash·node 저장 방식이 서로 달라, 삽입 후
// 반복자/참조/포인터의 유효성이 각각 어떻게 되는지도 다르다.
//
// 이 프로그램은 각 컨테이너에서 원소의 주소를 정수로 붙잡아 두고, 원소를 더 넣은 뒤
// 같은 논리적 원소의 주소가 그대로인지(1) 바뀌었는지(0) 를 출력한다.
//
// 과제:
//   1) 이 프로그램의 정확한 표준출력을 예측하라(네 줄).
//   2) vector 의 두 값이 왜 "1 0" 인지(용량 내 추가 vs 용량 초과 재할당) 설명하라.
//   3) list/map 의 값이 왜 1 인지(node 안정성) 설명하라.
//   4) unordered_map 이 왜 1 인지 — rehash 가 "반복자"와 "원소 참조/포인터" 중 무엇을
//      무효화하는지 구분해 설명하라.

#include <cstdio>
#include <cstdint>
#include <vector>
#include <list>
#include <map>
#include <unordered_map>

int main() {
    // (2) vector: 용량 내 추가 vs 용량 초과 재할당
    std::vector<int> v; v.reserve(2);
    uintptr_t vd1 = (uintptr_t)v.data();
    v.push_back(1); v.push_back(2);                 // 용량(2) 이내
    uintptr_t vd2 = (uintptr_t)v.data();
    v.push_back(3);                                 // 용량 초과 → 재할당
    uintptr_t vd3 = (uintptr_t)v.data();
    std::printf("vec: %d %d\n", (int)(vd1==vd2), (int)(vd2==vd3));

    // (3) list: node 안정성
    std::list<int> l; l.push_back(100);
    uintptr_t la1 = (uintptr_t)&l.front();
    for (int i = 0; i < 50; i++) l.push_back(i);
    uintptr_t la2 = (uintptr_t)&l.front();
    std::printf("list: %d\n", (int)(la1==la2));

    // (3) map: node 안정성
    std::map<int,int> m; m[7] = 1;
    uintptr_t ma1 = (uintptr_t)&m.at(7);
    for (int i = 0; i < 50; i++) m[i] = i;
    uintptr_t ma2 = (uintptr_t)&m.at(7);
    std::printf("map: %d\n", (int)(ma1==ma2));

    // (4) unordered_map: rehash 후 원소 참조/포인터 유지
    std::unordered_map<int,int> um; um.reserve(2); um[7] = 1;
    uintptr_t ua1 = (uintptr_t)&um.at(7);
    for (int i = 0; i < 50; i++) um[i] = i;         // rehash 유발
    uintptr_t ua2 = (uintptr_t)&um.at(7);
    std::printf("umap: %d\n", (int)(ua1==ua2));
    return 0;
}