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

난이도: 중상

요약

무효화는 세 대상(반복자 / 참조·포인터 / end() 반복자)을 구분해야 한다. vector 는 재할당(용량 초과) 시 저장소가 이동해 전부 무효화, 용량 이내 push_back 은 유지. node 기반(list·map·set)은 원소가 제자리 node 라 삽입이 다른 원소를 무효화하지 않는다. unordered_map 은 rehash 시 반복자는 무효화되지만 원소의 참조·포인터는 유지(원소는 node 에 있고 버킷 배열만 재구성).

예측 출력

vec: 1 0
list: 1
map: 1
umap: 1

핵심 개념 · 단계별

vector — `1 0`

reserve(2) 로 용량 2 확보. push_back(1),(2) 는 용량 이내라 재할당 없음 → data() 동일 → vd1==vd2 = 1.
push_back(3) 은 용량(2) 초과 → 재할당: 새 버퍼 할당 → 기존 원소 이동(move_if_noexcept, cpp_internals/problem9) → 옛 버퍼 해제. data() 가 새 주소 → vd2==vd3 = 0.
규칙: 재할당이 일어나면 vector 의 모든 반복자·참조·포인터가 무효화. 재할당이 없으면 삽입점 이후 원소만 이동(insert), push_back 뒤끝은 기존 유지. reserve 로 재할당을 예측·억제할 수 있다.
함정: v.push_back(v[0]) 는 재할당 시 자기 원소 참조가 인자 평가 중 무효화될 수 있어 위험(표준 구현은 대개 방어하지만 일반화 금지).

list / map — `1`

std::list 는 이중 연결 리스트: 각 원소가 독립 node. 다른 원소를 넣거나 빼도 그 node 는 그대로 → &l.front() 불변 → 1.
std::map(적록 트리)도 원소가 node. 삽입 시 트리 재균형(회전)이 일어나도 node 자체는 이동하지 않고 포인터만 바뀐다 → &m.at(7) 불변 → 1.
규칙: node 기반 연관/리스트 컨테이너는 삽입이 어떤 반복자·참조도 무효화하지 않고, 삭제는 지워지는 원소만 무효화.

unordered_map — `1`

원소는 node 에 저장되고, 컨테이너는 버킷(포인터 배열) 로 node 를 가리킨다. 부하율 초과로 rehash 하면 버킷 배열만 재구성되고 node 는 그대로 있다.
따라서 rehash 는 모든 반복자를 무효화하지만 원소의 참조·포인터는 유지 → &um.at(7) 불변 → 1.
reserve/max_load_factor 로 rehash 시점을 통제. (반대로 vector 는 원소 자체가 배열 안이라 재할당이 참조까지 무효화 — 여기가 핵심 대조.)

흔한 오해·함정

"반복자 무효화 == 참조 무효화"가 아니다. unordered_map rehash·deque 양끝 삽입은 반복자만 무효화(참조/포인터 유지). 이 구분을 놓치면 "왜 iterator 로는 깨지고 포인터로는 되지?" 를 오해한다.
deque: 양끝 push_back/push_front 은 모든 반복자 무효화, 참조/포인터는 유지(기존 원소). 중간 삽입은 전부 무효화. (vector 와 달리 연속 저장이 아님.)
end() 반복자는 별도로 다뤄야 함 — 많은 연산이 end() 를 무효화한다.
무효화된 반복자·포인터를 역참조·비교하는 것 자체가 UB — 위 코드가 주소를 uintptr_t 정수로 미리 붙잡아 비교하는 이유(무효 포인터 값 사용 회피).
순회 중 삽입/삭제(for (auto it=..; it!=end; ++it) c.erase(it))는 대표적 무효화 버그 — erase 반환값으로 재대입해야(concurrency_memory/problem30 순회 중 변경과 연결).

면접 포인트

컨테이너별 무효화 규칙 표를 "반복자 / 참조·포인터"로 나눠 말할 수 있는가(vector 재할당=전부, node 기반=지워진 것만, unordered rehash=반복자만).
reserve/max_load_factor 로 무효화(재할당·rehash) 시점을 통제하는 법.
왜 무효 포인터를 정수로 비교했는지(무효 포인터 값 사용도 UB) — 실측 코드 작성 시 주의점.

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