3

我对std::map 所需的operator<()方法有疑问。我使用结构作为复合键，如下所示：

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;
  }
}

如前所述，我想使用具有 4 个值的复合键，但我不知道如何为operator<方法实现这一点。我观察到一次只存储 1 个值！

谁能告诉我正确的条件是什么样的？

提前致谢！

4

3 回答 3

9

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

于 2012-04-23T07:25:32.167 回答
2

您的实施的问题是它不稳定，请考虑...

return mk1.string1 < mk2.string1 && mk1.string2 < mk2.string2 &&
       mk1.string3 < mk2.string3 && mk1.uint1 < mk2.uint1;

...评估{ "a", "a", "a", 1 } < { "a", "b", "a", 1 }= a<a && ...= false && ...=false

...但是{ "a", "b", "a", 1 } < { "a", "a", "a", 1 }= a<a && ...= false && ...=false

因此，尽管它们在map.

一个可行的解决方案：每个必要的字符串比较只进行一次是简洁而高效的......

friend bool operator<(const MyKey& mk1, const MyKey& mk2)
{
    int x;
    return (x = mk1.string1.compare(mk2.string1)) ? x < 0 :
           (x = mk1.string2.compare(mk2.string2)) ? x < 0 :
           (x = mk1.string3.compare(mk2.string3)) ? x < 0 :
           mk1.uint1 < mk2.uint1;
}
于 2012-04-23T07:46:17.200 回答
2

我认为您的问题在于 operator< 不一定实现严格的弱排序。A<Bwhere和 is false的组合太多了B<A， whereA和BareMyKey对象。这被解释为A等于B。

于 2012-04-23T07:28:58.443 回答