STL優先級隊列和用指針重載

這是我第一次使用優先級隊列。我試圖實施Dijkstra的學校算法，我想我需要一個小堆來做到這一點。現在我的節點是指針，我想比較它們的重量，但我不認爲我可以用指針重載>和<？有什麼辦法可以完成這個嗎？STL優先級隊列和用指針重載

代碼這個地步：

priority_queue<Node*, vector<Node*>, node_comparison> minHeap;

然後，我有一個結構比較節點的權重

struct node_comparison 
{ 
    bool operator<(const Node* a, const Node* b) const 
    { 
    return a->totalWeight < b->totalWeight; 
    } 
};

但是它說，有這個操作符函數參數太多。我一直在試圖弄清楚，我現在可以如何使用我的節點管理一個最小堆優先級隊列，並一直卡住。有任何想法嗎？

來源

2013-03-26 Eric Smith

什麼是實際的錯誤？ – 2013-03-26 20:11:34

在[文檔]（http://en.cppreference.com/w/cpp/container/priority_queue/priority_queue）中，請參閱[示例]（http://en.cppreference.com/w/cpp/container/ priority_queue/priority_queue＃示例），它使用['std :: less ']（http://en.cppreference.com/w/cpp/utility/functional/less）。你需要爲'Node *'實現[類似的東西]（http://en.cppreference.com/w/cpp/utility/functional/less#Possible_implementation）。 – 2013-03-26 20:21:18

如果我正確理解你的問題，我相信你真正想要的是讓node_comparison一個仿（更具體地說，一個二元謂詞）：

struct node_comparison 
{ 
    bool operator() (const Node* a, const Node* b) const 
    { 
     return a->totalWeight < b->totalWeight; 
    } 
};

一個仿函數是一個類，其對象提供的電話運營商（operator()），因此，可以用一個你想用調用函數相同的語法被調用的過載：

Node* p1 = ...; 
Node* p2 = ...; 
node_comparison comp; 
bool res = comp(p1, p2) // <== Invokes your overload of operator()

內部，std::priority_queue將像我在上面的代碼片段中那樣或多或少地實例化謂詞，並以此方式調用它來執行其元素之間的比較。

在常規功能仿函數的優點是它們可以容納狀態信息（你可能不會需要的時刻，但結果往往是可取的）：

#include <cmath> 

struct my_comparator 
{ 
    my_comparator(int x) : _x(x) { } 

    bool operator() (int n, int m) const 
    { 
     return abs(n - _x) < abs(m - _x); 
    } 

    int _x; 
};

例如，上述謂詞根據構造時提供的另一個整數的距離來比較整數。這是它如何被使用：

#include <queue> 
#include <iostream> 

void foo(int pivot) 
{ 
    my_comparator mc(pivot); 
    std::priority_queue<int, std::deque<int>, my_comparator> pq(mc); 

    pq.push(9); 
    pq.push(2); 
    pq.push(17); 

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

int main() 
{ 
    foo(7); 

    std::cout << std::endl; 

    foo(10); 
}

來源

2013-03-26 20:13:34

你會需要你的比較仿函數來實現bool operator()(....)，不bool operator<(....)：

struct node_comparison 
{ 
    bool operator()(const Node* a, const Node* b) const 
    { 
    return a->totalWeight < b->totalWeight; 
    } 
};

來源

2013-03-26 20:14:21 juanchopanza

STL優先級隊列和用指針重載

回答

相關問題