Iterating over std::map with custom less operator implementation gives less elements that it contains

Question

Assuming I have the following simple program (http://cpp.sh/5sygh):

#include <map>
#include <iostream>

using Key = std::pair<unsigned long, unsigned long long>;

struct KeyLess {
  bool operator()(const Key& lhs, const Key& rhs) {
      if (lhs.first < rhs.first) {
        return  true;
      }

      if (lhs.second < rhs.second) {
        return true;
      }

      return false;
  }
};

int main() {
    std::map< Key , int, KeyLess> m;
    m[Key{2, 169}] = 1;
    m[Key{1, 255}] = 2;
    m[Key{1, 391}] = 3;
    m[Key{1, 475}] = 4;

    std::cout << "Elements in map: " << m.size() << std::endl;     
    for(const auto &x: m) {
        std::cout <<"Value: "<< x.second << std::endl;
    }
}

The output contains only 2 items instead of 4 in the map:

Elements in map: 4
Value: 2
Value: 1

What do I miss here?

Answer 1

Your compare function does not meet the requirements of strict weak ordering.

In SWO, if A < B, and B < C, then A must be less than C. Key equality is also checked by seeing if two values are not less than each other. If (!(a<b) && !(b<a)) then a == b. Two keys should not both be less than each other.

For your keys and using your compare function

Key{2, 169} < Key{1, 255} // this is true because 169 < 255
Key{1, 255} < Key{2, 169} // this is also true because 1 < 2

Obviously this is a problem, since both of these keys compare less than each other using your comparator.

My suggested solution: since your keys are std::pairs, you shouldn't need to define a new comparator. std::pair already uses lexicographical compare by default.