vector를 sort 한 이후 문제가 생길 때

   자신이 만든 비교함수(binary predicate)를 이용하여 vector 를 비교를 하고자 했는데 에러가 난 상황. 이 경우 주로 sort 를 두 번째 하려고 할 때 에러가 발생. 그렇다면 binary predicate 가 잘못 정의되었을 가능성이 있다^[각주:1].

환경 : Visual C++ 6.0 on Windows XP SP3

(급해서 일단 VC 6.0 으로 작업. 나도 VC 2010 있다. -_-;;;)

   디버그 모드로 실행시켰을 때, 다음과 같은 에러가 났다.

Access violoation. 이 에러는 일반적으로 접근하지 말아야 하는 메모리를 접근했을 때 나타나는 에러로, release mode 라면 다음과 같은 친근한(?) 에러 메세지를 볼 수 있다.

다시 debug mode로 실행시켜서 call stack 을 따라가 보자.

상황은, binary predicate 는 vector 로 된 operand 2개를 받게 되는데, 그 중 한 개의 operand 를 제대로 접근할 수 없는 경우다. _compare_col 번째 요소에 대해서 (그 요소는 std::string type 인데) c_str() 함수를 호출할 때 문제가 발생한 것이다. 실제로 인자로 넘어 온 [op2]를 Variables 창에서 보면 값이 제대로 입력되지 않은 것을 알 수 있다. binary predicate가 제대로 정의되지 않았기 때문에 위와 같은 문제가 발생했을 것이란 심증은 많은데, std::sort 가 VC 에서 구현된 코드를 보니 그것을 명확히 알기는 좀 어렵다. 어쨌든, 계속 나아가자.

자, 위와 같은 상황이, 내가 만든 binary predicate 때문에 발생하고 있다면, 그리고 두 번째로 sort 를 할 때 문제가 발생하므로, 아마도 내가 만든 binary predicate 가 STL 의 sort algorithm 이 지켜야 하는 strict weak ordering 을 지키지 않았기 때문일 것이다. 실제로 내가 sort 의 세 번째 인자로 넘기려고 만든 함수 객체(functor)는 다음과 같다.

class vector_compare{

public:

    int        _compare_col;

    bool    _reverse;

    bool operator()(const std::vector<std::string>& op1, const std::vector<std::string>& op2) const{

        double v1 = atof(op1.operator[](_compare_col).c_str()) ;

        double v2 = atof(op2.operator[](_compare_col).c_str()) ;

        return (v1 > v2) == _reverse;

    }

};

내가 약간 착각한 것이

        return (v1 > v2) == _reverse;

이 부분인데, 난 보통 변수를 토글시킬 때 저런 식으로 하는데, 저렇게 하면 문제가 생기는 것은 다음과 같이 알 수 있다. 우선, STL의 경우, strict weak ordering 에서

not (a > b) and not (b > a) iff a <= b and b <= a

따라서 a == b 가 된다. 즉, sort 를 할 때 a > b 도 b > a 도 아니면 두 요소는 같다고 간주된다. 그러나 위처럼 정의해 버리면 다음과 같이 오류가 발생한다.

Suppose v1 == v2 and _reverse is False. Then,
i) (v1 > v2 ) == F conforms to F == F, thus T.
ii) (v1 < v2) == F conforms to F == F, thus T.

즉, 위처럼 되면 v1 > v2 여도, v2 > v1 이어도 모두 True 가 반환된다. 원래는 둘다 모두 False 가 반환되어 결과적으로 v1 == v2 가 되어야 함에도 불구하고 True 가 반환된 것이다. v1 이 op1 으로 넘어 가고, v2 가 op2 로 넘어가도 v1 > v2 처럼 True 가 반환되고, v2가 op1 으로, v1 이 op2 로 넘어 가도 True 가 반환되는 것이다. 이렇게 되면 같은 두 값 v1과 v2를 비교하는데도 어떤 땐 v1 이 크게 나오고 어떨 땐 v2 가 크게 나오겠지.

따라서 다음과 같이 직관적으로 바꾸면 문제는 해결된다.
  

class vector_compare{

public:

    int        _compare_col;

    bool    _reverse;

    bool operator()(const std::vector<std::string>& op1, const std::vector<std::string>& op2) const{

        double v1 = atof(op1.operator[](_compare_col).c_str()) ;

        double v2 = atof(op2.operator[](_compare_col).c_str()) ;

 

        if(_reverse == true){

            return v1 < v2;

        }

        return v2 < v1;      

    }

};

1. 이런 경우에 대한 '모든' 원인을 내가 언급할 수는 없다. 단지 내가 직접 경험한 경우만을 언급할 수 있을 뿐이다. [본문으로]