C++ iterator 사용 시 주의 사항

다음은 대회 중에 제출한 소스의 일부이다.

if (it-- != t2c.begin()) { // do something }

여기서 t2c는 std::map<ll, ll> 타입이고 it는 std::map<ll, ll>::iterator 타입이다.

위의 조건문에서는 undefined behavior가 발생한다.

 

지금까지는 iterator가 invalidated 상태가 되어도 dereference만 하지 않으면 문제가 없다고 생각하였다.

대회 종료 후 코드 테스트 중 원인을 알 수 없는 segmentation fault가 발생하였다.

도저히 원인을 찾을 수 없어 gdb로 디버깅을 하다가 놀라운 사실을 발견하였다.

일부 컨테이너에서는 iterator의 증감 연산 시 iterator가 invalidated 상태가 되면 segmentation fault가 발생한다.

 

어느 정도 이해는 되는 부분이다.

std::vector의 경우 원소들이 메모리에 연속적으로 배치되어 있으므로 큰 문제가 없다.

반면 std::set이나 std::map 같은 경우 이진 트리 내에서 연산이 이루어진다.

존재하지 않는 노드로 이동하려 하므로 충분히 segmentation fault가 발생할 수 있다.

 

하지만 대회 중에는 정상적으로 작동하였고 문제 없이 AC를 받았다.

그 이유는 컴파일러의 최적화 덕분이다.

컴파일러는 it가 t2c.begin()이 아닌 경우에만 증감 연산자를 실행하도록 최적화하였다.

실제로 최적화 옵션을 끄고 위의 코드를 컴파일하면 segmentation fault가 발생한다.

컴파일러 제작자에게 감사 인사를 드리고 앞으로는 다음과 같이 작성하자.

if (it != t2c.begin()) { --it; // do something }

 

끝