【備忘録】C++のstd::sortでsegmentation fault

std::sortでややハマったので，忘れないうちにメモしておきます．

std::sortの基本的な使い方

sort.cpp

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

using namespace std;

int main() {
  int data[] = {1, 5, 3, 2};
  vector<int> A(data, data+4);
  sort(A.begin(), A.end());

  // 出力
  for(size_t i=0; i<A.size(); i++) {
    cout << A[i] << ' ';
  }
  cout << endl;

  return 0;
}

コンパイルして，実行します．

$ g++ sort.cpp
$ ./a.out

出力

1 2 3 5

定義した比較関数を使ってソートする（悪い例）

次に少し応用して，定義した比較関数compareを使ったソートを試してみます．

sort_func.cpp

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

using namespace std;

// 比較関数を定義する
bool compare(int i, int j) {
  return i <= j;
}

int main() {
  int data[] = {1, 5, 3, 2};
  vector<int> A(data, data+4);
  sort(A.begin(), A.end(), compare); // 定義した比較関数を使う

  // 出力
  for(size_t i=0; i<A.size(); i++) {
    cout << A[i] << ' ';
  }
  cout << endl;

  return 0;
}

$ g++ sort_func.cpp
$ ./a.out

出力

1 2 3 5

うまく動作します．

同じ値が入った配列をソートする（悪い例）

上のコードを少し変えて，ソートする配列の要素が全て同じ場合を試してみます．
簡単のため，1だけが並んだ配列のソートを試してみます．標準入力から1の個数を与えるようにします．

sort_func_same.cpp

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

using namespace std;

bool compare(int i, int j) {
  return i <= j;
}

int main() {
  // ソートする配列を変更
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i=0; i<N; i++) {
    A[i] = 1;
  }
  sort(A.begin(), A.end(), compare);

  // 出力
  for(int i=0; i<N; i++) {
    cout << A[i] << ' ';
  }
  cout << endl;

  return 0;
}

実際に実行してみます．

$ g++ sort_func_same.cpp
$ ./a.out
10

出力

1 1 1 1 1 1 1 1 1 1

うまく動作している？

$ ./a.out
100

出力

0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

んん？

$ ./a.out
100000

出力

Segmentation fault

セグフォしてしまいました．

原因と結論

比較関数の中で，値が同じ場合はfalseを返すようにしないといけませんでした．

bool compare(int i, int j) {
  return i < j;
}

ある配列をソートしようとするとき，単純に考えると，ある２つの要素を取ってきて，比較関数にかけたときの返り値がtrueの場合にその２つの要素を交換します．このとき，比較関数をreturn i <= j;としてしまうと，iとjが等しい場合に，

1. 比較関数がtrueを返して，iとjをひっくり返す．
2. ひっくり返ったiとjを再度比較することがあった場合に，またまたtrueを返して，ひっくり返す．

といった感じで連続してひっくり返し続けてしまうのが原因ではないかと考察しました．実際のstd::sortではアルゴリズムとしてクイックソート（の改良版であるイントロソート）が使われているそうで，その際の要素のアクセス順などの厳密な考察はしていませんが，大雑把に考えるとそういうことでしょうか．上の例で，要素数が小さいときには支障がなかった（ように見えた）り，100くらいのやや大きめの値を入れたときにどこからか0が湧いてきたりするのは謎ですが，比較演算子を等号なしの不等号に変更すると問題なく動作しました．

今回は単純な例で試してみましたが，自分がハマったのはもう少し複雑な比較関数でした．今後比較関数を自前で定義するときは，比較関数に等号が成立してしまう条件は入れないように気をつけようと思います．

参考

sort - cpprefjp C++日本語リファレンス
sort function C++ segmentation fault - Stack Overflow

更新

[2020/04/30] コードの記法をやや変更しました．