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?
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.