6

I am having difficulties to set up the comparison correctly. Here is an example of my problem, where my code wrongly assumes {1,2}={2,1}: http://ideone.com/i7huL

#include <iostream>
#include <map>
using namespace std;

struct myStruct {
  int a;
  int b;
  bool operator<(const myStruct& rhs) const {
           return rhs.a < this->a && rhs.b < this->b;
  }
};


int main() {
       std::map  <myStruct, int> mymap ;
       myStruct m1={1,2};
       myStruct m2={2,1};
       mymap.insert(make_pair(m1,3));
       std::map<myStruct, int>::iterator it1 = mymap.find(m1);
       std::map<myStruct, int>::iterator it2 = mymap.find(m2);
       cout << it1->second << it2->second;
       // here it1->second=it2->second=3, although I would have expected it2 to be equal to map.end().
}

I could use || instead of &&, but I'm not sure this is the correct way either. I just want to have operator< implemented in such a way that I am able to find objects in my map, without making any errors, as is the case in the code I linked to.

Thanks.

4

7 回答 7

7

是的,这个操作符实现没有多大意义。我建议:

  bool operator<(const myStruct& rhs) const {
      return rhs.a < this->a || (rhs.a == this->a && rhs.b < this->b);
  }
于 2012-07-28T19:15:20.283 回答
7
bool operator<(const myStruct& rhs) const {
  if (a < rhs.a) return true;
  if (a == rhs.a) return b < rhs.b;
  return false;
}

如果您正在寻找对许多数据成员的概括,那么有一个使用 C++11 std::tie的好例子:

struct S {
    int n;
    std::string s;
    float d;
    bool operator<(const S& rhs) const {
        return std::tie(n, s, d) < std::tie(rhs.n, rhs.s, rhs.d);
    }
};
于 2012-07-28T19:18:03.673 回答
5

问题是您的运营商没有定义严格的弱排序。仔细想想你的例子{1,2}{2,1}你的运营商会怎样。假设X = {1,2}Y = {2,1}

X < Y?1 < 22 < 1?不,因此 X 不小于 Y。

Y < X?2 < 11 < 2?不,因此 Y 不小于 X。

那么,如果 X 不小于 Y,并且 Y 不小于 X,还剩下什么?他们是平等的。

您需要选择结构的成员之一,或者a作为b主要比较。如果主要比较结果相等,那么您才检查次要比较。就像你按字母顺序排列某些东西一样。首先你检查第一个字母,只有当它们相等时,你才能继续下一个。Hans Passant 提供了一个例子。

对于您的操作员,这是一个更严重的问题示例。我上面给出的不一定是坏的,因为也许你 {1,2}被认为等于{2,1}。基本问题作物具有这样的一组值:考虑X = {1,1}, Y = {1,2}, Z = {2,2}

对于您的运算符,X 肯定小于 Z,因为 1 小于 2。但是 X 等于 Y,Y 等于 Z。为了遵守严格的弱排序,如果 X = Y,并且 Y = Z,那么 X 应该等于 Z。但这里不是这样。

于 2012-07-28T19:24:26.887 回答
3

您询问了如何推广到四个 int 成员,这是我将如何构建此类代码以获得最大清晰度。

bool operator<(const myStruct& rhs) const
{
  if (a < rhs.a)
    return true;
  if (a > rhs.a)
    return false;
  if (b < rhs.b)
    return true;
  if (b > rhs.b)
    return false;
  if (c < rhs.c)
    return true;
  if (c > rhs.c)
    return false;
  if (d < rhs.d)
    return true;
  if (d > rhs.d)
    return false;
  return false;
}

您可以轻松地为任意数量的数据成员扩展此类代码。

于 2012-07-28T19:24:10.613 回答
1

我更喜欢通过比较元素的相等性来写这个,直到找到两个不同的元素:

bool operator<(const myStruct& rhs) const {
    if (a != rhs.a)
        return a < rhs.a;
    if (b != rhs.b)
        return b < rhs.b;
    return false; // this and rhs are equal.
}

我发现这比用 || 混合编写单个表达式更清晰、更可扩展。和 && (根据@HansPassant),并且比@jahhaj 让每个通过测试导致 a return true;or的方法更紧凑return false;。性能大致相同,除非您对值的分布有所了解。有一个避免operator==()和只使用的论点operator<(),但这仅适用于您尝试编写最大程度的通用模板代码。

于 2012-07-29T17:40:22.217 回答
1

最简单的解决方案用于std::tie比较元组。

return std::tie(rhs.a, rhs.b) < std::tie(a, b);

这可以非常快速且简单地推广到更多数据成员。

于 2012-07-28T19:33:06.470 回答
0

问题是你需要知道你的结构代表什么。否则定义 < 运算符将变得任意。其他人将无法给你一个合适的答案。举一个例子,当你的结构表示二维点的笛卡尔坐标时。在这种情况下,您可以定义一个有意义的排序运算符,例如结构与原点的距离。

即,距离 d1 = this->a*this->a + this->b*this->b 距离 d2 = rhs.a*rhs.a + rhs.b*rhs.b if(d1 < d2) 返回 true ; 否则返回假;

于 2012-07-28T19:26:29.873 回答