이터레이터

개념

정의

• 이터레이터(iterator)는 포인터처럼 요소를 가리키며 이동하는 객체입니다.
• begin(), end(), *, ++, ==, != 연산으로 순회합니다.
• 핵심 목표는 "컨테이너가 달라도 같은 방식으로 순회/알고리즘 적용"입니다.

왜 중요한가?

• vector, list, deque, set 등 내부 구조가 달라도 이터레이터 인터페이스는 유사합니다.
• 그래서 find, count, for_each 같은 STL 알고리즘을 같은 형태로 사용할 수 있습니다.

begin() / end() 규칙

vector<int> v{10, 20, 30};

auto b = v.begin(); // 첫 요소(10)를 가리킴
auto e = v.end();   // 마지막 다음 위치(past-the-end)

• begin()은 첫 요소를 가리킵니다.
• end()는 마지막 요소 다음 위치를 가리킵니다.
• end()는 역참조(*)하면 안 됩니다.
• 빈 컨테이너에서는 begin() == end()입니다.

이터레이터 위치 개념도

vector v = {10, 20, 30, 40, 50}

  begin()          end()
     │               │
     ▼               ▼
  ┌────┬────┬────┬────┬────┬────┐
  │ 10 │ 20 │ 30 │ 40 │ 50 │ ??? │  ← end()는 past-the-end (역참조 금지)
  └────┴────┴────┴────┴────┴────┘
    ▲    ▲    ▲
    it   it   it   ...  it == end() 되면 종료

---

기본 순회 패턴

일반 순회 (읽기/쓰기 가능)

for (auto it = v.begin(); it != v.end(); ++it) {
    cout << *it << '\n';
    // *it = 100; // 수정도 가능(컨테이너가 non-const일 때)
}

읽기 전용 순회 (const_iterator)

const vector<int> cv{1, 2, 3};
for (auto it = cv.cbegin(); it != cv.cend(); ++it) {
    cout << *it << '\n';
    // *it = 10; // 컴파일 에러: const_iterator는 수정 불가
}

역순 순회 (reverse_iterator)

for (auto it = v.rbegin(); it != v.rend(); ++it) {
    cout << *it << ' '; // 뒤에서 앞으로 출력
}

---

find 패턴

• find는 <algorithm> 헤더가 필요합니다.

auto it = find(v.begin(), v.end(), 3);
if (it != v.end()) {
    cout << "찾은 값: " << *it << '\n';
} else {
    cout << "못 찾음\n";
}

• it != v.end()이면 찾은 것입니다.
• it == v.end()이면 못 찾은 것입니다.
• find의 시간 복잡도는 선형 탐색이므로 보통 O(N)입니다.

필요하면 인덱스로도 변환할 수 있습니다 (vector 기준):

if (it != v.end()) {
    size_t idx = static_cast<size_t>(distance(v.begin(), it));
    cout << "인덱스: " << idx << '\n';
}

• distance는 vector에서는 O(1), list에서는 O(N)이 될 수 있습니다.

---

erase(iterator) 핵심 규칙

• erase(it)는 삭제된 요소의 다음 위치 이터레이터를 반환합니다.
• 따라서 삭제 직후에는 ++it가 아니라 it = v.erase(it);로 갱신해야 안전합니다.

for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0)
        it = v.erase(it); // 반환값 사용
    else
        ++it;
}

• 이 패턴을 지키지 않으면 이터레이터 무효화로 크래시/요소 스킵이 발생할 수 있습니다.
• Part 8에서 vector erase 함정을 더 깊게 다룹니다.

---

자주 하는 실수 + 체크 질문

자주 하는 실수

실수	문제
*v.end() 수행	past-the-end 역참조로 UB
erase(it) 후 ++it	무효화된 이터레이터 사용
push_back 후 기존 it 신뢰	재할당 시 무효화 가능
list에서 it + 1 사용 시도	랜덤 접근 미지원(컴파일 에러)

체크 질문 (스스로 답해보기)

• 왜 end()는 "유효한 비교 대상"이지만 "역참조 대상"은 아닌가?
• const_iterator가 필요한 상황을 실제 코드 예시로 설명할 수 있는가?
• erase 루프에서 if 분기와 else 분기에서 이터레이터를 다르게 갱신하는 이유는?

---