为一个结构体定义 operator<

Question

我有时会将小的structs用作映射中的键，因此我必须为它们定义一个operator<。通常，这看起来像这样：

struct MyStruct
{
    A a;
    B b;
    C c;

    bool operator<(const MyStruct& rhs) const
    {
        if (a < rhs.a)
        {
           return true;
        }
        else if (a == rhs.a)
        {
            if (b < rhs.b)
            {
                return true;
            }
            else if (b == rhs.b)
            {
                return c < rhs.c;
            }
        }

        return false;
    }
};

这似乎过于冗长且容易出错。是否有更好的方法或者某种可以自动定义 struct 或 class 的 operator< 的简单方法？

我知道一些人喜欢使用像 memcmp(this, &rhs, sizeof(MyStruct)) < 0 这样的东西，但如果成员之间存在填充字节或者 char 字符串数组在 null 终止符后可能包含垃圾数据，则此方法可能无法正常工作。

- Kristopher Johnson

---

可以用更简洁的方式，但不会显著增加错误率：return (a < rhs.a) || (a == rhs.a && ((b < rhs.b) || (b == rhs.b && c < rhs.c))); - Jon Purdy

顺便提一下，由于你的第一个 if 子句实际上已经返回，所以不需要使用 else 关键字。内部代码块也是如此。在这两种情况下，你可以直接省略 else 这个单词。 - Andrew Truckle

Answer 1

这是一个相当古老的问题，因此这里的所有答案都已过时。C++11允许更优雅和高效的解决方案：

bool operator <(const MyStruct& x, const MyStruct& y) {
    return std::tie(x.a, x.b, x.c) < std::tie(y.a, y.b, y.c);
}

为什么这种方法比使用 boost::make_tuple 更好呢？因为 make_tuple 会创建所有数据成员的副本，这可能代价高昂。相比之下，std::tie 只会创建一个轻量级引用包装器（这个包装器有可能被编译器完全优化掉）。

实际上，上述代码现在应该被认为是用于实现具有多个数据成员的结构体的词典序比较的惯用方法。

- Konrad Rudolph

---

值得一提的是，上述代码无法正常工作 - 运算符 < 只接受一个参数。operator<(const MyStruct& rhs) - Riot

不，这段代码本身没有问题。不过，它需要在MyStruct之外定义 - 这是最佳实践。 - Konrad Rudolph

使用大型结构体和C++1y，您可以添加一个函数auto AsTuple(const MyStruct & s) { return std::tie(s.x, s.y); }。这样避免了在operator <中重复编写结构体的字段……不幸的是，我没有看到在C++11中实现它的任何方法。 - Renaud

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Konrad Rudolph

我的代码实现了字典排序比较。而字典排序比较是一个严格的弱序关系，它是反对称和传递性的。 - Konrad Rudolph

Answer 2

其他人提到了boost::tuple，它可以为你提供字典序比较。如果你想将其保留为具有命名元素的结构体，则可以创建用于比较的临时元组：

bool operator<(const MyStruct& x, const MyStruct& y)
{
    return boost::make_tuple(x.a,x.b,x.c) < boost::make_tuple(y.a,y.b,y.c);
}

在C++0x中，这变成了std::make_tuple()。

更新：现在C++11已经出现了，它变成了std::tie()，可以创建一个引用元组而无需复制对象。有关详细信息，请参见Konrad Rudolph的新答案。

- Mike Seymour

---

我想知道构建这些元组对象对性能有多大影响。 - Timo

@Timo: 构建和比较应该内联，所以如果它比直接比较值更慢，我会感到惊讶。但唯一确定的方法是测量它。 - Mike Seymour

如果您需要比较 x.geta()、x.getb()、x.getc() 或其他返回引用的函数，这仍然是一个不错的选择。但我还没有能够使用 tie 来实现这一点。 - Johan Lundberg

Answer 3

我会这样做：

