我的邊緣在哪裏？

我正在嘗試使用std::set，我將在其中扔出一堆邊緣，並且只留下唯一的邊緣。我的邊緣在哪裏？

Edge是兩個（整數索引）節點之間的一條線。邊緣(1,2)==(2,1)，因爲這些邊緣是無向的。

雖然我遇到了一個令人費解的情況，在下面的代碼中標記爲//??的部分，行爲不符合我的預期。

運行此代碼的結果僅保留2個邊（1,2）和（4,8）。（2,1）被設置丟棄，但它不應該是，除非我激活operator==中的註釋//|| (A==o.B && B==o.A)部分！這裏發生了什麼？

這set<Edge>執行讓我感覺..前衛。

#include <stdio.h> 
#include <set> 
using namespace std ; 

struct Edge 
{ 
    int A,B ; 
    Edge(int iA, int iB) : A(iA), B(iB) {} 
    bool operator==(const Edge & o) const { 
    //?? 
    return (A==o.A && B==o.B) ;//|| (A==o.B && B==o.A) ; 
    } 
    bool operator<(const Edge& o) const {//MUST BE CONST 
    return A < o.A && B < o.B ; 
    } 
    void print() const { printf("(%d, %d)", A,B) ; } 
    void compare(const Edge& o) const { 
    print() ; 
    if(*this==o) printf("==") ; 
    else printf("!=") ; 
    o.print() ; 
    puts(""); 
    } 
} ; 

int main() 
{ 
    Edge e1(1, 2) ; 
    Edge e2(1, 2) ; 
    Edge e3(2, 1) ; 
    Edge e4(4, 8) ; 

    e1.compare(e2) ; 
    e1.compare(e3) ; 
    e1.compare(e4) ; 

    set<Edge> edges ; 
    edges.insert(e1) ; 
    edges.insert(e2) ; 
    edges.insert(e3) ; 
    edges.insert(e4) ; 

    printf("%d edges\n", edges.size()) ; 
    for(auto edge : edges) 
    { 
    edge.print(); 
    } 
}

來源

2012-12-21 bobobobo

@HunterMcMillen另外，'<'必須實現這一點（因爲它是內部集的順序相應的操作員）。 – Nobody

是的，它會在最後的實現中，我只是想知道爲什麼（2,1）被排除在set之外。已被註釋掉_ – bobobobo

嗯。那麼'（1,2）<（2,1）'是錯誤的，'（2,1）<（1,2）'也是錯誤的。 – bobobobo

我建議你改變你的邊緣（）構造函數，以確保A和B總是被初始化，使得A<=B（如果邊緣可以指向回自己的源節點）或A<B（如果不是），並放棄在operator ==實現中的額外邏輯。這對我來說似乎不那麼「鋒利」。

來源

2012-12-21 20:48:32 phonetagger

哇！很好的答案。我只是重寫了構造函數，'A = min（iA，iB）; B = MAX（IA，IB）;'。獎勵積分效率！當然，這意味着'Edge'對象中的'A'和'B'需要被保護成員，'set'函數必須被寫入，但是爲了我的目的，它們不會被改變。 – bobobobo

我相信你operator<是錯誤的，既e3<e2和e2<e3都是假的。

也許你想要的東西，如：

return A < o.A || ((A == o.A) && (B < o.B)) ;

來源

2012-12-21 20:48:24 Mat

C++ set不關心您的==操作符，它與您的<操作符相同。這是你的<運營商呈現的問題：如果你想確保(1,2)等於(2,1)，你應該改變你的<的實施，這樣的表現：

bool operator<(const Edge& o) const { 
    int myMin = min(A, B); 
    int myMax = max(A, B); 
    int hisMin = min(o.A, o.B); 
    int hisMax = max(o.A, o.B); 
    return myMin < hisMin || (myMin == hisMin && myMax < hisMax); 
}

什麼這個實現確實是構建一個規範表示的邊緣，其中{A,B}中的較小者變成「規範A」，並且較大者變成「規範B」。當以其規範形式比較邊緣時，從(1,2) < (2,1)和(2,1) < (1,2)評估爲false的事實，(1,2)和(2,1)的相等性可以是暗示的。

來源

2012-12-21 20:49:22 dasblinkenlight

-1

您的比較應該是

return (A == o.A && B == o.B) || (B == o.A && A == o.B);

來源

2012-12-21 20:51:38 dchhetri

我的邊緣在哪裏？

回答

相關問題