[Effective STL] 19. 상등(equality)과 동등(equivalence) 관계

항목 19. 상등 관계(equality)와 동등 관계(equivalence)의 차이를 파악하자

 

 

 

STL 비교 동작

• STL의 대부분의 동작은 객체들 사이의 비교 동작이다.
  • find(), insert()
• 이 두 함수는 '두 값이 같은가?'를 알아내는 대표적인 함수이지만, 동작 방식이 상이하다.
  • find
    • 상등성(equality)
    • operator==를 사용한다.
  • insert
    • 동등성(equivalence)
    • operator<를 사용한다.

 

 

 

상등성(equality)

• 어떤 표현식 "x == y"가 참이라고 하면 x, y는 같으며, 거짓이면 다르다.
• 하지만, x, y가 같다고 해서 x, y의 모든 데이터 멤버가 같은 값이라는 뜻은 아니다.

class Widget
{
public:
    ...
private:
    TimeStamp lastAccessed;
    ...
};

bool operator==(const Widget& lhs, const Widget& rhs)
{
    // 같은지의 여부를 알아볼 때 lastAccessed 필드를 고려하지 않음
    // 상등성 체크(operator==)로는 lastAccessed가 달라도 같은 것으로 체크된다.
}

 

 

 

동등성( equivalence)

• 정렬된 범위 안에 있는 객체 값들의 상대적인 순서에 따른다.
  • 모든 연관 컨테이너(set, multiset, map, multimap)가 내부 데이터 요소를 관리할 때 사용하는 정렬 순서
• 컨테이너 c의 어떤 객체 x, y에 대해
  • x, y 모두가 c의 정렬 순서에 대해 서로의 앞에 오지 않으면 x, y는 동등하다.

set<Widget> s;
// s의 멤버 w1, w2에 대해
!(w1 < w2) && !(w2 < w1)
// 위의 식을 만족하면 w1, w2는 동등하다.

// 하지만, 일반적으로 연관 컨테이너 비교 함수는 operator<가 아니라 less이다.
// less는 사용자 정의가 가능한 술어 구조(predicate)이다.(항목 39 참조)
// 그러므로 아래 수식이 좀 더 정확하다.
!c.key_comp()(w1, w2) && !c.key_comp()(w2, w1)

 

 

 

상등성과 동등성 예제

• 임의의 set<string>이 있고, 이 셋은 대소문자를 구분하지 않는다.

/* struct CIStringCompare
{
public:
    binary_function<string, string, bool>
    {
        bool operator()(const string& lhs, const string& rhs) const
        {
            return ciStringComapre(lhs, rhs);
        }
    }
} */
// binary_function은 c++17에서 제거되었으므로
// 아래처럼 구현해야 한다.
struct CIStringCompare
{
public:
	bool operator()(const string &lhs, const string &rhs) const
    {
        return ciStringCompare(lhs, rhs);
    }
};

set<string, CIStringCompare> ciss;

ciss.insert("Persephone"); // 새 요소 추가
ciss.insert("persephone"); // 동등한 것이 있으므로 추가되지 않는다.

// 이 조건문은 참이다.(동등성)
if(ciss.find("persephone") != ciss.end()) ...
// 이 조건문은 거짓이다.(상등성)
if(find(ciss.begin(), ciss.end(), "persephone") != ciss.end()) ...

 

 

 

표준 연관 컨테이너가 상등성이 아닌 동등성에 기반을 둔 이유

• 표준 연관 컨테이너의 요소는 정렬된 순서로 관리되므로, 비교함수가 반드시 필요하다.
  • 기본적으로는 less를 사용한다.
• 만일 표준 연관 컨테이너가 상등성을 지원해야 했다면,
  • 정렬용 비교 함수 외에도 상등성을 알아내는 함수가 하나 더 필요했을 것이다.
• 그렇다면 비교 함수와 상등성을 지원하는 컨테이너가 있다고 가정해 보자.

set2CF<string, CIStringCompare/*동등비교함수*/, equal_to<string>/*상등비교함수*/> s;

// 이렇게 insert 하면 어떻게 될까?
s.insert("Persephone");
s.insert("persephone");
// 두번째 insert는 동등성에 따라 추가되지 않아야 할까?
// 상등성에 따라 추가되어야 할까?

// 마찬가지로, 아래 find는 성공일까 실패일까?
if(s.find("persephone") != s.end()) ...
// find 자체는 상등성 검사를 할 테지만..
// 위의 insert에서 persephone이 insert 되었는지 안되었는지가 결국 중요해진다.

 

 

 

참고

• 표준 연관 컨테이너가 정렬된 요소를 가지지 않는 경우에는 상등성과 동등성을 모두 사용한다.
  • hash_set 등(항목 25 참조)