반복자 무효화 : 어떠한 연산을 조심해야 할까요?

 STL을 공부하시다 보면, 반복자 무효화라는 용어는 한 번 쯤 들어보셨으리라 생각합니다. 반복자는 순회, 탐색 등을 위해서 쓰는 녀석인데요. 이것이 어떠한 이유로 무효화가 될 수 있습니다. 보통, iterator가 가리키는 것이 삭제 되었을 때 무효화가 되는데요. vector와 같이, 동적 배열을 사용할 때는 그 이외에도 조심해야 할 부분들이 몇 가지 더 있어요.

 

 

---

 예제 프로그램 1을 봅시다.

 

 

 먼저, 이 프로그램을 생각해 봅시다. vector v에 원소를 200개 추가했습니다. 그리고, 이 때, 벡터의 시작 원소를 iter가 가리키게 했습니다. 그리고 난 다음에, v에다가 0부터 1999까지 또 추가를 합니다. 프로그램에는, 벡터에 remove 연산을 가하지 않았습니다.

 

 

 그런데 결과가 의외입니다. 0 0 0 0 4 5 6? 의도대로라면 0 1 2 3 4 ... 가 출력이 되어야 하는데 말입니다. 이는 어떠한 부분 때문에, 정의되지 않은 행동을 수행했다는 의미입니다. 당연하게도, iter = v.begin(); 문 뒤에 2000개의 수를 v에 추가하는 연산을 지우면, 제대로 된 값이 출력됩니다.

 

 

 그러한가요? 벡터는 어떠한 원소가 삭제될 때에도 무효화가 되지만, push_back을 호출할 때에도, 무효화가 될 수 있다는 것을 보여줍니다. 왜 그럴까요?

 

 

[관련글]

동적 배열에 대해 알아봅시다.

 

 

 이는 push_back을 호출했을 때 다음과 같은 상황이 벌어질 수 있기 때문입니다.

 

 

 예를 들어 capacity가 꽉 찬 상태에서, 5를 추가하라는 명령이 들어왔다고 해 봅시다. 그러면, 이 때, expand 연산이 수행됩니다. 그러면 기존 용량의 x배 정도로 확장할 거에요.

 

 

 그 다음에 새롭게 할당된 공간에 5를 추가할 거에요.

 

 

 iter = v.begin(); 이라는 문장 다음에 vector에 요소를 많이 추가하는 명령이 있다면, 당연하게도, 추가가 많이 된다면 expand도 많이 일어날 겁니다. 확장 연산에서, 무효화가 되는 부분을 주황색으로 표시했는데요. iter가 주황색 부분을 가리키고 있어요.

 

 즉, 8번째 줄의 iterator가 무효화가 되었다고 말을 할 수 있어요. 그렇기 때문에, 정의되지 않은 동작, 예기치 못한 실행 결과가 나옵니다. 즉, 벡터는 insert 연산이 수행되어서 capacity가 바뀌었을 때도 참조자가 무효화 될 수 있기 때문에 조심해야 합니다.

 

 

---

 예제 프로그램 2를 봅시다. 이번에는 set 입니다. 이들은 트리 형태로 구성이 되는 구조입니다. 그렇다면, 노드 안에 prev라던지 next가 있거나, 혹은 parent, left, right와 같은 포인터가 있으리라 예상할 수 있습니다.

 

 

 그러면 이런 경우는 어떨까요? 일단 0부터 198까지 set에 추가했습니다. 그리고, iter가 v.end()에 다다를 때 까지 순회를 하는데요. iter가 가리키는 내용을 출력하고, iter가 가리키는 객체를 제거해 버립니다. 그러면 어떻게 될까요?

 

 

 경우에 따라서는 seg fault가 뜰 겁니다. 이것을 그림으로 표현해 보겠습니다.

 

 

 현재 이터레이터는 0번 노드를 가리키고 있습니다. 그런데 이 친구가 가리키고 있는 것을 remove를 해 봅시다.

 

 그러면, 주황색 부분이 제거되었기 때문에, iter가 무효화 되었습니다. 여기서 어떻게 next 원소로 가나요? parent를 어떻게 타야 하나요? 아니면 오른쪽 child를 또 어떻게 타야 하나요? 제거가 되었기 때문에, 어떻게 할 방법이 없습니다. 그러면, 이것을 방지하기 위해서 어떻게 해야 할까요?

 

 iter가 가리키는 것을 제거하기 전에, 다른 이터레이터에 iter가 가리키는 것을 복사하고, iter 값을 증가시키면 됩니다.

 

 

 iter2 = iter를 대입하면, 두 녀석이 가리키는 노드가 같습니다. 이 상태에서 초록색 노드를 바로 삭제하지 않습니다. 대신에 iter++을 해서 이터가 다음 원소를 가리키게 합니다.

 

 

 그러면 우리가 삭제해야 할 대상은 이터2가 가리키고 있습니다. 따라서, v.remove(iter2); 를 호출하면 됩니다.

 

 

 그러면 iter2만 무효화가 되고, iter는 다음 원소를 안전하게 가리키게 됩니다.

 

 

 즉, 이런 식으로 바꾸면, 안전하게 프로그램을 수행할 수 있습니다.