simon simon - 1 month ago 13
Less Question

What are the requirements of std::map's compare parameter regarding strict ordering?

I have an integral type, which represents a ring buffer index. The less comparison function defined this way:

friend bool operator < (const CircularValue & lhs, const CircularValue &rhs) {
UInt max = lhs.value + std::numeric_limits<UInt>::max() / 2;
return (lhs.value < max)
? rhs.value > lhs.value && rhs.value < max
: rhs.value > lhs.value || rhs.value < max;
}


Lhs considered lower than rhs if rhs takes place in the half of the available interval above lhs.
I would like to use it in a map as key, but not sure if it can cause problem. It has the property of irreflexivity and asymmetry, but not transitivity.

Answer

It will cause problems. As described by cppreference, the following requirements must be met by a comparator:

  • cmp(a,a) yields false
  • if cmp(a,b) yields true, then cmp(b,a) yields false
  • if cmp(a,b)==true and cmp(b,c)==true then cmp(a,c) must also be true (this won't be met by your comparator)
  • if a and b are to compare equal, then both cmp(a,b) and cmp(b,a) yield false