sort 시 seg fault발생 - strict weak ordering

 지난주에 programmers lv1 실패율 문제를 풀다가 seg fault가 났었다. 내가 알던 seg fault는 잘못된 memory에 접근하는 경우에 생겼기 때문에 vector의 index를 잘못 참조하지 않는지 확인했지만 아무리 봐도 그런 경우가 없었다.

 그래서 이것저것 디버깅을 해 보다가 sort 함수를 빼면 seg fault가 안 나는 것을 확인했고, 그러다가 결국 정렬 함수에 문제가 있다는 것을 알게 되었다.

 아래는 내가 쓴 코드다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, double> pid;

bool comp(pair<int, double>& a, pair<int, double>& b){
    if(a.second > b.second) return true;
    else{
        return a.first < b.first;
    }
}

vector<int> solution(int N, vector<int> stages) {
    vector<pid> v;
    ...
    // 여기서 v에 적당한 값을 넣는다.    
    sort(v.begin(), v.end(), comp);

    vector<int> answer(N);
    for(int i = 0;i <N; i++){
        answer[i] = v[i].first;
    }
    return answer;
}

 그냥 코드 자체만 봐도 정렬에서 오류가 있다. a.first와 b.first를 비교하는 상황은 a.second == b.second라는 조건이 선행되어야 하는데 이 선행조건 없이 a.first < b.first를 바로 비교했기 때문이다.

 반례로,{3, 0.7}과 {4, 0.8}을 정렬하는 상황을 생각해 보자. 내가 작성한 comp 함수는 second를 먼저 내림차순으로 정렬하고 first를 오름차순으로 정렬하는 함수다. 따라서 {4, 0.8}, {3, 0.7}로 정렬되어야 한다. 그러나 comp의 a에 {3, 0.7}, b에 {4, 0.8}이 들어가면 else문으로 들어가서 true가, comp의 a에 {4, 0.8}, b에 {3, 0.7}이 들어가면 if문으로 들어가서 true가 리턴된다. 순서가 바뀌어야 하는데, 그렇지 않다! 즉, 코드를 잘못 작성한 것이다.

 맞왜틀은 존재하지 않는다!

 아무튼 코드를 잘못 작성하긴 했지만, 정확한 이유를 알아보자. c++에서 정렬함수를 customize해서 사용할 때는 strict weak ordering을 만족시켜야 한다. 이게 뭔지 알아보자.

 

 

 

Strict Weak Ordering

 아래 4가지 명제를 만족하는 것과  strict weak ordering은 동치이다. 즉, strict weak ordering을 만족하기 위해서는 아래 4가지 명제를 만족해야 한다. 설명은 comp(a, b)는 a < b일 때 true를 리턴한다고 가정하겠다.

1. comp(a,a) = false
    - 자기자신과의 비교는 false여야 한다. (a < a는 false)
2. comp(a,b) = true THEN comp(b,a) = false
    - a < b가 true라면 b < a는 false이다.
3. comp(a,b) = true AND comp(b,c) = true THEN comp(a,c) = true
    - a < b이고 b < c라면 a < c여야 한다.
4. comp(a,b) = false, comp(b,a) = false, comp(b,c) = false, comp(c,b) = false THEN comp(a,c) = false, comp(c,a) = false
    - a > b이고 b > a이고, b>c이고 c>b이면 a>c and c>a이다.
    - a = b이고 b = c이면 a = c여야 한다는 의미이다.

 내가 작성한 코드는 적어도 2번 명제를 만족하지 않는다. 이를 아래와 같이 작성하면 4개의 명제를 만족하게 되면서, seg fault가 해결된다.

 

bool comp(pair<int, double>& a, pair<int, double>& b){
    if(a.second > b.second) return true;
    else if(a.second < b.second) return false
    else{
        return a.first < b.first;
    }
}

 -> 조금 귀찮더라도, a와 b를 비교할 때 <, ==, >를 확실하게 표기하는 게 정확한 것 같다.

 -> 추가적으로, comp 함수가 true이면 첫 번째 인자(a)가 두 번째 인자(b)보다 앞에 있다고 생각한다. 그래서 내림차순 정렬이면 a > b로, 오름차순 정렬이면 a < b로 하면 된다.