C++設置：存儲重複項：關於<運算符

Question

我很新C++（但知道我的方式圍繞C），所以我可能錯過了一些明顯的東西。

TLDR：我使用一個std :: set來儲存元素兩次，這絕對不是我想要的。

長的故事： 我已定義的類集團和我需要存儲這個類中的一組元素，所以我定義了<運營商派：

class Clique{ 
public : 
    int b; 
    int e; 
    int l; 
    std::set<int> X; 

    bool operator <(const Clique &rhs) const 
    { 
    if(b < rhs.b) 
     return true; 
    if(e < rhs.e) 
     return true; 
    if(X.size() < rhs.X.size()) 
     return true; 
    std::set<int>::iterator itX = X.begin(); 
    std::set<int>::iterator itrhs = rhs.X.begin(); 
    // both sets have same size, need only to check end for one of them                                    
    while((*itX == *itrhs) && (itX != X.end())){ 
     ++itX; 
     ++itrhs; 
    } 
    if(itX == X.end()){ 
     //both sets are equal                                               
     return false; 
    } 
    else 
     return (*itX < *itrhs); 
    } 

    void print_clique(FILE *F) const ; 
}; 

（我沒」確定如何設置比較完成，所以我寫了一個例程，首先按大小比較它們，然後逐個元素地進行比較）。

現在我想將Clique元素存儲在一個集合中，這就是問題出現的地方。 我的std :: set （1）似乎不按照我定義的順序存儲Clique元素; （2）存儲相同派

我已經寫了幾個拷貝打印一組桂系：

void print_cliqueset(std::set<Clique> mySet){ 
    int setsize = 0; 

    std::set<Clique>::iterator it = mySet.begin(); 
    Clique cur_c = *it; 
    Clique prev_c = *it; 
    while(it != mySet.end()){ 
    // for(std::set<Clique>::iterator it = mySet.begin(); it != mySet.end(); ++it){                                
    it->print_clique(stdout); 
    setsize ++; 
    ++it; 
    if(it != mySet.end()){ 
     cur_c = *it; 
     assert (prev_c < cur_c); 
     gassert(prev_c.b <= cur_c.b); 
    prev_c = *it; 
    } 
    } 

    assert(setsize == mySet.size()); 
} 

我的功能比需要更多的複雜，但我想確保我的理解發生了什麼事。

這裏是印刷這樣的一組的一個典型輸出： 有用於每個派，其中我打印第一b，則e，然後在集合X

6829 9716 1 2 3 5 8 9 10 
6792 9687 1 2 3 7 8 9 10 
606 6531 1 2 3 5 6 7 8 9 
6829 9687 1 2 3 5 7 8 9 10 
410 9951 2 6 
484 9805 1 2 4 6 
494 9805 2 4 6 10 
506 9805 1 2 5 6 
484 9821 1 2 4 
484 9871 2 3 4 6 
506 9821 1 2 5 
484 9802 1 2 3 4 6 
486 9805 1 2 4 6 9 
486 9802 1 2 3 4 6 9 
507 9802 1 2 3 4 6 9 10 
502 9802 1 2 3 4 6 10 
506 9802 1 2 3 5 6 
507 9806 1 2 4 9 10 
507 9805 1 2 5 6 9 
527 9806 1 2 5 9 10 

元件由於我們的線可以看到，派系並沒有按照我定義的（或想要定義的）順序排序。他們應該首先由成員b（這是每行的第一行）排序，而事實並非如此。

然後我在輸出中有一些重複行（沒有出現在上面的例子中，但出現在完整的輸出中）。我想因爲它似乎混淆有關訂單的事實，我有重複並不奇怪...

我想答案是什麼很明顯的，但我看不到它。任何幫助，將不勝感激！

Answer 1

你bool operator <(const Clique &rhs) const是錯誤的，因爲它不尊重嚴格的順序。

它可以簡單地是：

bool operator <(const Clique& rhs) const 
{ 
    return std::tie(b, e, X) < std::tie(rhs.b, rhs.e, rhs.X); 
} 

Answer 2

您的operator<已損壞。考慮兩個Clique S：

c1 is {b = 0, e = 1, ...} 
c2 is {b = 1, e = 0, ...} 

你的代碼將返回true兩個c1 < c2和c2 < c1。

顯然，在這種情況下std::set顯示出奇怪的行爲。

我會解決你的operator<以下列方式：

bool operator <(const Clique &rhs) const 
{ 
    if(b != rhs.b) 
     return b < rhs.b; 
    if(e != rhs.e) 
     return e < rhs.e; 
    if(X.size() != rhs.X.size()) 
     return X.size() < rhs.X.size(); 
    std::set<int>::iterator itX = X.begin(); 
    std::set<int>::iterator itrhs = rhs.X.begin(); 
    // both sets have same size, need only to check end for one of them 
    while((itX != X.end()) && (itX == *itrhs)){ 
     ++itX; 
     ++itrhs; 
    } 
    if(itX == X.end()){ 
    //both sets are equal 
     return false; 
    } 
    else 
     return (*itX < *itrhs); 
} 

Answer 3

操作者<的定義應使得對於每個對元素「B」和「E」之間的關係b < e應被用來確定任何種關係。以下是等價的力量在這裏：

a > b < ==>b < a

a == b < ==>!(a < b) && !(b < a)

a >= b < ==>`（一< B）

等等上。如果您爲每個關係檢查使用多個字段進行檢查，那麼您有一種多維範圍。只有這樣做才能達到平坦範圍：

• 更重要的字段首先被檢查;如果在此字段中的值不相等，則立即返回結果
• 否則 - 如果它們相等 - 則檢查顯着性順序中的下一個字段，依此類推。

在集合中使用這種複雜的關係定義的要求會讓事情變得更加困難，因爲您應該做的就是說明一個元素是否小於另一個元素。所以在你的情況下，你必須自己檢查等於。如果lhs.b > rhs.b您的程序檢查字段「下一個重要性鏈」。

Answer 4

運營商<必須提供嚴格的弱排序。即如果x < y則!(y < x)和!(y == x)。

在Clique的情況下，要求似乎是元素b，e和X在詞彙上進行比較。

來表示這種情況的慣用方法是做所有比較中的operator<方面：

#include <set> 

class Clique{ 
public : 
    int b; 
    int e; 
    int l; 
    std::set<int> X; 

    bool operator <(const Clique &r) const 
    { 
     auto const& l = *this; 

     if (l.b < r.b) return true; 
     if (r.b < l.b) return false; 

     if (l.e < r.e) return true; 
     if (r.e < l.e) return false; 

     if (l.X < r.X) return true; 
     if (r.X < l.X) return false; 

     return false; 
    } 

    void print_clique(FILE *F) const ; 
}; 

是的，std::set確實提供operator<當密鑰類型提供它。

另一種方式來寫這個，因爲賈羅德被暗指是這樣的：

#include <set> 
#include <tuple> 

class Clique{ 
public : 
    int b; 
    int e; 
    int l; 
    std::set<int> X; 

    bool operator <(const Clique &r) const 
    { 
     auto const& l = *this; 
     return std::tie(l.b, l.e, l.X) < std::tie(r.b, r.e, r.X); 
    } 

    void print_clique(FILE *F) const ; 
}; 

這一點我想你會同意簡潔，富有表現力，準確，地道。