[C++] sort에서 cmp함수를 설정할 때 주의할 점

1181번: 단어정렬

위 문제를 풀 때, algorithm 헤더의 sort 함수로 문자열 순서를 정렬할 때,
마지막 인자로 비교함수를 커스텀해서 넣어주는 부분이 있는데

비교함수를 잘못만들어서 런타임에러로 한참을 헤맸다.

다른 부분에서도 문제가 없었는데 왜 런타임에러가 났는지 이 질문 글을 통해 알 수 있었다.

bool cmp(string a,string b){
    if(a.size()!=b.size()){
        return a.size()<b.size();
    }
    else{
        for(int i=0;i<a.size();i++){
            if(a[i]==b[i])
                continue;
            else{
                if(a[i]<b[i])
                    return true;
                else
                    return false;
            }
        }
        return true; // 이 부분이 문제!!
    }
}

위 cmp 함수에서 보면 다른 부분은 문제가 없지만 끝의 경우,
그러니까 두 문자열이 길이도, 철자도 모두 같은 경우 cmp 함수는 true를 리턴하게 되어있다.

C++ Compare Function Object

위 링크를 보면 cmp(a,a) 처럼 같은 객체가 들어오면 false 를 리턴하는게 필수로 요구된다.

내 코드는 같은 객체의 경우에 true를 리턴했으므로 런타임에러가 난 것이다.

그 밖에도 compare 함수를 커스텀할 때 지켜야할 것들이 있는데 그것을 Strict Weak Ordering 이라 한다.

이산수학에서 배우는 Relation과 관련된 것인데, 대표적으로

1. comp(a,a) == false (반사 관계)
2. 만약 comp(a,b) == true 이면 comp(b,a) == false 이다. (비대칭 관계)
3. 만약 comp(a,b) == true 이면서 comp(b,c) == true 이면, comp(a,c) == true 이다. (전이관계)

3가지 정도가 있다.
sort를 사용할 때던, 비교연산자를 오버로딩(overloading)할 때던 주의해야할 사항이다.

bool cmp(string a,string b){
    if(a.size()!=b.size()){
        return a.size()<b.size();
    }
    else{
        for(long unsigned int i=0;i<a.size();i++){
            if(a[i]==b[i])
                continue;
            else{
                if(a[i]<b[i])
                    return true;
                else
                    return false;
            }
        }
        return false; // false로 고친다.
    }
}

false로 바꿔줌으로써 문제가 해결되었다.

추가자료 : strict_weak_ordering