std::priority_queue に自作のラムダ式の比較関数を渡す

C++

ABC307 F - Virus 2 でハマったのでメモ。

ツイートは こちら。（教えてくださった方に感謝。）

a < b という関係が成り立つときに a から先に要素を取り出したいとします。

  • ダメなやつ
auto comp = [](const T& a, const T& b) -> bool {
    return a < b;
};

std::priority_queue<T, std::vector<T>, decltype(comp)> que(comp);

※デフォルトで std::less が渡されているのに大きい順に pop されることに想いを馳せてみましょう。

  • 動くやつ
auto comp = [](const T& b, const T& a) -> bool {
    return a < b;
};

std::priority_queue<T, std::vector<T>, decltype(comp)> que(comp);

取り出したくないやつを引数の左側に持ってくると良いです。

だいたい T = std::tuple<int, int, int> みたいなやつが出てきたときにラムダ式を書きたくなるので、 他には std::greater<T> を渡して適宜符号を反転させる方法もあります。

std::sortと同じ感覚でやると大変なことになる（なりました）ので、気を付けましょう。