基于 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

附件是工作代码。您缺少的棘手部分是没有添加一段代码来遍历已经工作的集合，然后检查值。你很接近！如果您需要更彻底的答案，我会在评论中回答问题。希望这对您有所帮助！

#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)


}

Answer 2

您的代码无法工作¹，因为您的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。 std::unordered_set 似乎更适合这项任务。您只需要一个 operator== 来比较是否相等，这是微不足道的，并且一个散列函数 returns 对于被认为相同的元素具有相同的值。它可以像添加 m 和 n.

一样简单

¹ 嗯，也许它可以工作，或不工作，或两者兼而有之，这是未定义的行为。

基于 std::set 的无序选择实现最终有重复项

Unordered selection implementation based on std::set ends up having duplicates

c++

set

stdset