#define COMPARE(x) if((x) < (rhs.x)) return true; \
                   if((x) > (rhs.x)) return false;
COMPARE(a)
COMPARE(b)
COMPARE(c)
return false;
#undef COMPARE

- Benoit

---

这种东西无法使用模板进行替换，因为需要从封闭函数中返回。一个建议是：将(x)>(rhs.x)替换为(rhs.x)<(x)，只依赖于成员的operator<。此外，我认为括号是多余的，如果输入需要它们，我无法看出这个宏如何正常工作。 - Mark Ransom

我会将最后的COMPARE(c); return false;替换为return c < rhs.c，以避免多余的>比较。 - Kristopher Johnson

你说得对。这是在易读性和效率之间做出妥协的问题。 - Benoit

如果你不在乎可读性，为什么还要使用if语句？ COMPARE（X，def）（！（rhs.x < x）&&（x < rhs.x））&& def; 返回COMPARE（a，COMPARE（b，COMPARE（c，true）））; 但是再次考虑，为什么要猜测哪个更快。编写代码，编译，时间，然后_potentially_优化和可读性的代码更容易优化。 - Rune FS

Answer 4

在这种情况下，你可以使用boost::tuple<int, int, int> - 它的operator<按照你所需的方式正常工作。

- Steve Townsend

Answer 5

我认为最简单的方法是在所有比较中坚持使用 < 操作符，而不使用 > 或 ==。以下是我遵循的模式，您可以对所有结构体进行跟随：

typedef struct X
{
    int a;
    std::string b;
    int c;
    std::string d;

    bool operator <( const X& rhs ) const
    {
        if (a < rhs.a) { return true; }
        else if ( rhs.a < a ) { return false; }

        // if neither of the above were true then 
        // we are consdidered equal using strict weak ordering
        // so we move on to compare the next item in the struct

        if (b < rhs.b) { return true; }
        if ( rhs.b < b ) { return false; }

        if (c < rhs.c) { return true; }
        if ( rhs.c < c ) { return false; }

        if (d < rhs.d) { return true; }
        if ( rhs.d < d ) { return false; }

        // if both are completely equal (based on strict weak ordering)
        // then just return false since equality doesn't yield less than
        return false;
    }
};

- bjackfly

---

你需要“else”做什么？ - ackb

非常喜欢 < 运算符需要以自身为定义的想法。 - ceorron

Answer 6

我通常这样实现词典排序：

bool operator < (const MyObject& obj)
{
    if( first != obj.first ){
        return first < obj.first;
    }
    if( second != obj.second ){
        return second < obj.second;
    }
    if( third != obj.third ){
        return third < obj.third
    }
    ...
}

请注意，对于浮点数值（G++警告），需要额外考虑，对于这些内容，类似以下代码会更好:

bool operator < (const MyObject& obj)
{
    if( first < obj.first ){
        return true;
    }
    if( first > obj.first ){
        return false;
    }
    if( second < obj.second ){
        return true;
    }
    if( second > obj.second ){
        return false;
    }
    ...
}

- Frigo

Answer 7

我所知道的最好方法是使用 boost tuple。它提供了内置的比较和构造函数等功能。

#include <boost/tuple/tuple.hpp>
#include <boost/tuple/tuple_comparison.hpp>

typedef boost::tuple<int,int,int> MyStruct;

MyStruct x0(1,2,3), x1(1,2,2);
if( x0 < x1 )
   ...

我也喜欢Mike Seymors的建议，使用boost的make_tuple来创建临时元组。

- Peter G.

---

是的... 但是当涉及到复杂结构时，它执行得好吗？ - Benoit

为什么它不能表现良好？这项工作发生在编译时。 - Peter G.

Answer 8

#include <iostream>

#include <boost/fusion/include/adapt_struct.hpp>
#include <boost/fusion/include/less.hpp>

struct MyStruct {
   int a, b, c;
};

