[C++] The Use of priority_queue And decltype

在 C++ 中要使用 heap structure，最直覺的方法就是使用 STL 的 priority_queue。priority_queue 預設會假定你在 template parameter 所指定的 data type 會支援 operator<，並且利用 operator< 去對資料做排序。其預設的排序行為會行程 max heap，若需要使用的是 min heap，則必須在 template parameter 指定 compare function 或 compare object 的 type，並在 constructor 指定 compare functor 的行為。

在 C++11 推出前，為了提供自定義行為的 functor，會讓 code 變得稍稍難看了點 (請參閱 cplusplus 上的範例)，然而，運用 C++11 的 lambda expression 或是 decltype 即可讓程式碼變得更為簡潔易懂。



舉個例子，假設今天給定一堆整數，想要建一個 min heap，方法如下：

bool cmp (const T& lhs, const T& rhs)
{ return lhs > rhs; }

priority_queue<T, vector<T>, bool (*) (const T& lhs, const T& rhs)> pq(cmp);

請自行把 T 換成自定義的型態 [注]。

根據這段程式碼，可以注意幾個小地方：

1. 這個 compare function 可以視情況改用 lambda expression 來得到更好的便利性
2. function pointer 的型態相當長，所以程式碼會無可避免得很長

根據第二點，就是個使用 decltype 的絕妙場合，因為此時 decltype 會自動幫我們找出該 compare function 的 type 並填入 template parameter，因此本來的工作就交由 compiler 幫我們處理掉了，因此原本的程式碼可以進一步的精簡如下：

bool cmp(const T lhs, const T rhs)
{ return rhs < lhs; }

priority_queue<T, vector<T>, decltype(cmp)> pq(cmp);

看起來就舒服多了，對吧? 而且手殘出錯的機率也就更低了，同樣的方法也適用於不知道該怎麼定義型態的 lambda expression。


[注]
當 T 是 int 或是其他 primitive type 時，可以直接在 template parameter 使用 std::greater 即可變成 min heap。例如

priority_queue<int, vector<int>, std::greater<int>> pq;