reverse_iterator에서 iterator로 변환을 위한 base 사용 시 주의 사항

[C++ STL] reverse_iterator에서 iterator로 변환을 위한 base 사용 시 주의 사항 」
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. #include "stdafx.h"   
2. #include <vector>   
3. #include <algorithm>   
4.   
5. int _tmain(int argc, _TCHAR* argv[])   
6. {   
7.        
8.     // 1부터 5까지 vector v에 넣습니다.   
9. 
   
10.     std::vector<int> v;   
11.     for(int i = 1; i <= 5; i++)   
12.         v.push_back(i);   
13.   
14.     // find를 이용해서 reverse_iterator를 3의 위치에 둡니다   
15. 
    
16.     // 1,2,3,4,5   
17. 
    
18.     //     *   
19.     std::vector<int>::reverse_iterator ri =    
20.         std::find(v.rbegin(), v.rend(), 3);   
21.   
22.     // reverse_iterator::base를 이용해 현재 위치를 기준으로   
23. 
    
24.     // iterator를 생성합니다.   
25. 
    
26.     // 즉, iterator를 3에다 두려고 합니다.       
27. 
    
28.     std::vector<int>::iterator it( ri.base());       
29.   
30.     // 3을 지우려고 합니다.   
31.     v.erase(it);   
32.   
33.     // 무슨일이 일어날까요?     
34.   
35.     return 0;   
36. }  

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

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

위 그림과 같이 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()를 사용하면 되겠죠?

 

1. #include "stdafx.h"   
2. #include <iostream>   
3. #include <vector>   
4. #include <algorithm>   
5.   
6. int _tmain(int argc, _TCHAR* argv[])   
7. {   
8.        
9.     // 1부터 5까지 vector v에 넣습니다.   
10. 
    
11.     // 결과 v = {1,2,3,4,5}   
12. 
    
13.     std::vector<int> v;   
14.     for(int i = 1; i <= 5; i++)   
15.         v.push_back(i);   
16.   
17.     // find를 이용해서 reverse_iterator를 3의 위치에 둡니다   
18. 
    
19.     // 1,2,3,4,5   
20. 
    
21.     //     *   
22. 
    
23.     std::vector<int>::reverse_iterator ri =    
24.         std::find(v.rbegin(), v.rend(), 3);   
25.   
26.     // reverse_iterator::base를 이용해 현재 위치를 기준으로   
27. 
    
28.     // iterator를 생성합니다.   
29. 
    
30.     // base()가 ri의 한 칸 오른쪽을 it로 만다는 것을 대비해서   
31. 
    
32.     // ri를 미리 한 칸 증가시켜 it가 3을 가르키게 합니다.   
33. 
    
34.     std::vector<int>::iterator it( (++ri).base());   
35.        
36.     // 3을 지우려고 합니다.   
37.     v.erase(it);   
38.   
39.     // 이젠 정상적으로 3이 지워집니다.   
40.   
41.     return 0;   
42. }  

여기서 주의할 것은 ++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인데도 불구하고 버전에 따라 정책이 따르니 다른 컴파일러들은 더 다양하겠죠

출처 : http://alones.kr/blog/841?TSSESSION=758d55316affcf935b2f9a577e5bf262