이전 글에서 VC++/gcc 두 플랫폼 STL의 map iterator 작동이 달라서 불만을 토로 했었다. 문제는 iterator가 맨 첫번째 원소를 가리키고 있을 때, -- 연산을 줄 때의 행동이었다. VC++은 싸이클을 그리면서 일단 null 노드, 즉 end()로 얻어지는 노드로 가는 반면, gcc는 그대로 머무르는 행동을 보였다. 그래서 VC++의 경우 -- 을 연속해서 주면 싸이클을 그리면서 움직인다.

직접 두 STL 구현의 소스를 까봤다. STL의 map은 Red-Black Tree라는 이진트리로 구성이 되어있다. 따라서 -- 연산은 Binary Search Tree에서 predecessor를 찾는 코드가 된다. 알고리즘 책에 보면 있는 그런 일반적인 알고리즘이다. 두 구현에서 -- 연산은 당연히 거의 비슷하다 . 먼저 gcc STL의 구현이다. libcstd++ 소스가 없어서 인터넷에서 겨우 찾았다. stl_tree.cc에 구현이 되어 있는 내용.

_Rb_tree_node_base*
_Rb_tree_decrement(_Rb_tree_node_base* __x)
{
    if (__x->_M_color == _S_red && __x->_M_parent->_M_parent == __x)
        __x = __x->_M_right;
    else if (__x->_M_left != 0)
    {
        _Rb_tree_node_base* __y = __x->_M_left;
        while (__y->_M_right != 0)
            __y = __y->_M_right;
        __x = __y;
    }
    else
    {
        _Rb_tree_node_base* __y = __x->_M_parent;
        while (__x == __y->_M_left)
        {
            __x = __y;
            __y = __y->_M_parent;
        }
        __x = __y;
    }
    return __x;
}

그리고 VC++ STL의 구현 내용. 실제로는 각종 디버깅 코드가 있는데 다 삭제하고 핵심만 남겼다.

static _Nodeptr _Max(_Nodeptr _Pnode)
{	// return rightmost node in subtree at _Pnode
    while (!_Isnil(_Right(_Pnode)))
        _Pnode = _Right(_Pnode);
    return (_Pnode);
}
 
void _Dec()
{	// move to node with next smaller value
    if (_Isnil(_Ptr))
    {
        _Ptr = _Right(_Ptr);	// end() ==> rightmost
        if (_Isnil(_Ptr))
            return;	// begin() shouldn't be incremented, don't move
    }
    else if (!_Isnil(_Left(_Ptr)))
        _Ptr = _Max(_Left(_Ptr));	// ==> largest of left subtree
    else
    {	// climb looking for left subtree
        _Nodeptr _Pnode;
        while (!_Isnil(_Pnode = _Parent(_Ptr)) && _Ptr == _Left(_Pnode))
            _Ptr = _Pnode;	// ==> parent while left subtree
        if (_Isnil(_Ptr))
            return;	// begin() shouldn't be incremented, don't move
        else
            _Ptr = _Pnode;	// ==> parent if not head
    }
}

보다시피 거의 동일하다. 딱 하나 다른 경우가 첫 번째 if 문에서 VC++은 _Isnil로 체크하는데, gcc는 좀 다른 방식으로 체크를 하고 있다. 참고로 RB-Tree의 구현은 바운더리 체크를 쉽게 하기 위해 root의 부모로 널로 채워진 sentinel node를 두고 있다.

그러면 이제 아래의 코드를 돌려보자.

map<int, int> m;
m[2]=2;
m[4]=4;
m[6]=6;

map<int, int>::iterator i = m.begin();
--i;
fprintf(stderr, "%d\n", i == m.end() ? 0:i->second);
--i;
fprintf(stderr, "%d\n", i == m.end() ? 0:i->second);
--i;
fprintf(stderr, "%d\n", i == m.end() ? 0:i->second);
--i;
fprintf(stderr, "%d\n", i == m.end() ? 0:i->second);
--i;
fprintf(stderr, "%d\n", i == m.end() ? 0:i->second);

출력문에 지저분한 비교문이 있는 것은 VC++ STL은 end 노드를 출력하고자 접근하면 assertion을 띄어주기 때문에 저렇게 넣었다. gcc는 assertion을 위한 코드는 없다. 디버깅 glibc 버전이면 있을 수도.

VC++의 행동은 싸이클을 그리면서 도는 것이었기 때문에 당연히 아래처럼 결과가 나온다.

0 6 4 2 0

맨 처음 i는 2를 가리킬 것이고 여기서 한 칸 내려가면 맨 끝 원소로 가기 때문에 0을 출력할 것이다. 그리고 다시 거기서 한 번 내려가면 최대 원소인 6이 나온다.

그런데 gcc는 바닥에 있을 때는 늘 머물렀기 때문에 0 0 0 0 0으로 나와야만 한다. 그런데???

결과는 VC++과 똑같이 0 6 4 2 0으로 나온다!!! 즉, gcc map STL에서도 iterator는 바닥을 지나 싸이클을 돌면서 순회한다. 그러면 결국 원소가 하나만 있을 때, iterator 연산에 문제가 있다는 것을 말한다. 실제로 위의 테스트 코드에서 원소 4, 6의 삽입을 막아 버리고 map에 원소 하나만 있도록 한 뒤 같은 코드를 돌리면 결과:

2 2 2 2 2 2

로 나오게 된다.

좀 더 실험을 해보자. 이번에는 원소를 m[6]=6 코드를 막고, 즉, map에다 삽입을 2, 4 순서로 삽입한 뒤 돌리면? 여전히 위와 같이 2만 출력된다. 마지막으로!! 원소 삽입을 큰 것 부터 해보자. 즉, map에다가 4, 2로 두 개만 딱 넣어보자. 그러면?? 싸이클을 그리면서 순회한다 -_-;

아무래도 맨 최상단의 if 문에서 비교하는 nil 노드 때문에 이상하게 되는 것 같은데 더 이상 자세한 디버깅은 귀찮고 짜증나서 포기한다.

(잠정적인) 결론: gcc STL map iterator 구현에 버그가 있다. 만약, 이터레이터 자체가 순회하는 것이 잘못된 행동일 수 있다. 그러나 적어도 행동의 일관성은 보여야할 것 아닌가? 어떤 경우에는 바닥에 머물고 어떤 경우에는 싸이클을 그리면 어떡 하라는거야! 완전 지금 기분은 --;

여러분들의 추가적인 테스팅 대환영 합니다.