std map composite key

Question

I have a problem with the operator<() method which is required for a std::map. I'm using a struct as composite key that looks as follows:

struct MyKey {
  std::string string1;
  std::string string2;
  std::string string3;
  unsigned int uint1;

  friend bool operator<(const MyKey& mk1, const MyKey& mk2)
  {
    return mk1.string1 < mk2.string1 && mk1.string2 < mk2.string2 &&
           mk1.string3 < mk2.string3 && mk1.uint1 < mk2.uint1;
  }
}

As introduced I want to use a composite key with 4 values, but I don't know how to achieve this for the operator< method. I observed that only 1 value is stored at a time!

Can anybody tell me how the right condition looks like?

Thanks in advance!

Answer 1

The Standard library's associative containers such as std::map, std::set, std::multiset, std::multimap, std::bitset require that the ordering of elements must follow Strict Weak Ordering, which means your implementation of operator< must follow strict weak ordering. So one implementation could be this:

friend bool operator<(const MyKey& mk1, const MyKey& mk2)
{
  if (mk1.string1 != mk2.string1 )
       return mk1.string1 < mk2.string1;

  else if ( mk1.string2 != mk2.string2)
       return mk1.string2 < mk2.string2;

  else if (mk1.string3 != mk2.string3)
       return  mk1.string3 < mk2.string3;

  else
       return mk1.uint1 < mk2.uint1;
}

Or you can implement it as:

friend bool operator<(const MyKey& mk1, const MyKey& mk2)
{
  auto const & t1 = std::tie(mk1.string1, mk1.string2, mk1.string3, mk1.uint1);
  auto const & t2 = std::tie(mk2.string1, mk2.string2, mk2.string3, mk2.uint1);
  return t1 < t2;
}

In this solution, std::tie function creates two tuples t1 and t1 of the references of the arguments passed to it, and then compare t1 and t2 using overloaded operator< for std::tuple instead. The operator< for tuple compares the elements lexicographically — strict-weak ordering is achieved..

Answer 2

I think you have a problem in that the operator< doesn't necessarily implement strict weak ordering. There are too many combinations where A<B is false and B<A is also false, where A and B are MyKey objects. This is interpreted as A being equal to B.