[C++ STL] reverse_iterator에서 iterator로 변환을 위한 base 사용 시 주의 사항

Feb 25

alonesProgramming/C/C plus plus , , , , , , , , , , 6 Comments

STL 컨테이너를 역으로 순회하기 위해 reverse_iterator를 사용하고 있던 도중 다음과 같은 상황을 만나 iterator로 변경을 해야 하는 경우가 있다.

  1. 순 방향으로 순회하기 위해
  2. reverse_iterator를 인자로 받지 않는 컨테이너 함수나 알고리즘 함수를 만났을 경우
    일반적으로 컨테이너 요소를 삽입 (insert)하거나 삭제 (erase)하는 함수들은 reverse_iterator를 받지 않는다.

이 경우 reverse_iterator::base를 이용해서 현재 순회하고 있는 시점을 기준으로 iterator로 바꿀 수 있을 것입니다.

하지만 다음 코드는 대형 코드 내에서 많은 디버깅을 요할 수도 있고, 때론 재앙을 일으킬 수 있습니다.

(-_-;; 죽지 않고 단지 동작을 살짝 다르게 하면서 치명상을 입히니)

■ reverse_iterator::base()를 실수로 사용한 예제

STL 표준에 좀 더 충실한 (디버깅도 용이한) VS2005을 이용해서 예제 코드를 만들어봤습니다.

Vector에 1부터 5까지 넣고 reverse_iterator를 3에 가져다 둔 후에 base()를 이용해 그 위치를 가리키는 iterator를 만들고 3을 erase()로 지우려는 코드입니다.

(최소한 제가) 의도한 결과는 1,2,4,5 입니다.

하지만 결과는 1,2,3,5 입니다.

■ 원인

앞 예제의 원인은 reverse_iterator::base()의 구현 정책 때문에 발생하는 일입니다.

reverse_iterator

사용자 삽입 이미지위 그림과 같이 find()로 3에 해당하는 위치로 reverse_iterator로 옮긴 것은 예상하는 것과 같습니다.

하지만 reverse_iterator::base()로 it를 만든 것은 위 그림과 같이 4를 가리키는 결과가 됩니다.

왜일까요? 왜 base() 후 it가 같은 위치인 3을 가르키지 않을까요?

답 또한 위 그림에 있습니다.

일반적으로 iterator의 begin()과 end()의 정책은 begin()은 컨테이너의 첫 요소를 가리키게 하고 end()는 마지막 요소 다음의 아무 것도 없는 곳을 가리킵니다.

그래서 while( it != v.end()) 라는 것을 쓸 수 있겠죠?

같은 원리로 reverse_iterator의 rbegin()은 컨테이너의 마지막 요소를, rend()는 첫 요소의 앞을 가리키게 되어 있습니다.

base()는 reverse_iterator를 기준으로 iterator를 위치를 잡아주어야 하지만 위 그림의 어긋난 한 칸 (end()가 rebegin()보다 한 칸 오른쪽으로 가있습니다) 도 맞추어야 iterator가 문제없이 자기 고집대로 동작할 수 있겠죠?

그렇지 않다면 rend()가 begin()이 되어 begin()은 null을 가리키고 rbgein()은 end()가 되어 it != v.end() 를 이용한 loop들은 재앙을 맞이하겠죠?

아무튼 그래서 base()는 reverse_iterator가 가리키는 요소로부터 오른쪽 한 칸을 iterator의 위치로 지정해줍니다.

즉, 우리의 예제 코드에서 base()를 한 순간 it는 3이 아닌 한 칸 오른쪽에 있는 4를 가리키게 되었습니다.

MSDN의 VS2005 이상의 reverse_iterator::base()에서도 이 내용에 대해서 설명을 하고 있으며 아래와 같이 표현하고 있습니다.

&*(reverse_iterator ( i ) ) == &*( i – 1 ).

즉, iterator에 대한 reverse_iterator는 iterator의 왼쪽으로 한칸 이동 시킨 같과 같다는 뜻입니다. (저희 설명을 왼쪽으로 했구요)

■ 해결책

간단하게 ri를 왼쪽으로 한칸 더 밀어 넣고 base()를 사용하면 되겠죠?



여기서 주의할 것은 –ri.base()라고 작성하면 문제가 될 수있습니다.

(※ 제가 테스트 도중 초기 VC6.0 코드에서 컴파일이 되지 않는 것에만 집중해서 –ri.base()를 ++ri.base()로 잘못 쓴 것을 최익필님이 아래 댓글과 같이 지적 해주셔서 수정했습니다. 감사합니다. )

※ 이하 부분은 powell 님의 아래 지적과 그 것을 통해 재 확인 내용으로 수정했습니다. (2008.02.26)

즉, –ri.base() 코드는 컴파일러에 따라 컴파일될 수도 있고 되지 않을 수도 있다.

예로 VC6과 VC8 (VS2005)을 살펴보면,


먼저 VC8.0의 경우는 reverse_iterator::base()는 아래와 같고 current는 _RanIt로 결국 vector의 wrapper iterator가 됩니다.

_RanIt __CLR_OR_THIS_CALL base() const
{ // return wrapped iterator
return (current);
}

그리고 vector의 해당 iterator인 _Vector_iterator인 operator–()을 가지고 있어 –ri.base()는 컴파일 가능합니다.


VC6.0은 디버깅으로 따라가기 힘들어서 밝히진 못했지만, ri.base()로 반환된 형이 operator–()가 없기 때문에 컴파일 실패를 한 것 같습니다.

동일한 MS의 C++ library인데도 불구하고 버전에 따라 정책이 따르니 다른 컴파일러들은 더 다양하겠죠.

※ 이와 관련된 것은 아래 VC++ Team blog에 제가 문의한 것과 MSDN 포럼에 올려서 VC++ 팀의 Stephan T. Lavavej로부터 받은 답변을 보시면 도움이 되실 겁니다.

Ref: [1] MSDN reverse_iterator::base

       [2] Effective STL, Item 28