[Effective STL] 21. 연관 컨테이너 비교 함수 객체의 동일값 비교

항목 21. 연관 컨테이너용 비교 함수는 같은 값에 대해 false를 반환해야 한다

 

 

 

같은 값  처리

set< int, less_equal<int> > s; // <=로 정렬되는 set
s.insert(10); // 10을 set에 삽입 1(10A)
s.insert(10); // 10을 set에 삽입 2(10B)

• 이 경우 처리 순서를 보면..

1. 내부 데이터 구조를 뒤지면서 10B를 삽입할 위치를 찾는다.
2. 10B가 10A와 같은지 operator<=를 비교 함수로 써서 체크(equivalent)한다.(항목 19 참조)

   • !(10A <= 10B) && !(10B <= 10A) // 10A와 10B가 동등한지 확인한다.
     // !(true) && !(true) 라고 쓸 수 있을 것이다.
     // 결국 false && false
     // 결과는 false

3. set은 10A와 10B가 동등하지 않다는 결론을 내린다.

• 즉, 비교 함수가 같은 값에 false를 리턴하면 10을 다시 넣으려고 시도하게 된다.(오류)
• 같은 값에 대해 true를 반환하는 비교함수는 모두 이런 결과를 만든다.

 

 

 

주의 사항

• operator!를 사용하는 비교 연산자 반전을 조심할 것

struct StringPtrGreater
{
    bool operator()(const string* ps1, const string* ps2) const
    {
        return !(*ps1 < *ps2); // *ps1 < *ps2의 반대를 만들려고 !를 사용했으나..
        // 결과는 *ps1 > *ps2가 아니라 *ps1 >= *ps2이다.
        // 같은 값에 대해 true를 반환하는 함정에 걸렸다.
    }
}

• set, map 뿐 아니라 multiset, multimap에서도 동일 값에 대해서는 false를 반환해야 한다.
  • 비교 함수가 같은 값에 대해 false를 반환하지 않으면 모든 표준 연관 컨테이너가 올바르게 동작하지 않게 된다.

multiset< int, less_equal<int> > s; // <= 를 사용한다.(같을 시 true 반환)
s.insert(10); // 10A
s.insert(10); // 10B

// std::equal_range를 사용하여 주어진 값의 범위를 찾는다.
// 하지만, 동작하지 않는다..
auto range = std::equal_range(s.begin(), s.end(), 10);
// equal_range는 같은(equal) 값의 범위가 아니라 동등한(equivalent) 값의 범위를 식별한다.
// s의 비교함수에 의해 10A, 10B는 동등하지 않으므로 실패하게 된다.

 

 

 

strict weak ordering

• 연관 컨테이너 요소를 정렬하는 데 사용되는 비교 함수는 비교하고자 하는 객체에 대해 이를 만족해야 한다.
• sort 등의 알고리즘에 넘겨지는 비교 함수(항목 31 참조) 역시 비슷한 제약을 받는다.

 

• 반사성 없음 (Irreflexive) (이번 항목에서 다룬 제약)
  • comp(a, a)는 항상 false여야 한다.
  • 즉, 요소는 자기 자신과 같지 않다고 간주한다.
• 반대칭성 (Antisymmetry)
  • comp(a, b)가 true라면, comp(b, a)는 false여야 한다.
  • 즉, 만약 a가 b보다 작다면, b는 a보다 작지 않다.
• 이행성 (Transitivity)
  • comp(a, b)와 comp(b, c)가 둘 다 true라면, comp(a, c)도 true여야 한다.
  • 즉, a가 b보다 작고, b가 c보다 작다면, a는 c보다 작아야 합니다.
• 비등방성 (Transitivity of Equivalence)
  • comp(a, b)와 comp(b, a)가 둘 다 false라면, a와 b는 같은 순서에 위치한다.
  • 이는 동일한 순서에 있는 모든 요소들이 정렬에서 동일하게 취급된다는 뜻이다.