BOOST_FUSION_ADAPT_STRUCT( MyStruct,
                           ( int, a )
                           ( int, b )
                           ( int, c )
                          )

bool operator<( const MyStruct &s1, const MyStruct &s2 )
{
   return boost::fusion::less( s1, s2 );
}

int main()
{
   MyStruct s1 = { 0, 4, 8 }, s2 = { 0, 4, 9 };
   std::cout << ( s1 < s2 ? "is less" : "is not less" ) << std::endl;
}

- usta

Answer 9

如果您无法使用boost，可以尝试类似以下的方式：

#include <iostream>

using namespace std;

template <typename T>
struct is_gt
{
  is_gt(const T& l, const T&r) : _s(l > r) {}

  template <typename T2>
  inline is_gt<T>& operator()(const T2& l, const T2& r)
  {
    if (!_s)
    {
      _s = l > r;
    }
    return *this;
  }

  inline bool operator!() const { return !_s; }

  bool _s;
};

struct foo
{
  int a;
  int b;
  int c;

  friend bool operator<(const foo& l, const foo& r);
};

bool operator<(const foo& l, const foo& r)
{
  return !is_gt<int>(l.a, r.a)(l.b, r.b)(l.c, r.c);
}

int main(void)
{
  foo s1 = { 1, 4, 8 }, s2 = { 2, 4, 9 };
  cout << "s1 < s2: " << (s1 < s2) << endl;
  return 0;
}

我猜这个方法避免了任何宏，只要结构中的类型支持<，它应该可以工作。当然，这种方法会有一些额外的开销，需要构造is_gt，并且对于每个参数如果其中一个值大于另一个值，就会产生多余的分支...

编辑：

根据评论修改后，这个版本现在也应该进行短路优化了，现在使用两个布尔值来保持状态（不确定是否有办法用一个布尔值实现）。

template <typename T>
struct is_lt
{
  is_lt(const T& l, const T&r) : _s(l < r), _e(l == r) {}

  template <typename T2>
  inline bool operator()(const T2& l, const T2& r)
  {
    if (!_s && _e)
    {
      _s = l < r;
      _e = l == r;
    }
    return _s;
  }

  inline operator bool() const { return _s; }

  bool _s;
  bool _e;
};

并且

bool operator<(const foo& l, const foo& r)
{
  is_lt<int> test(l.a, r.a);
  return test || test(l.b, r.b) || test(l.c, r.c);
}

只需收集各种比较的有趣函数即可。

- Nim

---

如果这两个结构体相等，这段代码能正常工作吗？在这种情况下，operator<() 应该返回 false，但是我觉得你只检查了不大于的情况。 - Kristopher Johnson

这种方法不允许短路评估 - 有什么办法可以解决吗？ - mskfisher

@mskfisher - 我想我可以做到，但是再考虑一下...所有这些非常复杂的方法都有点毫无意义，你需要的是||运算符！即，返回l.a < r.a || l.b < r.b || l.c < r.c; 请参见上面的编辑... - Nim

新的||方法不能处理l.a > r.a且l.b < r.b的情况 - 它应该返回false，但实际上它会返回true。 - mskfisher

@mskfisher，糟糕，你说得对 - 今天太长了...最终编辑应该有一个短路版本，现在运算符不是一行代码了... - Nim

Answer 10

我刚学会了 boost::tuple 技巧，感谢 @Mike Seymour！

如果你买不起 Boost，我的最爱是：

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;

    return (c < rhs.c);
}

我喜欢这个结构是因为它把所有东西都设置在平行的结构中，这使得错误和遗漏更容易被发现。

不过，当然，你已经进行了单元测试，对吧？

- mskfisher

---

请注意，这基本上与@Benoit的答案相同，只是没有宏，因此那个答案的评论也适用于这里。 - Kristopher Johnson

谢谢。已经注意到了Mark Ransom提到的仅使用<的观点。 - mskfisher