C++에는 vector, list, set, map 등 다양한 컨테이너가 존재하며, 이러한 컨테이너의 요소들을 순회할 때는 반복자(iterator)를 활용할 수 있습니다. 하지만 C++에서 반복자를 사용할 때는 각별한 주의가 필요합니다. 컨테이너를 순회하는 도중에 컨테이너의 구조나 크기가 변경되면, 반복자가 무효화(invalidation)되어 예기치 못한 동작이나 오류가 발생할 수 있기 때문입니다.
아래 예제 코드를 통해 반복자 무효화 문제가 실제로 어떻게 발생하는지 살펴보겠습니다.
예제 코드
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector <int> vec{11, 55, 110, 155, 220};
for (auto it=vec.begin(); it!=vec.end(); it++)
if ((*it) == 110)
vec.push_back(89); // 벡터를 순회하는 도중 새로운 값을 삽입
for (auto it=vec.begin();it!=vec.end();it++)
cout << (*it) << " ";
}
실행 결과
11 55 110 155 220 89 89
왜 이런 결과가 나오는가?
이 프로그램은 실행할 때마다 다른 결과를 출력할 수 있습니다. 그 이유를 살펴보겠습니다.
위 코드에서 벡터의 크기를 미리 지정하지 않고 초기값만 제공했습니다. 그런데 순회 중에 새로운 값을 추가하고 있습니다. 이때 벡터에 여유 공간이 없다면, 런타임에 새로운 메모리 블록을 할당하고 기존의 모든 요소를 새 위치로 복사합니다. 문제는 기존 반복자가 여전히 이전 메모리 주소를 가리키고 있다는 점입니다. 따라서 반복자가 더 이상 유효하지 않은 메모리를 참조하게 되어 무효화 현상이 발생합니다.
결과적으로 위 예제에서는 값 110을 만날 때마다 새 요소가 삽입되어, 의도와 달리 89가 두 번 출력된 것을 확인할 수 있습니다.
컨테이너별 반복자 무효화 규칙
그렇다면 어떤 상황에서 반복자가 무효화되는지, 컨테이너 유형별로 정리해 보겠습니다.
| 삽입(Insertion) | 삭제(Erasure) | 크기 조정(Resizing) | |
|---|---|---|---|
| vector | 삽입 지점 이전을 가리키는 반복자와 참조자는 영향을 받지 않지만, 그 이후의 모든 반복자는 무효화됩니다. 또한 벡터의 크기가 증가(재할당)되면 모든 반복자가 무효화됩니다. | 삭제 지점 이후의 모든 반복자와 참조자가 무효화됩니다. | 삽입 또는 삭제와 동일하게 동작합니다. |
| deque | 삽입 위치가 deque의 끝이 아닌 경우, 모든 반복자와 참조자가 무효화됩니다. | 삭제 위치가 끝(end)이 아닌 곳이라면, 모든 반복자가 무효화됩니다. | 삽입 또는 삭제와 동일하게 동작합니다. |
| list | 모든 반복자와 참조자가 영향을 받지 않습니다. | 삭제되는 요소 자체를 가리키는 반복자나 참조자만 무효화됩니다. | 삽입 또는 삭제와 동일하게 동작합니다. |
| set, map, multiset, multimap | 모든 반복자와 참조자가 영향을 받지 않습니다. | 삭제되는 요소 자체를 가리키는 반복자나 참조자만 무효화됩니다. | 해당 없음 |
정리 및 팁
반복자 무효화는 디버깅하기 어려운 미정의 동작(undefined behavior)의 주요 원인입니다. 이를 방지하기 위해 다음 사항을 기억하세요.
- 순회 중 삽입/삭제 자제: 컨테이너를 순회하는 동안에는 가능한 한 구조 변경을 피하는 것이 안전합니다.
- erase의 반환값 활용:
erase()는 삭제된 요소의 다음 요소를 가리키는 유효한 반복자를 반환하므로, 이를 활용하면 안전하게 삭제하며 순회할 수 있습니다. - reserve() 활용:
vector의 경우 미리 충분한 용량을 확보하면 재할당으로 인한 전체 반복자 무효화를 줄일 수 있습니다. - 연결 리스트나 트리 기반 컨테이너 고려:
list,map,set등은 노드 기반이므로 다른 요소에 대한 반복자가 유지되어, 빈번한 삽입/삭제가 있는 상황에 적합합니다.