make_heap使用函數對象

什麼操作符我必須重載make_heap？（）運算符是什麼？如果我已經在我的算法中定義了另一個案例。任何人都可以提供使用make_heap的正確方法。請參閱下面的代碼以更好地理解。make_heap使用函數對象

裏面一個頂點類我有

bool operator() (vertex &v) const 
{ 
    return (v.key() == _key); 
}

這同時在以下STD方法構造圖find_if

vertex_iterator GraphComponents::graph::find_vertex_by_key(int key) 
{ 
    return std::find_if(_vertices.begin(), _vertices.end(), GraphComponents::vertex(key)); 
}

現在在我的算法用於我想頂點使用作爲一個函數對象在不同的情況下。

std::list<int> GraphComponents::graph::breadth_first_search (int key, int start_key) 
{ 
    std::vector<GraphComponents::vertex *> heap; 
    for (vertex_iterator copy_iter = _vertices.begin(); copy_iter != _vertices.end(); ++copy_iter) { 
    heap.push_back(&(*copy_iter)); 
    } 
    std::make_heap(heap.begin(), heap.end(), vertex(<should be distance>)); 
}

這裏，我並不想用在比較關鍵，但我想用一段距離構件，使得具有最短距離的頂點是在堆的頂部。從實施我自己的堆短，什麼是建議的方式呢？

來源

2012-04-16 Matthew Hoggan

實現一個函數，該函數接受您的類型的兩個參數，並且如果左手參數應該被認爲相對小於右手參數，則返回true。（少可以意味着更大）

然後將該函數作爲第三個參數傳遞給make_heap。或者，您可以使用上述語義實現operator<，如果您未傳遞任何功能，將使用該語法。

http://en.wikipedia.org/wiki/Strict_weak_ordering

在你的情況，你的元素是指針，所以你不能寫一個operator<，因爲該功能對所有指針類型已經定義。所以，你必須寫一個單獨的功能，這樣的事情：

bool CompareByDistance(const GraphComponents::vertex * lhs, 
         const GraphComponents::vertex * rhs) 
{ 
    return lhs->distance() < rhs->distance(); 
}

來源

2012-04-16 01:13:28

我試着操作<但是當我跑了它通過調試器，它永遠不會被調用。我將如何使用堆來調用兩個頂點的謂詞？示例代碼將有所幫助。這部分STL對我來說是新的。 – 2012-04-16 01:16:37

非常感謝您的幫助+1 – 2012-04-16 01:34:11

@MatthewHoggan剛剛遇到同樣的問題。將CompareByDistance傳遞給所有make_heap，push_heap和pop_heap函數作爲最後一個參數。 – burkay 2017-03-26 14:03:32

make_heap使用函數對象

回答

相關問題