C++ 반복자

반복자: 컨테이너와 알고리즘 사이의 능력 계약

반복자는 단순 포인터처럼 보이지만 가능한 이동 방향과 연산이 정해진 계약이다. 알고리즘이 요구하는 iterator category와 컨테이너의 무효화 규칙이 맞아야 안전하다.

01

범위 구성

begin은 포함, end는 제외인 반열린 구간을 유지한다.

[first,last)
02

카테고리 확인

std::sort처럼 random access가 필요한 알고리즘인지 확인한다.

list에는 부적합
03

변경 연산

컨테이너 수정 뒤 기존 iterator를 계속 써도 되는지 문서 규칙을 따른다.

무효화 검사
04

const 구분

iterator와 const_iterator, iterator to const의 차이를 구분한다.

수정 가능성
Input
한 번 읽는 스트림 여러 번 순회한다는 가정이 깨질 수 있다.
single-pass
Forward
동일 범위 재순회 가능 forward_list처럼 전진만 되지만 multi-pass가 가능하다.
++만
Bidirectional
-- 이동 가능 list, map 계열은 앞뒤 이동은 되지만 +n 임의 접근은 안 된다.
std::prev
Random
인덱스식 이동 vector, deque는 +n과 거리 계산이 가능해 sort 요구를 만족한다.
차이 계산

erase 루프 · end 사용 · algorithm 요구 점검

erase 루프 삭제 후 무효화된 iterator를 증가시키지 말고 반환값을 사용한다.
end 사용 end는 원소가 아니므로 역참조하지 않는다.
algorithm 요구 알고리즘 문서의 iterator category requirement를 컨테이너와 맞춘다.

삭제 루프 기본형

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