priority_queueにおける比較関数の渡し方（c++）

経緯

c++でヒープを実装する時に、カスタム比較関数を渡す必要性が生じたがその方法がわからなかった。
（連結リストのノードの値をもとにヒープを構築するための比較関数が必要となった）

// This code won't work
bool compare(ListNode* a, ListNode* b) { return a->val > b->val}
priority_queue<ListNode*, vector<ListNode*>, compare> minHeap(k);

関数を定義してそれを渡せば良いくらいの認識であったが、どうやらそうではないらしい。ここで、c++のpriority_queueにおける比較関数の渡し方について調べてみると何も理解していなかったことに気づいたので以下に整理したことをまとめる。

本題

c++におけるstd::priority_queueは（https://cplusplus.com/reference/queue/priority_queue/）で定義されている。

template <class T, class Container = vector<T>,  class Compare = less<typename Container::value_type> > class priority_queue;

具体的には上記のようなクラステンプレートとなっている。
ここで、注目すべきは第３テンプレートパラメータでオブジェクトclass Compareを期待していることだ。上記のコードでただの関数ポインタを与えても動かない理由だ。そもそも、これは引数ではなくてテンプレートパラメータだから関数のポインタや実体を与えても全く動かないのは当然である。class priority_queueはこのテンプレートパラメータで与えられた型を元にオブジェクトを生成しているというわけだ。

では実際どのようにして比較関数を渡せば良いのだろうか。

もう少し理解するために、以下（https://en.cppreference.com/w/cpp/header/queue）の詳細なクラスの定義を見てみることにする。
重要なところを取り出すと

template <class T, class Container = std::vector<T>, class Compare = std::less<T>>
class priority_queue {
protected:
    Container c;
    Compare comp;

public:
    // ①
    priority_queue()
      : priority_queue(Compare())
    {
    }
    // ②
    explicit priority_queue(const Compare& x)
      : priority_queue(x, Container())
    {
    }
    // ③
    priority_queue(const Compare& x, const Container&);
};

のような形になっている。このコードの後半部分よりpriority_queueのクラスがどのようにコンストラクトされるかがわかる。

1. operator()を持つ関数オブジェクトを使用

struct Compare {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

priority_queue<ListNode*, vector<ListNode*>, Compare> minHeap;

この場合関数オブジェクトを用いてテンプレートパラメータに渡している。
オブジェクトとして渡されたCompareを元に内部ではそのインスタンスを生成している。
引数がない時は、コンストラクタ①→②→③というように委譲されていく。この過程でCompare()によってオブジェクトがコンストラクトされ、そのインスタンスであるcomp(ListNode* a, ListNode* b)を直接比較関数のように使えるようになる。

2. Lambda関数を使用

auto compare = [](ListNode* a, ListNode* b) { return a->val > b->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(compare)> minHeap(compare);

ラムダ関数を使用する場合declared type(decltype)を使用してオブジェクトの型を渡す必要がある。Lambda関数は内部的に関数オブジェクトに変換されているため基本的に関数オブジェクトと同じと考えて良い。(名前のないFunctorを作る）
ただし、ここでdecltypeはオブジェクトの型であり、オブジェクトとして変数の状態を保持しているものではないためその実体を引数として渡す必要がある。（基本、キャプチャなしのラムダ関数は、状態（メンバ変数）を一切持たない無状態（stateless）な関数オブジェクトになるので問題にはならないが、キャプチャを取りうる仕様上その実体も引数として渡す必要がある。）
この場合、引数があるため、コンストラクタ②→③というように委譲されていき、その過程で引数に与えた実体を元にpriority_queueが構築される。

3. 関数ポインタを使用

bool compare(ListNode* a, ListNode* b) { return a->val > b->val};
priority_queue<ListNode*, vector<ListNode*>, bool(*)(ListNode*, ListNode*)> minHeap(compare);

この場合関数ポインタの型をテンプレートパラメータに与えてその実体（ポインタ）を引数として渡している。
この場合はラムダ関数と同じように引数があるため、コンストラクタ②→③というように委譲されていきその過程で実体を元に比較関数が作られている。この場合オブジェクトにはならないが、priority_queue内で

class priority_queue {
protected:
    Container c;
    // Compare => bool(*)(ListNode*, ListNode*)
    bool(*)(ListNode*, ListNode*) comp;
}

に変換され、comp(ListNode* a, ListNode* b)のように比較が可能となるため要件を満たしている。（関数ポインタは関数呼び出し演算子 () を持つため、関数オブジェクト（ファンクタ）と同じように扱える）

まとめ

以上より、３つの方法でカスタム比較関数を渡せることが確認できた。それぞれc++における関数ポインタや関数オブジェクトを理解する必要があり複雑である。

備考

可能な限り調べましたが、理解の間違いなどありましたら是非ご指摘いただけますと幸いです。