Strict weak ordering

   strict weak ordering 은 strict partial order 이면서 incomparability가 equivalence를 의미하는 order 이다. 우선 strict partial order의 정의를 살펴 보자.

집합 A와, A에서 정의된 relation〈 에 대하여〈 가 다음 두 조건을 만족시키면〈 는 strict partial order이다.
i) a〈 a 는 성립하지 않는다 (nonreflexivity)
ii) a〈 b 이고 b〈 c 이면 a〈 c 이다 (transitivity)
for a, b, c ∈ A.

이 때 strict partial order 이기 때문에 〈 는 A의 모든 원소에 대해 비교가능할 필요는 없다. 이 상태에서〈 가 weak ordering 이 되면서 추가되는 조건, 즉

incomparability는 equivalence를 의미한다.

에 의해〈 는 total ordering 이 된다. 즉, A x A 의 모든 pairs (a,b) ∈ A x A 에 대하여, a〈 b 가 정의되거나, 정의되지 않을텐데, 정의되면 그것으로 끝이고, 정의되지 않으면 equivalence 인 것이다. 즉, '같다'^[각주:1]. 따라서 strict weak ordering〈 에 의해 집합 A의 모든 원소쌍은 관계를 갖게 된다.

   수학적 관계(relaion)의 일종인 '<' 이 집합 A 에 대하여 정의될 때, A의 모든 원소에 대하여 <  가 정의될 필요는 없다. 예를 들면 모든 복소수 집합 C 에 대하여 '<'를 실수에 대해서만 정의하는 것과 같은 것이 있다. STL에서 요구하는 operator< 는, 그러나, 위의 설명에 따라 모든 원소에 대하여 연산이 가능해진다. 즉, operator< 에 의해 비교가능한 두 원소의 쌍 (a,b)는 참이거나 거짓이고 (a<b 가 참이거나, b<a가 참이거나, but not both (asymmetric)), 만약 그 둘이 모두 성립하지 않는다면 둘을 같은 것으로 간주한다. 이와 같은 특성 때문에 STL에서는 operator== 를 정의해주지 않은 객체도 set이나 map에 넣을 수 있게 된다. 즉, 동일 타입의 두 변수 a,b에 대하여 a<b 와 b<a 가 모두 거짓이면 둘은 같다고 보는 것이다.

위에서 'strict' 라는 말이 쓰인 이유는, non-strict인 경우는 주로 '≤', 즉 '<' 또는 '=' 에 대하여 사용하기 때문이다. 즉 '≤'는 non-strict 이고 '<'는 strict 인 것이다. STL의 입장에서 생각해 보면 'a≤b and b≤a 이면 a==b' 이기 때문에 operator== 를 위해서라면 partial ordering 도 괜찮을 것 같은데 왜 굳이 strict weak ordering 을 했는지는 명확히 알지 못하겠다. 한 가지 생각은 operator< 를 정의하는 것은 operator<= 를 정의하는 것보다 명확하기 때문이 아닌가 한다. operator<=는 '< 또는 ='를 의미하기 때문에 정의하는 입장(프로그래머 입장)에서는 < 와 == 둘을 모두 고려하는 operator<= 보다는 < 만 고려하는 operator< 가 더 명확하고, 이것만으로도 operator== 가 저절로 정의될 수 있기 때문이다. 또한 C++의 경우 일반적으로 배열에는 동일 타입의 변수만을 집어 넣게 되는데 그 때 과연 'partial' 이나 incomparability 라는 상황이 생길 수 있을까? (파이썬이라면 모를까...) 하여튼 이 부분은 좀 난해하다.

---

   이제 실제 코드로 살펴 보자. STL의 set 이나 map에 객체를 집어 넣기 위해서는 그 객체가 operator< 를 갖고 있어야 한다. 즉 set에 집어 넣는 객체에 대하여 operator< 를 호출할 수 있어야 한다. 왜냐 하면 성능의 최적화를 위하여 set과 map은 내부적으로 binary search를 이용하는데(표준 문서에 그것을 이용하라고 specify되어 있지는 않다고 한 것 같다), 그러기 위해서는 operator< 연산을 할 수 있어야 하기 때문이다. 이 전 글 에지(edge) 객체 구현해 보기 에서 정의한 operator< 를 살펴 보자.

