使用自定義值比較器的提升最小隊列

Question

我想在稀疏圖上實現最短路徑搜索（這不是一個提升圖，可能無法高效地轉換爲一個），所以我自然堅持使用優先級來實現Dijkstras算法隊列。由於我的圖是一個自定義的，我需要實現的距離比較，因爲一個函數對象，並把它交給隊列：

#include <boost/heap/fibonacci_heap.hpp> 
#include <iostream> 
#include <climits> 

#define BIG (INT_MAX/2) 

struct node_compare { 
    std::vector<int> dist; 

    void set(int node, int d) { 
    dist[node] = d; 
    } 

    node_compare(int dim) : dist(dim, BIG) {}; 

    /* this is a 'greater than' because boost implements max-heaps */ 
    bool operator()(const int& n1, const int& n2) const { 
    std::cout << "Comparing " << n1 << " < " << n2 << " = " << dist[n1] << " > " << dist[n2] << std::endl; 
    return dist[n1] > dist[n2]; 
    } 

}; 

typedef boost::heap::fibonacci_heap<int, boost::heap::compare<node_compare>> priority_queue; 

int main(int argc, char** argv) { 
    /* comparator implementation, based on distances */ 
    node_compare cmp(5); 

    priority_queue pq(cmp); 

    cmp.set(3, 10); 

    for (int i = 0; i < 5; i++) 
    pq.push(i); 

    while(!pq.empty()) { 
    std::cout << pq.top() << std::endl; 
    pq.pop(); 
    } 
} 

什麼打動我的是，不知何故優先級隊列似乎建立自己的node_compare實例，儘管我在構造函數中提供了一個實例。這應該不可能，因爲node_compare沒有默認構造函數...

我知道這看起來有點像「請爲我找到那個bug」 - 問題的種類，但我真的沒有知道我是否錯過了一些重要的C++語義或者提升邏輯。

Answer 1

堆確實存儲它自己的node_compare的實例，但不會默認構造它，而是從您在構造函數中傳遞的對象構造它。

因此，在隊列priority_queue pq(cmp);中，隊列使用node_compare類的自動生成的拷貝構造函數複製cmp對象。

如果在創建priority_queue之前調用cmp.set(3, 10);，它也應該設置在隊列的比較器中。

恐怕您創建堆後無法更改比較器。堆對象有一個value_comp()成員函數，它返回一個const引用給比較器，所以你不能改變返回的比較器。我認爲你不能改變比較器，因爲這會使堆中的數據結構無效。

但是你可以存儲到比較內部的距離向量的引用：

struct node_compare { 
    const std::vector<int> &dist_; 

    node_compare(const std::vector<int> &dist) : dist(dist) {}; 

    bool operator()(const int& n1, const int& n2) const { 
     return dist_[n1] > dist_[n2]; 
    } 
}; 

你只需要要小心，你不改變傳送的距離矢量您添加的元素到您的堆後。