C++ set: сохранение дубликатов: путают около <operator

Question

Я довольно новичок в C++ (но знаю свой путь вокруг C), поэтому мне, вероятно, не хватает чего-то очевидного.

TLDR: Я использую std :: set, который хранит элементы дважды, что определенно не то, что я хочу.

Длинная история: я определил класс Clique и мне нужно хранить элементы этого класса в наборе, поэтому я определил оператор < для Clique:

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 в наборе, и здесь возникает проблема. My std :: set (1) не хранит элементы Clique в том порядке, который я определил; (2) хранит несколько копий одного и того же кликой

Я написал функцию для печати набор Clique:

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()); 
} 

Моя функция является более сложной, чем это необходимо, но я хотел, чтобы убедиться, что я понял, что происходило.

Вот типичный выход печати такого набора: Там есть строка для каждой клики, в котором я напечатать первую б, то е, то элементов множества 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» и «е» отношений b < e должно быть использовано для определения любого вида отношения. Следующие эквивалентности действуют здесь:

a > b < ==>b < a

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

a >= 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 ; 
}; 

который я думаю, вы согласитесь, лаконичен, выразительный, правильно и идиоматический.