Реализация неупорядоченного выбора, основанная на std :: set, заканчивается дубликатами

Question

Попытка реализовать комбинацию из 4 объектов, взятых по 2 за раз, без учета расположения (такое должно считаться дубликатом: так, чтобы порядок не важен) объектов с std::set контейнером:

struct Combination {
    int m;
    int n;
    Combination(const int m, const int n):m(m),n(n){}
};
const auto operator<(const auto & a, const auto & b) {
    //explicitly "telling" that order should not matter:
    if ( a.m == b.n && a.n == b.m ) return false;
    //the case "a.m == b.m && a.n == b.n" will result in false here too:
    return a.m == b.m ? a.n < b.n : a.m < b.m;
}
#include <set>
#include <iostream>
int main() {
    std::set< Combination > c;
    for ( short m = 0; m < 4; ++ m ) {
    for ( short n = 0; n < 4; ++ n ) {
        if ( n == m ) continue;
        c.emplace( m, n );
    } }
    std::cout << c.size() << std::endl; //12 (but must be 6)
}

Ожидаемый набор комбинаций: 0 1, 0 2, 0 3, 1 2, 1 3, 2 3, что составляет 6 из них, но в результате c.size() == 12. Кроме того, мой operator<(Combination,Combination) удовлетворяет !comp(a, b) && !comp(b, a) means elements are equal требованию.

Чего мне не хватает?

Answer 1

Ваш код не может работать ¹ , потому что ваш operator< не вводит строгий общий порядок . Одно требование для строгого общего порядка состоит в том, что для любых трех элементов a, b и c

a < b

и

b < c

подразумевается, что

a < c

(в математическом смысле). Давайте проверим это. Если мы возьмем

Combination a(1, 3);
Combination b(1, 4);
Combination c(3, 1);

, вы увидите, что

a < b => true
b < c => true

, но

a < c => false

---

Если вы не можете упорядочить элементы, которые вы не можете использовать std::set. A std::unordered_set кажется более подходящим для этой задачи. Вам просто нужно operator== для сравнения на равенство, что тривиально, и функция ha sh, которая возвращает одинаковое значение для элементов, которые считаются идентичными. Это может быть так же просто, как добавить m и n.

---

¹ Ну, может быть, может работать, или нет, или оба, это неопределенное поведение.

Answer 2

Прилагается рабочий код. Хитрая часть, которую вы пропустили, не добавляла раздел кода для итерации по уже работающему набору, чтобы затем проверить значения. Вы были близки! Если вам нужен более подробный ответ, я отвечу на вопросы в комментариях. Надеюсь, это поможет!

#include <set>
#include <iostream>


using namespace std; 

struct Combination {
    int m;
    int n;
    Combination(const int m, const int n):m(m),n(n){}
};
const auto operator<(const auto & a, const auto & b) {
    //explicitly "telling" that order should not matter:
    if ( a.m == b.n && a.n == b.m ) return false;
    //the case "a.m == b.m && a.n == b.n" will result in false here too:
    return a.m == b.m ? a.n < b.n : a.m < b.m;
}


int main() {
    set< Combination > c;
    for ( short m = 0; m < 4; ++ m ) 
    {
         for ( short n = 0; n < 4; ++ n ) 
          { 
                //Values are the same we do not add to the set
                if(m == n){

                    continue; 
                }
                else{
                   Combination s(n,m);  

                   const bool is_in = c.find(s) != c.end();
                   if(is_in == true){

                       continue; 
                   }
                   else{
                       cout << " M: " << m << " N: " << n << endl; 
                       c.emplace( m, n); 
                   }

                }
          } 
    }

    cout << c.size() << endl; //16 (but must be 6)


}