CODEWITHSUNDEEP
c++setstdset
Slaus
Slaus

Reputation: 2236

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

Trying to implement a combination of 4 objects taken 2 at a time without taking into account the arrangement (such must be considered duplicates: so that order is not important) of objects with std::set container:

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

The expected set of combinations is 0 1, 0 2, 0 3, 1 2, 1 3, 2 3 which is 6 of those, but resulting c.size() == 12. Also, my operator<(Combination,Combination) does satisfy !comp(a, b) && !comp(b, a) means elements are equal requirement.

What am I missing?

Upvotes: 1

Views: 46

Answers (2)

Lukas-T
Lukas-T

Reputation: 11350

Your code can't work1, because your operator< does not introduce a strict total ordering. One requirement for a strict total ordering is that, for any three elements a, b and c

a < b

and 

b < c

imply that 

a < c

(in a mathematical sense). Let's check that. If we take 

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

you see that 

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

but 

a < c => false

If you can't order the elements you can't use std::set. A std::unordered_set seems to more suited for the task. You just need a operator== to compare for equality, which is trivial and a hash function that returns the same value for elements that are considere identical. It could be as simple as adding m and n.

1 Well, maybe it could work, or not, or both, it's undefined behaviour.

Upvotes: 1

user13072753
user13072753

Reputation:

Attached is the working code. The tricky part that you were missing was not adding a section of code to iterate through the already working set to then check the values. You were close! If you need a more thorough answer I will answer questions in the comments. Hope this helps!

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


}

Upvotes: 1

Related Questions