HHeLiBeXの日記 正道編

日々の記憶の記録とメモ‥

sortの比較関数の実装ではまった

最初、以下のような実装をしていた。

#include <algorithm>
#include <iostream>

using namespace std;

class ValList {
public:
    vector<int> valList;
    ValList(vector<int> &valList) {
        this->valList = valList;
    }
};

class Comp {
public:
    bool operator()(const ValList *v1, const ValList *v2) const {
        for (int i = 0; i < min(v1->valList.size(), v2->valList.size()); ++i) {
            if (v1->valList[i] < v2->valList[i]) {
                return true;
            }
        }
        return false;
    }
};

int main(int argc, char** argv) {
    int n = 20;
    vector<ValList*> v;
    for (int i = 0; i < n; ++i) {
        vector<int> v1;
        v1.push_back(i);
        v1.push_back(n - i);
        v.push_back(new ValList(v1));
    }

    sort(v.begin(), v.end(), Comp());
}

これを実行すると、なぜか「Segmentation fault」が発生する。なぜ?と思ってCompクラスに以下のようなデバッグコードを入れてみたところ・・・

class Comp {
public:
    bool operator()(const ValList *v1, const ValList *v2) const {
if (v1 == NULL) {
cerr << "v1 is null" << endl;
}
if (v2 == NULL) {
cerr << "v2 is null" << endl;
}
        for (int i = 0; i < min(v1->valList.size(), v2->valList.size()); ++i) {
            if (v1->valList[i] < v2->valList[i]) {
                return true;
            }
        }
        return false;
    }
};
v1 is null
Segmentation fault

と、比較関数に渡されている参照がNULLになっている‥

いろいろ調べて、比較関数は「strict weak ordering」になっていなければならないというのは意識していたのだが、原因がさっぱり分からず‥

で、いろいろデバッグ出力をしながら考えていたら、ふと気づいた。v1 < v2v2 < v1が同時に成り立つことがある実装になっていることに‥

ソートしようとしているデータは以下のようになっている。

[0, 20]
[1, 19]
 :

なので、例えばv1 = [0, 20]v2 = [1, 19]を比較すると、v1[0] < v2[0](0 < 1)かつv2[1] < v1[1](19 < 20)なので、「strict weak ordering」になっていない。

こういう比較をやるときは、以下の様に実装しなければならない。

class Comp {
public:
    bool operator()(const ValList *v1, const ValList *v2) const {
        for (int i = 0; i < min(v1->valList.size(), v2->valList.size()); ++i) {
            if (v1->valList[i] != v2->valList[i]) {
                if (v1->valList[i] < v2->valList[i]) {
                    return true;
                } else {
                    return false;
                }
            }
        }
        return false;
    }
};

つまり、今回の場合だと、先頭の要素から順に比較して、互いに等しくない要素が現れた時点でtruefalseを返さなければならない、ということ。

これに悩んで2時間もはまっていたがな‥