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 < v2
とv2 < 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; } };
つまり、今回の場合だと、先頭の要素から順に比較して、互いに等しくない要素が現れた時点でtrue
かfalse
を返さなければならない、ということ。
これに悩んで2時間もはまっていたがな‥