bool edge::operator<(const edge& e) const {

 

        const std::string& max1 = (_node1 > _node2 ? _node1 : _node2);

        const std::string& max2 = (e._node1 > e._node2 ? e._node1 : e._node2);

 

        if(max1 == max2){

                const std::string& min1 = (_node1 < _node2 ? _node1 : _node2);

                const std::string& min2 = (e._node1 < e._node2 ? e._node1 : e._node2);

                return min1 < min2;

        }

        return max1 < max2;

}

  
위의 정의는 위에서 언급한 strict weak ordering 의 정의를 만족한다. 즉,
i) (a,b) < (a,b) 성립하지 않는다 (if 문 안쪽으로 들어간 후 false 를 return 한다)
ii) (a,b) < (c,d) 이고 (c,d) < (e,f) 이면 (a,b) < (e,f) 이다.
(증명) (a,b) < (c,d) 이므로 'max{a,b} < max{c,d}'(1) 이거나 'max{a,b} == max{c,d} 이고 min{a,b} < min{c,d}'(2)이다.
(c,d) < (e,f) 이므로 'max{c,d} < max{e,f}' (3)이거나 'max{c,d} == max{e,f} 이고 min{c,d} < min{e,f}'(4)이다.
(1), (3) 인 경우
   max{a,b} < max{c,d} 이고 max{c,d} < max{e,f} 이므로 max{a,b} < max{e,f} 이다.
(1), (4) 인 경우
   'max{a,b} < max{c,d}'이고, 'max{c,d} == max{e,f} 이고 min{c,d} < min{e,f}' 이므로, max{a,b} < max{c,d} == max{e,f} 이므로 max{a,b} < max{e,f} 이다.
(2), (3) 인 경우
   'max{a,b} == max{c,d} 이고 min{a,b} < min{c,d}' 이고 'max{c,d} < max{e,f}' 이므로 max{a,b} < max{e,f} 이다.
(2), (4) 인 경우
   'max{a,b} == max{c,d} 이고 min{a,b} < min{c,d}' 이고, 'max{c,d} == max{e,f} 이고 min{c,d} < min{e,f}' 이므로 max{a,b} == max{c,d} 이고 max{c,d} == max{e,f} 이다. 따라서 max{a,b} == max{e,f} 이다. 또한 min{a,b} < min{c,d} 이고 min{c,d} < min{e,f} 이므로 min{a,b} < min{c,d} < min{e,f} 이므로 min{a,b} < min{e,f} 이다. 따라서 max{a,b} == max{e,f} 이고 min{a,b} < min{e,f} 이다. QED.

위의 조건만으로도 모든 edge가 비교가 가능하기 때문에 strict weak ordering의 세 번째 조건 incomparability 가 equivalence를 의미한다는 사용되지 않는다.

만약 operator< 를 다음과 같이 정의했다고 가정해 보자.

bool edge::operator<(const edge& e) const {

 

        const std::string& max1 = (_node1 > _node2 ? _node1 : _node2);

        const std::string& max2 = (e._node1 > e._node2 ? e._node1 : e._node2);

 

        //if(max1 == max2){

        //        const std::string& min1 = (_node1 < _node2 ? _node1 : _node2);

        //        const std::string& min2 = (e._node1 < e._node2 ? e._node1 : e._node2);

        //        return min1 < min2;

        //}

        return max1 < max2;

}

  
즉 'max 값이 큰 것이 크다'라고. 그러면 a > b ≠ c 에 대하여  (a,b) < (a,c) 도 false 가 return 되고 (a,c) < (a,b) 도 false 가 return 된다. 따라서 (a,b)와 (a,c)는 같은 것이 된다^[각주:2]. 그러나 edge 를 정의할 때 이와 같은 상황을 의도하는 경우는 거의 없기 때문에 위의 정의는 제대로 동작하지 않게 된다. 물론 compile 에러도 나지 않고 run-time 에러도 나지 않는다. 단지 논리적 에러가 생겨서 결과가 우리가 의도하지 않은 값이 나올 뿐이다.

참고: strict weak ordering

1. 실제로 '같다'는 것이 아니라, 같은 것으로 간주된다는 의미이다. 만약 이렇게 간주하는 것이 잘못된 것이라면 operator< 를 잘못 정의한 것이다, 아래의 예에서처럼. [본문으로]
2. 다시 말하지만, a < b 와 b < a 가 둘 다 거짓이면 a==b 로 간주한다는 것이다. 지금 우리는 <와 == 를 동시에 '정의'하고 있는 것이다, 결과적으로. [본문으로]