#stl 상등 관계(equality)와 동등 관계(equivalence)의 차이 파악

두 값이 같은가를 판단하는 두 가지 방법이 존재한다. 첫 번째 방법은 두 값이 같은지를 바로 판단하는 것이고 두 번째 방법은 작지도 않고 크지도 않다는 것을 확인해서 두 값이 같은지를 판단한다. 이 첫 번째 방법은 operator== 로 판단하는데, A == B 이면 두 값이 같다고 판단한다. 반면 두 번째 방법은 operator< 로 판단하는데, !(A < B) && !(A > B) 이면 두 값이 같다고 판단한다.

상등 관계와 동등 관계는 수학적인 개념인데, 동등 관계(equivalence relation)에서 반대칭 관계(antisymmetric releation)를 만족하면 상등(equality)하다고 한다. 동등 관계에 대칭 관계(Symmetric relation)가 포함되므로 결국 상등 하려면 대칭 관계와 반대칭 관계 둘 다 만족해야 하는데, 이 관계를 만족하는 연산은 같다(=) 연산밖에 없다.

상등 관계와 동등 관계가 이렇다. 이게 왜 STL과 관련지어서 나오냐면 같은 값을 가졌는지 판단할 때, find() 류는 operator== 로 하고 std::insert() 류는 operator< 로 하기 때문이다. 하나만 쓰지! 참 원망스럽다. 하지만 이해가 가기도 한다. 연관 컨테이너(set, multiset, map, multimap)는 정렬된 순서로 내부 데이터를 관리하는데, 이때 정렬 기준으로 operator< 를 사용한다. 이 연산으로 동등 관계를 파악할 수 있는데, 구태여 상등 관계를 밝히는 operator== 연산을 추가로 정의할 필요가 없고 만약 쓴다면 더욱 혼란스러울 것 같다.

머리가 복잡해진다. 두 가지 방법이 존재하는데, STL에서는 이 두 가지 방법을 다 사용하고 있고 사용하는 이유가 “한번 죽어봐라!”가 아닌 타당한 이유처럼 보인다. 어떻게 안전하게 사용할 수 있을까? STL 범위 안에서 섞어 쓰는 건 어쩔 수 없다. 하지만 하나의 컨테이너 안에서 상등과 동등 중 하나의 관계만을 사용할 수 있다. 바로 같은 동작을 하는 함수라도 컨테이너 멤버 함수로 있는 게 있는데, 이 함수를 사용해야지 안전하다. 이 함수는 두 값이 같은지 판단할 때, 컨테이너에 맞게 상등 혹은 동등 관계로 판단한다. 즉, 연관 컨테이너이면 동등 관계로 판단한다. 또한, 컨테이너에 최적화된 함수이므로 성능상의 이점도 있다. 그냥 이런 건 닥사용이다.

덧붙이자면 Effective STL 항목 21에 보면 연관 컨테이너용 비교 함수는 같은 값에 대해 false를 반환해야 한다고 설명되어 있는데, operator< 대신에 <= 연산을 사용해서 잘못된 결과가 나오는 것을 보여준다. 일단 <= 연산은 동등 관계도 아닐뿐더러 !(A <= B) && !(A >= B) 연산으로는 A와 B가 같은지 판단할 수도 없다.

VS2005 딩컴웨어 STL 구현을 살펴보자면,

template<class _InIt, class _Ty>
inline
    _InIt _Find(_InIt _First, _InIt _Last, const _Ty& _Val)
    {    // find first matching _Val
    _DEBUG_RANGE(_First, _Last);
    for (; _First != _Last; ++_First)
        if (*_First == _Val)
            break;
    return (_First);
    }

std::find() 는 이렇게 operator== 로 상등 관계로 판단하고

_Nodeptr _Lbound(const key_type& _Keyval) const
    {    // find leftmost node not less than _Keyval
    _Nodeptr _Pnode = _Root();
    _Nodeptr _Wherenode = _Myhead;    // end() if search fails

    while (!_Isnil(_Pnode))
        if (this->comp(_Key(_Pnode), _Keyval))
            _Pnode = _Right(_Pnode);    // descend right subtree
        else
            {    // _Pnode not less than _Keyval, remember it
            _Wherenode = _Pnode;
            _Pnode = _Left(_Pnode);    // descend left subtree
            }

    return (_Wherenode);    // return best remembered candidate
    }

map::find() 는 _Lbound() 를 호출하는데, 컨테이너의 비교 술어 함수를 호출한다. 즉, operator< 로 동등 관계로 판단한다.

참고

• Effective STL - 항목 19, 21