iterator category와 invalidation

카테고리 확인

알고리즘이 요구하는 iterator category가 컨테이너 반복자와 맞는지 본다.

sort는 random access

begin은 포함, end는 제외인 반열린 구간으로 전달한다.

off-by-one 방지

insert, erase, push_back 후 기존 iterator가 살아 있는지 컨테이너별로 확인한다.

무효화 핵심

list에는 list::sort처럼 컨테이너 전용 알고리즘이 필요한 경우가 있다.

std::sort 불가

vector

연속 메모리와 random access 재할당이 일어나면 iterator, pointer, reference가 모두 무효화될 수 있다.

capacity 확인

list

노드 기반 양방향 중간 삽입과 삭제는 강하지만 임의 접근이 없어 std::sort에 맞지 않는다.

list::sort 사용

map

정렬된 키 순회 삽입은 대체로 기존 iterator를 유지하지만 삭제한 원소의 iterator는 무효다.

키 변경 불가

unordered

해시 버킷 기반 rehash가 일어나면 iterator가 무효화될 수 있고 순서는 보장되지 않는다.

reserve 고려

end iterator erase 후 반환되는 다음 iterator를 사용해 루프를 이어가야 한다.

알고리즘 요구 binary_search는 정렬된 범위가 전제이고, sort는 random access가 필요하다.

참조 안정성 iterator만이 아니라 reference와 pointer가 살아 있는지도 컨테이너별로 확인한다.

for (auto it = v.begin(); it != v.end(); )
  if (pred(*it)) it = v.erase(it);
  else ++it;