読者です 読者をやめる 読者になる 読者になる

のんびり読書日記

日々の記録をつらつらと

STLのvectorとpriority_queueのソート用比較関数は不等号が逆

この前自分のソースを読んでいたら、両方とも降順にソートするために作った比較関数なのに何故か不等号が逆になっていて、「うわ、ひどいバグ作っちゃった?!」って慌ててテストしたら問題なし。調べてみると、STLvectorとpriority_queueのソート用比較関数は何故か不等号が逆になっちゃうんですね。

#include <cstdlib>
#include <vector>
#include <queue>
#include <iostream>

struct StructGreater {
  bool operator() (int a, int b) {
    return a < b;
  }
};

bool funcGreater(int a, int b) {
  return a > b;
}

int main() {
  std::priority_queue<int, std::vector<int>, StructGreater> q;
  std::vector<int> v;
  size_t max = 10;
  for (size_t i = 0; i < max; i++) {
    int n = rand() % 100;
    q.push(n);
    v.push_back(n);
  }
  sort(v.begin(), v.end(), funcGreater);

  for (size_t i = 0; i < max; i++) {
    std::cout << "v:" << v[i] << "\tq:" << q.top() << std::endl;
    q.pop();
  }
  return 0;
}

ランダムに生成した整数列をvectorとpriority_queueに入れて、ソートして出力してみます。StructGreaterとfuncGreaterで不等号は逆なのですが、結果はちゃんと両方とも降順にソートされています。

% g++ sort.cc
% ./a.out
vector:93       queue:93
vector:92       queue:92
vector:86       queue:86
vector:86       queue:86
vector:83       queue:83
vector:77       queue:77
vector:49       queue:49
vector:35       queue:35
vector:21       queue:21
vector:15       queue:15

知ってる人にとっては当たり前なのかもしれないけど、念のためメモメモ。