make_heap和排序x和y座標

我想獲得最高座標(x, y) 以下是我寫的代碼，是這個正確的代碼。make_heap和排序x和y座標

#include <vector> 
#include <algorithm> 
#include <iostream> 
#include <iterator> 

struct item_t { 
    int x; 
    int y; 
    item_t(int h, int w) : x(h), y(w) {} 
    friend std::ostream& operator<<(std::ostream& os, const item_t& gt) { 
     os << "(" << gt.x << "," << gt.y << ")"; 
     return os; 
    } 
}; 
typedef std::vector<item_t> item_list_t; 
typedef item_list_t::iterator item_list_itr_t; 

struct compare_x_y { 
    bool operator()(const item_t& left, const item_t& right) const { 
     return left.x < right.x && left.y < right.y; 
    } 
}; 


int main (int argc, char **argv) { 
    item_list_t items; 

    items.push_back(item_t(15, 176)); 
    items.push_back(item_t(65, 97)); 
    items.push_back(item_t(72, 43)); 
    items.push_back(item_t(102, 6)); 
    items.push_back(item_t(191, 189)); 
    items.push_back(item_t(90, 163)); 
    items.push_back(item_t(44, 168)); 
    items.push_back(item_t(39, 47)); 
    items.push_back(item_t(123, 37)); 

    std::make_heap (items.begin(),items.end(),compare_x_y()); 
    std::cout << "initial max heap : " << "(" << items.front().x <<"," << items.front().y << ")" << std::endl; 


}

它是否適用於此輸入，但不適用於其他輸入。

來源

2011-12-26 Avinash

定義'最高'？從字面上看，它意味着：具有最大Y座標的座標。但是你比較它們的方式顯示一個X和Y需要比另一個X和Y大。但是比較（10,1）和（9,15）呢？ – 2011-12-26 14:19:47

是的，我需要安排它們，使得x和y都大於前面的x和y – Avinash 2011-12-26 14:23:09

您對最高座標的定義有些尷尬。你可以添加一些這樣的例子，它不會產生你期望的輸出嗎？ – Jan 2011-12-26 14:24:15

您的比較函數不是strict weak ordering，因此使用它會得到未定義的結果。

它不是一個嚴格的弱排序，因爲等價關係是不可傳遞的。例如，（2,2）相當於（4,1），（4,1）相當於（3,3）。但（2,2）不等於（3,3）。（如果兩個值都不小於另一個，則認爲兩個值相等）。

您將需要提供另一個比較功能。一些例子：

比較x，然後y如果x值相等。
比較兩點的x+y的值。

來源

2011-12-26 14:30:36 interjay

請在您的回答中修復錯字。「tranitive」 - >「transitive」 – werewindle 2011-12-26 14:40:08

好的，謝謝。 ''' – interjay 2011-12-26 14:46:09

另一個選項是* compare max（x，y），如果相等則比較min（x，y）*。這對於OP的問題可能已經足夠好了。 – Sjoerd 2011-12-26 14:55:40

make_heap和排序x和y座標

回答

相關問題