C++ 반복자 무효화(Iterator Invalidation) 완벽 가이드

C++ 반복자 무효화란?

이 글에서는 C++에서 자주 발생하는 반복자 무효화(iterator invalidation) 문제를 예제 코드와 함께 살펴보고, 이를 예방하는 안전한 코딩 방법까지 함께 정리합니다.

컨테이너 객체의 요소를 순회하는 도중 경계 검사 없이 컨테이너를 수정하면 반복자가 무효화될 수 있습니다. 이는 주로 컨테이너의 크기나 내부 구조가 변경될 때 발생하며, 무효화된 반복자를 사용하면 정의되지 않은 동작(undefined behavior)이 발생합니다.

문제 상황 예제

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 벡터 선언
    vector<int> v{1, 5, 10, 15, 20};

    // 순회 중 벡터를 수정하여
    // 반복자 무효화(invalidation) 발생
    for (auto it = v.begin(); it != v.end(); it++)
        if ((*it) == 5)
            v.push_back(-1);

    for (auto it = v.begin(); it != v.end(); it++)
        cout << (*it) << " ";

    return 0;
}

실행 결과

1 5 10 15 20 -1 -1

위 코드에서는 값이 5인 원소를 만나는 순간 push_back으로 새 요소를 추가합니다. 이때 벡터의 용량(capacity)이 부족하면 더 큰 새로운 메모리 공간으로 전체 요소가 복사(재할당)되는데, 기존 반복자는 여전히 이전 메모리 위치를 가리키고 있어 오류가 발생합니다. 즉, 반복자가 이미 해제된 메모리를 가리키는 댕글링(dangling) 상태가 되는 것입니다.

참고로 위 출력은 정의되지 않은 동작의 한 예이므로, 컴파일러나 실행 환경에 따라 결과가 달라지거나 프로그램이 비정상 종료될 수도 있습니다.

반복자가 무효화되는 이유

std::vector는 요소들을 연속된 메모리 공간에 저장합니다. push_back 등으로 현재 용량을 초과하는 요소가 추가되면 벡터는 내부적으로 다음 과정을 거칩니다.

기존 용량보다 큰 새 메모리 블록을 할당
기존 요소들을 새 메모리로 이동 또는 복사
기존 메모리 블록 해제

이 과정에서 기존 메모리를 가리키던 모든 반복자, 포인터, 참조는 무효화됩니다.

주요 컨테이너별 무효화 규칙

vector, string: 재할당이 일어나면 모든 반복자가 무효화됩니다. 중간 위치의 삽입·삭제 시에는 해당 지점 이후의 반복자가 무효화됩니다.
deque: 양 끝에서의 삽입·삭제는 반복자를 무효화하지만 참조는 유효하며, 중간 삽입·삭제 시에는 모든 반복자와 참조가 무효화됩니다.
map, set: 삽입은 기존 반복자를 무효화하지 않으며, erase는 삭제된 요소를 가리키던 반복자만 무효화합니다.

안전하게 작성하는 방법

1. reserve()로 재할당 방지

순회 전에 미리 충분한 용량을 확보해 두면 push_back이 발생해도 재할당이 일어나지 않아 반복자가 유효하게 유지됩니다.

2. 인덱스 기반 순회 사용

반복자 대신 인덱스로 접근하면 매번 컨테이너의 현재 상태를 기준으로 동작하므로 훨씬 안전합니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v{1, 5, 10, 15, 20};

    // 방법 1: 미리 용량을 확보해 재할당 방지
    v.reserve(v.size() + 1);

    // 방법 2: 인덱스 기반 순회
    for (size_t i = 0; i < v.size(); i++) {
        if (v[i] == 5)
            v.push_back(-1);
    }

    for (int x : v)
        cout << x << " ";

    return 0;
}

실행 결과

1 5 10 15 20 -1

3. erase()의 반환값 활용

순회하면서 요소를 삭제해야 한다면, erase가 반환하는 다음 유효 반복자를 반드시 받아 사용해야 합니다.

// erase는 삭제된 요소의 다음 반복자를 반환하므로 이를 활용
for (auto it = v.begin(); it != v.end();) {
    if (*it == 5)
        it = v.erase(it);  // 유효한 다음 반복자를 반환받음
    else
        ++it;
}

마무리

반복자 무효화는 컴파일 시점이 아닌 실행 시점에 문제를 일으키기 때문에 디버깅이 까다롭습니다. 컨테이너를 순회하는 코드와 수정하는 코드가 함께 있다면 반드시 무효화 규칙을 확인하고, reserve, 인덱스 접근, erase 반환값 활용 같은 안전한 패턴을 습관화하는 것이 좋습니다.