C++ 이터레이터 정리

이터레이터란

컨테이너의 원소를 가리키는 객체다. 포인터를 일반화한 개념으로, *, ++, --, == 등 포인터와 같은 연산을 지원한다. 컨테이너 내부 구현과 무관하게 동일한 인터페이스로 원소에 접근할 수 있다.

이터레이터 카테고리

아래로 갈수록 상위 카테고리의 기능을 모두 포함한다.

카테고리	가능한 연산	대표 컨테이너
Input	`*it`(읽기), `++`, `==`/`!=`	`istream_iterator`
Output	`*it`(쓰기), `++`	`ostream_iterator`, `back_inserter`
Forward	Input + 여러 번 순회 가능	`forward_list`, `unordered_set`
Bidirectional	Forward + `--`	`list`, `set`, `map`, `multiset`
Random Access	Bidirectional + `+n`, `-n`, `[]`, `<`/`>`	`vector`, `deque`, `array`

카테고리에 따라 사용 가능한 알고리즘이 달라진다. sort는 Random Access가 필요하고, reverse는 Bidirectional이면 된다.

begin / end

vector<int> v = {1, 2, 3};

v.begin();   // 첫 번째 원소를 가리킨다
v.end();     // 마지막 원소 다음 (past-the-end)을 가리킨다
v.rbegin();  // 마지막 원소를 가리키는 reverse_iterator
v.rend();    // 첫 번째 원소 앞을 가리키는 reverse_iterator

v.cbegin();  // const_iterator 버전 (수정 불가)
v.crbegin(); // const_reverse_iterator 버전

end()는 원소를 가리키지 않는다. 역참조(*)하면 미정의 동작이다
빈 컨테이너에서 begin() == end()이다
rbegin()과 prev(end())는 같은 원소를 가리키지만 타입이 다르다 (reverse_iterator vs iterator)

이동 함수

#include <iterator>

auto it = v.begin();

next(it);      // it + 1 위치의 복사본 반환. 원본 불변
next(it, 3);   // it + 3

prev(it);      // it - 1 위치의 복사본 반환. 원본 불변
prev(it, 2);   // it - 2

advance(it, 3);  // it를 3칸 앞으로 이동. 원본을 수정한다
advance(it, -1); // Bidirectional 이상이면 뒤로도 가능

distance(v.begin(), v.end());  // 두 iterator 사이의 거리. 여기선 3

함수	원본 수정	반환값	Random Access 복잡도	그 외 복잡도
`next`	X	iterator 복사본	O(1)	O(n)
`prev`	X	iterator 복사본	O(1)	O(n)
`advance`	O	void	O(1)	O(n)
`distance`	X	정수	O(1)	O(n)

Random Access iterator는 it + n으로 직접 이동할 수 있어서 O(1)이다
Bidirectional iterator는 한 칸씩 이동해야 해서 O(n)이다
next/prev는 표현식 안에서 안전하다: erase(prev(s.end())) 처럼 쓸 수 있다
advance는 void를 반환하므로 체이닝이 안 된다

컨테이너별 이터레이터 특성

vector / deque — Random Access

vector<int> v = {10, 20, 30, 40};
auto it = v.begin() + 2;   // O(1), 30을 가리킨다
it[1];                      // 40. 인덱스 접근 가능
sort(v.begin(), v.end());   // Random Access 필요 → 가능

삽입/삭제 시 이터레이터가 무효화된다
vector는 재할당 시 모든 이터레이터가 무효화된다

list — Bidirectional

list<int> l = {10, 20, 30};
auto it = l.begin();
// it + 2;  // 컴파일 에러. Random Access 아님
advance(it, 2);  // O(n)으로 이동
// sort(l.begin(), l.end());  // 컴파일 에러
l.sort();  // 멤버 함수 sort 사용

삽입/삭제해도 다른 이터레이터가 유효하다
splice 등 리스트 특화 연산에서 이터레이터가 유용하다

set / multiset / map — Bidirectional

set<int> s = {3, 1, 4, 1, 5};  // {1, 3, 4, 5}
*s.begin();    // 1 (최솟값)
*s.rbegin();   // 5 (최댓값)

s.erase(s.begin());           // 최솟값 하나 삭제
s.erase(prev(s.end()));       // 최댓값 하나 삭제

auto it = s.find(4);          // O(log N). 없으면 s.end()
s.lower_bound(3);             // 3 이상인 첫 원소
s.upper_bound(3);             // 3 초과인 첫 원소

erase(iterator)는 해당 원소 하나만 삭제한다
erase(값)은 해당 값 전부를 삭제한다 (multiset에서 주의)
삭제된 이터레이터만 무효화되고, 나머지는 유효하다

unordered_set / unordered_map — Forward

unordered_set<int> us = {3, 1, 4};
// prev(us.end());  // 컴파일 에러. Forward iterator는 --를 지원하지 않는다
for (auto it = us.begin(); it != us.end(); ++it) { /* 순회만 가능 */ }

순회 순서가 보장되지 않는다
rehash 시 모든 이터레이터가 무효화된다

이터레이터 무효화 요약

컨테이너	삽입 시	삭제 시
`vector`	재할당이면 전부, 아니면 삽입 지점 이후	삭제 지점 이후 전부
`deque`	전부 (양 끝 삽입은 이터레이터만 무효, 참조는 유효)	양 끝이면 해당 것만, 중간이면 전부
`list`	없음	삭제된 것만
`set`/`map`	없음	삭제된 것만
`unordered_*`	rehash 시 전부	삭제된 것만

실전 패턴

삭제하면서 순회

// 잘못된 방법: 삭제 후 it가 무효화됨
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it == target) v.erase(it);  // 미정의 동작
}

// 올바른 방법: erase가 다음 유효한 iterator를 반환
for (auto it = v.begin(); it != v.end(); ) {
    if (*it == target)
        it = v.erase(it);
    else
        ++it;
}

범위 기반 for와의 관계

// 이 둘은 동일하다
for (auto& x : v) { /* ... */ }
for (auto it = v.begin(); it != v.end(); ++it) { auto& x = *it; /* ... */ }

범위 기반 for 안에서 컨테이너를 수정하면 이터레이터가 무효화될 수 있다. 삭제가 필요하면 이터레이터 루프를 써야 한다.