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.

Answer 2

Your less operator should be:

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

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

      return false;
  }
};

When you compare structures with multiple elements it might help to think of structures as words and elements as characters.

With this modification, the less operator works lexicographically, the way you compare two words of the same length when you sort them: you continue the comparison on the next position while the words have the same character at the current position and decide when the characters at the current position differ. If you reach the end of both words, the words are equal.

Answer 3

You could hide the intricacies of the comparator and solve the bug (already explained by @MarkoMahnič) by making use of std::tie.

bool operator()(const Key& lhs, const Key& rhs)
{
   return std::tie(lhs.first, lhs.second) < std::tie(rhs.first, rhs.second);
}

Answer 4

Your comparator doesn't meet the requirements of std::map, it needs to provide a strict weak ordering. Fortunately std::tuple implements this for you if you need to compare multiple values:

struct KeyLess {
  bool operator()(const Key& lhs, const Key& rhs) {
      return std::tie(lhs.first, lhs.second) < std::tie(rhs.first, rhs.second);
  }
};

In your case you don't actually need a custom comparator at all as std::pair's < operator already has the same behaviour.

Answer 5

Your KeyLess code result in incorrect comparison:

KeyLess cmp;
std::cout << cmp(Key{2, 169},Key{1, 391})<< std::endl;  // yields true
std::cout << cmp(Key{1, 391},Key{2, 169})<< std::endl;  // yields true

When both comparisons yields false, it means that keys are equal, when they yield true, behavior of map iterator is not defined. It's related to the fact that map sorts its elements.

Note that operator()required to be const or program might not compile with standard C++17 and later. As a possible variant:

#include <map>
#include <iostream>

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

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

      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 &[key, value]: m) {
        std::cout << "Key: " << key.first << ", " << key.second << " Value: "<< value << std::endl;
    }
}